数据结构期末考试客观题及答案.docx
一、单选题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->ne×t=s,s=last;C.last->next=s,s->next=NULLzlast=s;D.s->next=last,last->next=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.ABDCE正确答案：B8、若检索树中序序列是从小到大的序列，下列说法正确的是。A.检索树中，每个结点的关键字都比其右子树中所有结点关键字大或相等，比其左子树中所有结点关键字小B.检索树中，每个结点的关键字都不比其左孩子关键字大或相等，不比其右孩子关键字小C.检索树中，每个结点的关键字都比其左孩子关键字大或相等，比其右孩子关键字小D.检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小正确答案：D9、如图所示检索树，其成功平均查找长度为一。A.2.9B.2.5C.3.2D.2.7正确答案：A10、具有5层结点的AVL树至少有个结点。A.17B.13C.12D.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.堆排序正确答案：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,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;i<n;i+)for(j=j<n;j+)x+;A.O(logn)B.O(nlogn)C.O(n)D.O(n*n)正确答案：D21、以下说法错误的是。A.装填因子是散列法的一个重要参数，它反映了散列表的装填程度B.散列表的结点中只包含数据元素自身的信息，不包含任何指针C.散列存储的基本思想是由元素值决定其存储地址D.散列表的查找效率主要取决于的散列函数和处理冲突的方法正确答案：B22、设散列表长m=14,散列函数HaSh(X)=XmOdl1。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。若用平方探测法di=i*i处理冲突,插入元素49时,其地址是。A.5B.9C.8D.3正确答案：B23、在有向图中，所有顶点的入度之和等于所有顶点的出度之和的一倍。A.1B.2C.4D.3正确答案：A24、对于下图所存储的有向图，从顶点A开始进行先广搜索，不能得到的顶点序列是OB.ACBDEC.ADCEBD.ABCDE正确答案：C25、非空的循环单链表L的尾结点(由P所指向)满足。A.p->next=NULLB.p=LC.p->ne×t=LD.p=NULL正确答案：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段调到A段的前面，其余结点次序不变），正确的程序段为。A段B收A.t=q->next;q->next=r->next;r->next=q;p->next=t;B.q->ne×t=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->ne×t=t;正确答案：D29、带头结点的单链表L为空的判定条件是一。A.L->next=NULLB.L->ne×t=LCLl=NULLDl=NULL正确答案：A30、设进栈序列是1,2,3,n,输出序列为pl,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元树(m»2,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,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、用某种排序方法对线性表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)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.算法的有穷性是指算法必须能在执行有限个步骤
