完整word版,合肥学院期末考试卷及答案,推荐文档

命题教师命题教师胡春玲共一5页,第_1_页合肥学院2013至2014学年第2学期数据结构与算法设计 课程考试(A)卷系—级专业学号姓名题号一一二四五六七八九十总分得分阅卷一、选择题：(2分X15=30分) 大题得分.栈和队列的共同特点是(A.栈和队列的共同特点是(A)。A、只允许在端点处插入和删除元素C、都是先进先出 D、没有共同点.以下数据结构中哪一个是非线性结构？A、队列 B、栈.下面程序的时间复杂为(B)。for(i=1,s=0;i<=n;i++){t=1A、O(n)B、O(n2)C、O(n3)B、都是先进后出(D)C、线性表 D、二叉树;for(j=1;j<=i;j++)t=t*j;s=s+t;}D、O(n4)4.在一个单链表中，已知执行(B)0A.s->next=p->next;q结点是p结点的前趋结点，若在4.在一个单链表中，已知执行(B)0A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=p5.设一组初始记录关键字序列为C.p->next=s->next;s->next=p5.设一组初始记录关键字序列为(45,基准而得到一趟快速排序的结果是(45为80,55,40,42,85),则以第一个记录关键字C45为A、 40,42,45, 55, 80, 83 B、 42,40,45, 80, 85, 88C、42,40,45, 55, 80, 85 D、42,40,45, 85, 55, 80.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为(D)。A、O(log2n) B、O(1)C、O(n2)D、O(n).设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A、5 B、6 C、7 D、8.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A)。A、abedfcB、acfebdC、aebdfcD、aedfcb.设散列表长m=14，散列函数H(K)=K%11,已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7,其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是(D)。A、8 B、3 C、5 D、9.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为(B)。A、第i行非0元素的个数之和 B、第i歹I」非0元素的个数之和C、第i行0元素的个数之和D、第i列0元素的个数之和.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为(D)0

A、top=top+1B、top=top-1C、top->next=top;D、top=top->next.二叉树的第K层的结点数最多为（D）。A、2k-1 B、2K+1 C、2K-1+1 D、2k-1.设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向图G的一■种拓扑排序序列的是（A）。A、1,2,3,4B、2,3,4,1 C、 1,4,2,3D、1,2,4,3.设有一组初始记录关键字序列为(34,76,.设有一组初始记录关键字序列为(34,76,生成的二叉排序树的深度为(A)。A、4B、5C、6D、7.图的深度优先遍历类似于二叉树的(A)。A.先序遍历 B.中序遍历二、填空题：(2分X10=20分)1.设顺序线性表中有n个数据元素，则在第数据元素个数是 n-i+1 。45,18,26,54,92),则由这组记录关键字C.后序遍历 D.层次遍历大题得分i个位置上插入一个数据元素需要移动表中.设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则在p后进行插入操作的语句片列为(s->next=p->next;p->next=s)(设结点的指针域为next)o.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是122427351826。.设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是 A[i][j]=1。.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较 h次。.设一组初始记录关键字序列(k1,k2,……,kn)是小根堆,则对61,2,…，n/2而言满足的条件为_kiwk2i且kiWk2i+1(2i+1<n)。.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(_k<L->r[mid].key )high=mid-1;elselow=mid+1;}return（0）;}.若要对某二叉排序树进行遍历，保证输出所有结点的值序列有序排列，应对该二叉排序大题得分树采用中序遍历法。三、应用题：(5分X5=25分)1.设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。小题得分

共5页，第2共5页，第2页2.请画出下图的邻接矩阵和邻接表小题得分.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给小题得分出构造过程小题得分.设有无向图G,要求给出用普里姆算法构造最小生成树和所走过的边的集合。64

645、假设一棵二叉树的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,请画出该树小题得分共5页,第3页四、算法阅读题：(12分)1、四、算法阅读题：(12分)1、LinkListmynote(LinkListL)(7分){//L是不带头结点的单链表的头指针大题得分小题得分if(L&&L->next){S1:S2:S1:S2:while(p—>next)p=p—>next；p—>next=q；q—>next=NULL;}returnL;}请回答下列问题：(1)说明语句S1的功能。 查询链表的尾结点(2)说明语句组S2的功能。将第一个结点连接到链表的尾部，作为新的尾结点(3)设链表表示的线性表为(a1,a2,…,an),写出算法执行后的返回值所表示的线性表。返回的线性表为：(a2,a3,…an,a。小题得分2.voidABC(BTNode*BT) (5分){ifBT{ABC(BT->left