04级数据结构试卷b标准答案.doc

山东轻工业学院06/07学年 第2学期《数据结构》期末考试试卷（B卷）适用班级：信管专业04级1～2班 标准答案及评分标准 单项选择题。（本题满分15分，每小题1分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 D D B B D C C C B D B B D D D 二、多项选择题（本题满分30分，每空2分） 1、ACD 、2、B H 3、C E 4、A E 5、ACD 6、CD 7、AD 8、ABDE 9、AD 10、ACD 11、AC 12、C 三、填空题。（本题满分15分，每空1分） 1、（Py-next=px-next;）（ px-next=py;） 2、（4） （2） 3、（相同） 4、（物理存储位置）（链指针） 5、（指针） 6、（sxssxsxx）7、（栈）8、（只允许在表的一端进行插入而在 一端进行元素的删除）9、（队尾指针）（存入）10、（O(1)） （O(n)） 四、判断题。（本题满分10分，每小题1分） 1 2 3 4 5 √ √ √ √ √ 五、简答题。（本题满分25分，每小题5分） 1．参考答案：（1）由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素，且其存储空间可以是连续的，也可以不连续；此外，这种存储结构对元素进行插入和删除操作时都无需移动元素，而仅仅修改指针即可，所以很适用于线性表容量变化的情况。（2.5分） （2）由于顺序存储结构一旦确定了起始位置，线性表中的任何一个元素都可以进行随机存取，即存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，故这一特点恰好避开了顺序存储结构的缺点。因此，应选用顺序存储结构。（2.5分） 2．参考答案：在单链表中只能由当前结点访问其后继的任一结点，但因其没有指向前驱的指针而无法访问其前驱结点。（2.5分）在双向链表中，由于当前结点既有指向后继结点的指针，又有指向前驱结点的指针，所以在双向链表中可以由当前结点出发访问表中的任何一个结点。（2.5分） 3．参考答案：语句2的循环控制变量I从0增加到n，测试到I=n才终止循环，共执行n+1次，但它的循环体却只能执行n次；语句3控制循环情况与此类似。可知各条语句的频度分别为1，n+1,n*(n+1)和n2 ,所以该程序段的语句频度为：T(n)=1+(n+1)+n*(n+1)+ n2 =2n2+2n+2 通常为了简化运算，可以用频度最大的语句衡量时间复杂度。当有若干个循环语句时，算法的时间复杂度由嵌套层数最多的语句的频度决定。如此题中，语句4的频度为n2 所以整个程序段的时间复杂度是O(n2) 。（5分） 4．参考答案：不合适。（3分）因为一个城市的设计和规划涉及非常多的项目，比较复杂，需要经常改动、扩充和删除各种信息，这样才能适应不断发展的需要；所以顺序表不能很好地适应其需要。（2分） 5．参考答案：顺序表。（5分） 六、算法设计（本题满分10分） 解答：（略） 你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。 ============================================================================== 命运如同手中的掌纹，无论多曲折，终掌握在自己手中 ==============================================================