数据结构期末考试客观题及答案.docx

《数据结构期末考试客观题及答案.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试客观题及答案.docx（18页珍藏版）》请在优知文库上搜索。

1、一、单选题1、有序数组a18进行二分查找时，查找到a5的查找路径（下标序列）为A.8,2,5B.1,3,5C.8,3,5D.8,4,5正确答案：C2、对a12进行二分查找，在等概率情况下，查找成功的平均查找长度为。A.37/12B.43/12C.35/12D.39/12正确答案：A3、已知IaSt指向单向简单链表的尾结点，将S所指结点加在表尾，正确的操作是OA.s-next=s,last=s,last-next=NULL;B.s-next=NULL,last-net=s,s=last;C.last-next=s,s-next=NULLzlast=s;D.s-next=last,last-nex

2、t=NULLJast=S;正确答案：C4、在长度为n的有序链表中插入结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是OA.O(n)和O(logn)B.O(n)和0(1)CQ(Iogn)和0(n)D.O(n)和0(n)正确答案：D5、设进栈序列是1,2,3,，n,输出序列为pl,p2,p3,，pn0若pl=3,则p2为oA.可能是1B.不可能是2C必是1D.可能是2正确答案：D6、高度为h的正则二叉树至少有结点。A.2hB.2h-1C.2h+1D.2h+1正确答案：B7、正则二叉树的先序序列为ABCDE,后序序列为BDECA,则其中序序歹l是oA.DBCAEB.BADCEGABCEDD.

3、ABDCE正确答案：B8、若检索树中序序列是从小到大的序列，下列说法正确的是。A.检索树中，每个结点的关键字都比其右子树中所有结点关键字大或相等，比其左子树中所有结点关键字小B.检索树中，每个结点的关键字都不比其左孩子关键字大或相等，不比其右孩子关键字小C.检索树中，每个结点的关键字都比其左孩子关键字大或相等，比其右孩子关键字小D.检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小正确答案：D9、如图所示检索树，其成功平均查找长度为一。A.2.9B.2.5C.3.2D.2.7正确答案：A10、具有5层结点的AVL树至少有个结点。A.17B.13C.12

4、D.15正确答案：C11、将结点13,24,37,90,53插入开始为空的平衡树，其先序遍历序列为A.24,13, 53, 37, 90B.13,24,37,90,53C.24,13, 37, 90, 53D.13,37,24,90,53正确答案：A12、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。A.25B.12C.26D.13正确答案：A13、排序的时间复杂度不受数据初始状态影响而恒为O(Mogn)的是()oA.快速排序B,冒泡排序C.希尔排序D.堆排序正确答案：D14、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()oA.冒泡排序B.希尔排序C,快速排序D.

5、堆排序正确答案：B15、执行一趟快速排序能够得到的序列是()oA.12,27,45,415534,63,72B.41,12,34,45,275572,63C.45,34,12,415572,63,27D.63,12,34,45,2刀5541,72正确答案：B16、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()oA.O(nlogn)B.O(Iogn)C.O(n2)D.O(n)正确答案：C17、设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序排序的第一趟冒泡排序结束后的结果是()oA.H,C,Q,P,A,M,S,R,D,F,X,YB.F,H,

