《西北工业大学21秋《数据结构》综合测试题库答案参考38》由会员分享,可在线阅读,更多相关《西北工业大学21秋《数据结构》综合测试题库答案参考38(13页珍藏版)》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构综合测试题库答案参考1. 在下列各种文件中,不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案:C2. 如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案:B3. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案:D4. 在文本编辑程序中查找某一特定单词在文本中出现的位置,可以利用串的定位操作。(
2、 )A、错误B、正确参考答案:B5. 广义表(a,b,c,d)的表头是( )。A.(b,c,d)B.(a,b,c,d)C.aD.(a)参考答案:B6. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案:B7. 散列函数有一个共同的性质,即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案:D8. 在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答
3、案:C9. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案:ABCD10. 已知指针p指向某单链表中的一个结点,则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案:B11. 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t),则在二分查找关键字b的过程中,先后进行比较的关键字依次为( )。A.f,c,bB.f,d,bC.g,c,bD.g,d,b参考答案:A12. 在一个长度为n的循环链表中,删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案:B13. 某二叉
4、树的前序和后序序列正好相同,则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案:A14. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案:A15. 一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下:25,48,16,35,79,82,23,40,36,72,在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为( )A.16,25,35,48,23,40,79,82,36,72B.16,25,35,4
5、8,23,40,79,82,72,36C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82参考答案:D16. 任何一个无向连通图的最小生成树( )。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案:B17. 由于希尔排序的最后一趟与直接插入排序过程相同,因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案:A18. 链式队列Q为空的判定条件:( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案:A19. 有向图用邻接矩阵表示后,顶点i的入度等于邻接矩
6、阵中第i列的元素个数。( )A、错误B、正确参考答案:B20. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案:A21. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案:A22. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案:A23. 若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案:B24. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考
7、答案:A25. 在图G的最小生成树T中,可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案:A26. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案:A27. 快速排序是排序算法中平均性能最好的一种排序。( )A.正确B.错误参考答案:A28. 对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。( )A、错误B、正确参考答案:B29. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案:B30. 已知循环队列的存储空间为数组data21,且当前队列的头指针和尾指针的值分别为8和3,则该队列的当前长度为(
8、 )。A.5B.6C.16D.17参考答案:C31. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案:D32. 后序线索二叉树是不完善的,要对它进行遍历,还需要使用栈。( )A.正确B.错误参考答案:A33. 若一棵满三叉树中含有121个结点,则该树的深度为6。( )A、错误B、正确参考答案:A34. 已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列。对这些
9、子序列进行一趟两两归并的结果是( )。A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,82参考答案:D35. 设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案:A36. 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案:A
10、37. 由于排序过程中涉及的存储器不同,可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案:CD38. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY,则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案:A39. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案:A40. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误
11、参考答案:A41. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案:B42. 用链接方式存储的队列,在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改参考答案:D43. 下面程序段的时间复杂度是( )。for(i=0; in; i+) for(j=1; jm; j+) Aij=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)参考答案:D44. 若用n表示图中顶点数目,则有( )条边的无向图成为完全图。A.nB.n-1C.n(n
12、-1)2D.n(n+1)2参考答案:C45. 已知完全二叉树T的第5层只有7个结点,则该树共有15个叶子结点。( )A、错误B、正确参考答案:A46. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案:A47. 右图中的拓扑序列为( )A.C1,C2,C6,C7,C5,C4,C3B.C1,C2,C6,C3,C4,C5,C7C.C1,C4,C2,C3,C5,C6,C7D.C5,C7,C4,C1,C2,C6,C3参考答案:D48. 一个栈的入栈序列是abcde,则栈的不可能的输出序列是
13、( )。A.edcbaB.decbaC.dceabD.abcde参考答案:C49. 若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案:A50. 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案:A51. 设串s1=Data Structures with Java,s2=it,则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案:D52. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案:A53. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树,并且有左右之分参考答案:D54. 对长度为n的关键字序列进行堆排序的空间复杂度为(