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

《A-2013-2014第2学期数据结构期末考卷答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………………………………………………………..装………………….订…………………..线………………………………………………………诚信应考考出水平考出风格浙江大学城市学院2013—2014学年第2学期期末考试答题卷《数据结构》开课单位：计算分院；考试形式：闭卷；考试时间：2014年06月29日；所需时间：120分钟题序一二三四五六七总分得分评卷人注：

2、试卷答案必须写在答卷上，写在试卷上不得分。得分一．判断题(有5条是正确的，将正确的编号写在答卷上，每空1分，共5分)请把正确编号填入下表内。15789得分二．选择题(本大题共15题，每题1分，共15分)请把正确选项填入相应的题号内。123456789101112131415ABDDBDDACCCCCBB得分三．填空题(本大题共6题15空，每空1分，共15分)1．⑴数据元素的集合⑵关系的集合2．⑶n/2⑷(n-1)/2⑸O(n2)3．⑹2⑺14．⑻I⑼F⑽D5．⑾abdecf⑿16．⒀3⒁4⒂2得分四．解答题(本大题共3题，每题5分，共15分)1

3、．设置表尾指针的循环单链表好。假设循环单链表长度为n，则对于设置表头指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度为O(n);对于设置表尾指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度同样为O(1)。另一方面，若要在表尾插入一个元素，前者需要O(n)，后者是O(1)，因而设置表尾指针的循环单链表好。2．ABDCEHFGIJ3．⑴该图是：有向图⑵深度优先遍历序列：ABECFD⑶广度优先遍历序列：ABDECF得分五．算法阅读题(本大题共3题，每题4分，共12分)12233344445555

4、51.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.MaxSize2．⑷EdgeNode⑸EdgeNode⑹VNode⑺G.vertices[i].data==ch⑻p=G.vertices[i].firstarc;⑼p=p->next;得分七．算法设计题(本大题共2题，每题10分，共20分)1．voidfunc(int*a,i

5、ntn){inti=0,j=n-1,temp;intk=a[0];while(ik&&ileft);intdep2=DepthBTree(BT->right)

6、;if(dep1>dep2)returndep1+1;elsereturndep2+1;}}