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

答卷纸第页共4页1诚信应考考出水平考出风格浙江大学城市学院2013—2014学年第2学期期末考试答题卷《数据结构》开课单位：计算分院；考试形式：闭卷；考试时间：2014年06月29日；所需时间：120分钟题序一二三四五六七总分得分评卷人注：试卷答案必须写在答卷上，写在试卷上不得分。一．判断题(有5条是正确的，将正确的编号写在答卷上，每空1分，共5分)请把正确编号填入下表内。15789二．选择题(本大题共15题，每题1分，共15分)请把正确选项填入相应的题号内。123456789101112131415ABDDBDDACCCCCBB三．填空题(本大题共6题15空，每空1分，共15分)1．⑴数据元素的集合⑵关系的集合2．⑶n/2⑷(n-1)/2⑸O(n2)得分得分得分年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………………………………………………………..装………………….订…………………..线………………………………………………………答卷纸第页共4页23．⑹2⑺14．⑻I⑼F⑽D5．⑾abdecf⑿16．⒀3⒁4⒂2四．解答题(本大题共3题，每题5分，共15分)1．设置表尾指针的循环单链表好。假设循环单链表长度为n，则对于设置表头指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度为O(n);对于设置表尾指针的表来说，其访问首元结点的时间复杂度为O(1)，访问表尾结点的时间复杂度同样为O(1)。另一方面，若要在表尾插入一个元素，前者需要O(n)，后者是O(1)，因而设置表尾指针的循环单链表好。2．ABEJFCDHIG得分ABDCEHFGIJ答卷纸第页共4页33．⑴该图是：有向图⑵深度优先遍历序列：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.MaxSize2．⑷EdgeNode⑸EdgeNode⑹VNode⑺G.vertices[i].data==ch⑻p=G.vertices[i].firstarc;⑼p=p-next;得分得分122333444455555答卷纸第页共4页4七．算法设计题(本大题共2题，每题10分，共20分)1．voidfunc(int*a,intn){inti=0,j=n-1,temp;intk=a[0];while(ij){while(a[j]k&&ij)j--;if(ij){a[i]=a[j];i++;}while(a[i]k&&ij)i++;if(ij){a[j]=a[i];j--;}}a[i]=k;}2．intDepthBTree(BTreeNode*BT)//求二叉树BT的深度{if(BT==NULL)return0;//空树深度为0else{intdep1=DepthBTree(BT-left);intdep2=DepthBTree(BT-right);if(dep1dep2)returndep1+1;elsereturndep2+1;}}得分