6、C,D,P,A,M,Q,R,S,Y,XC.A,D,C,R,F,Q,M,S,Y,P,H,XD.P,A,C,S,Q,D,F,X,R,H,M,Y正确答案：A18、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()0A.改进的冒泡排序B,直接插入排序C.快速排序D.简单选择排序正确答案：D19、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是()oA.简单选择排序B.直接插入排序C,快速排序D.堆排序正确答案：C20、以下代码的复杂度是()ox=0;for(i=l;in;i+)for(j=jnext=NULLB.p=LC.p-net=LD.p=NU

7、LL正确答案：C26、设有两个长度为n的单链表，结点类型相同，若以hl为首结点的链表是非循环的，以h2为首结点指针的链表是循环的，则OA.循环链表要比非循环链表占用更多的内存空间B.hl和h2是不同类型的变量C,对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是0(n)D.对于两个链表来说，删除第一个结点的操作，其时间复杂度都是0(1)正确答案：C27、用二分法对数组a13进行查找，若待查元素为X介于a7-a8之间，那么查找路径为(用下标序列表示)。A.6,10,7,8B.6,9,8,7C.6,9,7D.6,9,7,8正确答案：D28、将如图所示的单向链表中A段和B段交换位置（将B段调

8、到A段的前面，其余结点次序不变），正确的程序段为。A段B收A.t=q-next;q-next=r-next;r-next=q;p-next=t;B.q-net=r-next;r-next=p-next;p-next=q-next;C.p-next=q-next;q-next=r-next;r-next=p-next;D.t=q-next;q-next=r-next;r-next=p-next;p-net=t;正确答案：D29、带头结点的单链表L为空的判定条件是一。A.L-next=NULLB.L-net=LCLl=NULLDl=NULL正确答案：A30、设进栈序列是1,2,3,n,输出序列为p

9、l,p2,p3,pn0若p3=l,则pl为。A.不可能是3B.必是2C.必定是3D.可能是3正确答案：D31、用二分法对数组a13进行查找，在等概率的情况下，查找不成功的平均查找长度为。A.27/7B.48/13C.49/14D.54/13正确答案：A32、高为h的m元树(m2,hl)中结点总数n。A.mh+1-1B. mh+1-1C. (mh一l)(m-1)D. mh(m-1)正确答案：C33、若k元正则树中共有m个非叶结点，则叶子数。A=(k-l)m+lB=(k-l)m-lC.kmD.(k-l)m正确答案：A34、已知二叉树的先序序列是15,5,3,10,8,18,24；后序序列是3,8,

10、10,5,24,18,15；树中共有三片叶（3,8,24）,而根结点和另外一个结点的度数为2o其余结点度数为Io请问结点24的父亲结点是。A.18B.10C.5D.3正确答案：A35、依次插入20,8,17,25,30,18来构造开始为空的平衡二叉树,则此平衡二叉树的后序遍历序列为：A.8, 17, 20,18, 25, 30B.8, 17, 18,C.20, 17, 8,D.20, 8, 17,30, 25, 2025, 18, 3025, 30, 18正确答案：B36、在待排序的元素序列基本有序的前提下，效率最高的排序方法是A.快速排序B.插入排序C.归并排序D.选择排序正确答案：D37、

11、用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序时，元素序列的变化情况如下：(1) 25,84,21,47,15,27,68,35,20(2) 20,15,21,25,47,27,68,35,84(3) 15,20,21,25,35,27,47,68,84(4) 15,20,21,25,27,35,47,68,84则采用的排序方法是，A.堆排序B,冒泡排序C.直接插入排序D.希尔排序正确答案：A38、稳定的排序方法是OA.直接插入排序B.快速排序C.堆排序D.简单选择排序正确答案：A39、一个有n个顶点的无向图最多有条边。A.n(n-1)B.nC.n(n-1)

12、2D.2n正确答案：C40、已知一个图如图所示，若从顶点a出发按广度搜索法进行遍历,则可能得到的一种顶点序列为。A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,c,f,d,e,bD.a,e,b,c,f,d正确答案：B41、使用普里姆算法构造出如图所示的图G的一棵最小生成树，从顶点1出发依次得到的最小生成树的序列为。A.(l,3)1,(3,6)4,(6,4)2,(3,2)5,(2,5)3B.(l,3)1,(6,4)2,(2,5)3,(3,6)4,(3,2)5C(1,3)1,(3,6)4,(3,2)5,(6,4)2,(2,5)3D.(l,3)1,(3,2)5,(2,5)3,(3,6)4,(6,4)2正确答案：A42、具有n个顶点，m条边的无向图，其邻接表中，共有n个顶点结点和个边结点。A.mB.m/2C.2mD.n+m正确答案：C43、下面叙述正确的是。A.算法的空间复杂度是指算法程序中指令(或语句)的条数B.以上三种描述都不对C.算法的有穷性是指算法必须能在执行有限个步骤