A-2013-2014第2学期数据结构期末考卷答案.doc

诚信应考 考出水平 考出风格 浙江大学城市学院 2013 — 2014 学年第 2 学期期末考试答题卷 《 数据结构 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 06 月 29日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 总 分 得分 评卷人 注：试卷答案必须写在答卷上，写在试卷上不得分。 得分 一．判断题(有5条是正确的，将正确的编号写在答卷上，每空 1 分，共 5 分) 请把正确编号填入下表内。 1 5 7 8 9 得分 二．选择题 (本大题共 15 题，每题 1 分，共 15 分) 请把正确选项填入相应的题号内。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B D D B D D A C C C C C B B 得分 三．填空题 (本大题共 6 题 15 空，每空 1 分，共 15 分) 1．⑴ 数据元素的集合 ⑵ 关系的集合 2．⑶ n/2 ⑷ (n-1)/2 ⑸ O(n2) 3．⑹ 2 ⑺ 1 4．⑻ I ⑼ F ⑽ D 5．⑾ abdecf ⑿ 1 6．⒀ 3 ⒁ 4 ⒂ 2 得分 四．解答题 (本大题共 3 题，每题 5 分，共 15 分) 设置表尾指针的循环单链表好。假设循环单链表长度为n，则对于设置表头指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度为O(n); 对于设置表尾指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度同样为O(1)。另一方面，若要在表尾插入一个元素，前者需要O(n)，后者是O(1)，因而设置表尾指针的循环单链表好。 2． 3． 该图是：有向图 深度优先遍历序列：ABECFD 广度优先遍历序列：ABDECF 得分 五．算法阅读题 (本大题共 3 题，每题 4 分，共 12 分) 1. 2. 删除单链表L中p所指结点的直接前驱结点。 3．返回二叉树中p所指结点的双亲结点。 得分 六．算法填空题 (本大题共 2 题 9 空，每空 2 分，共 18 分) 1．⑴ (Q.rear+1)%Q.MaxSize==Q.front ⑵ i=Q.rear ⑶ Q.rear=(Q.rear+1)%Q.MaxSize 2．⑷ EdgeNode ⑸ EdgeNode ⑹ VNode ⑺ G.vertices[i].data==ch ⑻ p=G.vertices[i].firstarc; ⑼ p=p-next; 得分 七．算法设计题 (本大题共 2 题，每题 10 分，共 20 分) 1． void func(int *a,int n) { int i=0,j=n-1,temp; int k=a[0]; while(ij){ while(a[j]kij) j--; if(ij) { a[i]=a[j]; i++; } while(a[i]kij) i++; if(ij){ a[j]=a[i]; j--; } } a[i]=k; } 2． int DepthBTree(BTreeNode *BT) //求二叉树BT的深度 { if(BT=