西北工业大学21秋《数据结构》综合测试题库答案参考94

《西北工业大学21秋《数据结构》综合测试题库答案参考94》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》综合测试题库答案参考94（13页珍藏版）》请在装配图网上搜索。

1、西北工业大学21秋数据结构综合测试题库答案参考1. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B2. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A3. 空格串的长度是空格的个数。( )A、错误B、正确参考答案：B4. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B5.

2、最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A6. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )A.正确B.错误参考答案：A7. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D8. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C9. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B10. 对于双向链表，在两

3、个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B11. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )。A.栈B.队列C.树D.图参考答案：C12. 下列序列中，不构成堆的是( )。A.(1，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)参考答案：D13. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2

4、D.n2-1参考答案：A14. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A15. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B17. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D18. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。

5、( )A、错误B、正确参考答案：B19. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A20. 在队列中，允许进行插入操作的一端称为队头。( )A、错误B、正确参考答案：B21. 一组记录的关键字经一趟二路归并排序后得到含有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，48，23，40，79，82，72，36C.16，25，48，35，79

6、，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82参考答案：D22. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B23. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A24. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C25. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A26. 含n个顶点的无

7、向连通图中至少含有n条边。( )A、错误B、正确参考答案：A27. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A28. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A29. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A30. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D31. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：

8、D32. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C33. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A34. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A35. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free

9、(p-next)D.p=p-next-next; free(p-next)参考答案：A36. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A37. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B38. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B39. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.

10、15参考答案：A40. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A41. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A42. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A43. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D44. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入

11、B、删除C、排序D、定位参考答案：D45. 将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数组B中的位置K为( )。A.199B.197C.195D.193参考答案：C46. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A47. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C48. 二叉树是度为2的有序树。( )A、错误B、正确参考答案：A49. 广义表中的元素或者是一个不可分割的

12、原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B50. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A51. 由树转化成二叉树，其根节点的右子树总是空。( )A.正确B.错误参考答案：A52. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C53. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A54. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A55. 任何有向网的拓扑排序的结果是唯一的。( )A.正确B.错误参考答案：B56. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B57. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B58. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A59. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A60. 数据的不可分割的最小标识单位是( )。A.数据项B.数据记录C.数据元素D.数据变量参考答案：A