数据结构习题

《数据结构习题》由会员分享，可在线阅读，更多相关《数据结构习题（46页珍藏版）》请在装配图网上搜索。

1、数据结构习题一、 单选题1. 研究数据结构就是研究 A) 数据的逻辑结构B) 数据的逻辑结构和存储结构C) 数据的存储结构D) 数据的逻辑结构、存储结构及其数据在运算上的实现2. 下面关于算法的说法，错误的是 。 A) 算法最终必须由计算机程序实现B) 为解决某问题的算法与为该问题编写的程序含义是相同的C) 算法的可行性是指指令不能有二义性D) 以上几个都是错误的3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出 5个特性。可执行性、可移植性和可扩充性可执行性、有穷性和确定性确定性、有穷性和稳定性易读性、稳定性和确定性4. 以下属于逻辑结构的概念是 。A) 顺序表B)

2、 哈希表C) 有序表 D) 单链表5. 具有线性结构的数据结构是 。A) 图B) 树 C) 广义表D) 栈6. 数据的存储结构包括顺序、链接、散列和 种基本类型。A) 向量B) 数组C) 集合D) 索引7. 关于逻辑结构，以下说法错误的是 。A) 逻辑结构与数据元素本身的形式、内容无关B) 逻辑结构与数据元素的相对位置有关C) 逻辑结构与所含结点个数无关D) 一些表面上很不相同的数据可以有相同的逻辑结构 8. 根椐数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据组织形式。下列解释错误的是 。A) 集合中任何两个结点之间都有逻辑关系，但组织形式松散B) 线性结构中结点按逻辑关系

3、依次存储成一行C) 树型结构具有分支、层次特性，其形态有点像自然界中的树D) 图状结构中各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接9. 在数据结构中，从逻辑上可以把数据结构分成 。A) 动态结构和静态结构B) 紧凑结构和非紧凑结构C) 线性结构和非线性结构D) 内部结构和外部结构10. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 。A) 存储结构B) 存储实现C) 逻辑结构D) 运算实现11. 以下说法正确的是 。A) 数据元素是数据的最小单位B) 数据项是数据的基本单位C) 数据结构是带有结构的各数据项的集合而且对应数据项的类型要一致D) 一些表面上很不相同的数据可以有

4、相同的逻辑结构12. 以下说法错误的是 。A) 程序设计的实质是算法设计B) 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C) 运算实现是完成运算功能的算法或这些算法的设计D) 算法设计总是与数据的某种相应存储形式相联系13. 下列叙述中有关好的编程风格的正确描述是 A) 程序中的注释是可有可无的B) 对递归定义的数据结构不要使用递归过程C) 过程应是自封闭的，尽量少使用全程变量D) 多采用一些技巧以提高程序的运行效率14. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 存储方式最节省运算时间。 A) 单链表B) 仅有头指针的单循环链表C)

5、 双链表D) 仅有尾指针的单循环链表15. 单链表的主要优点是 。A) 便于随机查询B) 存储密度高C) 逻辑上相邻的元素在物理上也是相邻的D) 插入和删除比较方便16. 对一个具有n个元素的线性表，建立其单链表的时间复杂度为 。 A) O(n)B) O(1)C) O(n2)D) O(log2n)17. 线性表采用链式存储时，其地址 。A) 必须连续B) 一定不连续 C) 部分连续D) 连续与否均可18. 对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该 。A) 以顺序方式存储B) 以链接方式存储C) 以散列方式存储D) 以上均可19. 循环

6、链表的主要优点是 。A) 不再需要头指针B) 已知某结点位置后能容易找到其直接前趋C) 在进行插入、删除运算时能保证链表不断开D) 从表中任一结点出发都能扫描整个链表20. 若一线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 存储方式最节省时间。A) 顺序表B) 单链表C) 双链表D) 单循环链表21. 若用单链表来表示队列，则应该选用 。 A) 带尾指针的非循环链表B) 带尾指针的循环链表C) 带头指针的非循环链表D) 带头指针的循环链表22. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。从队列中出队一个元素，再进队两个元素后，rear

7、和front的值分别为 A) 1和5B) 2和4C) 4和2D) 5和123. 设栈的输入序列是(1、2、3，4)，则 不可能输出的序列。A) 1243B) 2134C) 1432D) 431224. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是 。A) 6 B) 4 C) 3D) 225. 一般情况下，将递归算法转换成等价的非递增归算法应该设置 。A) 堆栈B) 队列C) 堆栈或队列D) 数组26. 算术表达式的中缀形式为A+B*C-DE，后缀形式

8、为ABC*+DE-，其前缀形式为 。A) -A+B*CDEB) -A+B*CDEC) -+*ABCDED) -+A*BCDE27. 设栈的输入序列是1、2、n，若输出序列的第一个元素是n，则第i个输出元素 。A) 不确定B) n-i+lC) cD) n-i28. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是 。A) front+1=rearB) front=rear+1C) front=OD) front=rear29. 假定一个顺序循环队列存储于数组an中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是 。A) (rear-1)n=

9、frontB) rear=(front-1)nC) (rear+1)n=frontD) rear=(front+1)n30. 一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。A) 23415B) 54132C) 23145D) 1543231. 若一个栈的输入序列是1、2、3、n，输出序列的第一个元素是i，则第i个输出元素是 。A) i-j-1B) i-jC) j-i+lD) 不确定的32. 用单链表表示的链式队列的队头在链表的 位置A) 链头B) 链尾C) 链中D) 不确定的33. 设计一个判别表达式中左、右括号是否配对出现的算法，采用 数据结构最佳。A) 线性表的顺序

10、存储结构B) 队列C) 线性表的链式存储结构D) 栈34. 在下列算法描述中，涉及到队运算的算法是 。A) 表达式求值算法B) 深度优先搜索C) 二叉树前中后序遍历D) 广度优先搜索35. 栈的插入和删除操作在 进行。A) 栈顶B) 栈底C) 任意位置D) 指定位置36. 在一个顺序循环队列中，队首指针指向队首元素的 位置。A) 前一个B) 后一个C) 当前D) 最后37. 当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为 。A) N-2B) N-1C) ND) N+l38. 如果以链表作为栈的存储结构，则退栈操作时 。A) 必须判别栈是否满B) 判别栈元素的类型C) 必须判别栈是否

11、空D) 对栈不作任何判别39. 链栈与顺序栈相比有一个明显的优点，即 。A) 插入操作更加方便B) 通常不会出现栈满的情况C) 不会出现栈空的情况D) 删除操作更加方便40. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 。A) 所有的结点均无左孩子B) 所有的结点均无右孩子C) 只有一个叶子结点D) 是任意一棵二叉树41. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 。A) 250B) 500C) 505 D) 50142. 以下说法正确的是 。A) 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序 列中的最后一个结点B) 若

12、一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C) 在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有 一个子女结点D) 在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点43. 以下说法错误的是 。A) 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍 历序列中的第一个结点C) 己知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个D) 在前序遍历二叉树的序列中，任何结点其子树的所有结点

13、都是直接跟在该结点之后的44. 二叉树在线索化后，仍不能有效求解的问题是 。A) 前序线索二叉树中求前序后继B) 中序线索二叉树中求中序后继C) 中序线索二叉树中求中序前趋D) 后序线索二叉树中求后序后继45. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 遍历方法最合适。A) 前序B) 中序C) 后序D) 层次46. 一棵有124个叶结点的完全叉树，最多有 个结点。A) 247B) 248C) 249D) 25047. 设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是 A) a在b的右方B) a在b的左方C) a是b的祖先D) a是b的子孙48.

14、 在一棵具有n个结点的完全二叉树中，分枝结点的最大编号为 。A) (n+1)2)下限取整B) (n-1)2) 下限取整C) (n2) 下限取整D) (n2) 上限取整49. 在N个结点的线索二叉树中，线索的数目为 。A) N-1B) NC) N+1D) 2N50. 设深度为K的二叉树上只有度为0和2的结点，则这类二叉树上所含的结点总数至少为 。A) K+1B) 2KC) 2K-1D) 2K+151. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为 。A) n-1B) (n/m)-1C) (（n-1）*（m+1）)上限取整D) 前三者均不对52. 设有13个值，用它们组成一棵哈夫曼树

15、，则该哈夫曼树共有 个结点。A) 13B) 12C) 26D) 2553. 以下说法错误的是 。A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B) 二叉树是树的特殊情形C) 由树转换成二叉树，其根结点的右子树总是空的D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树54. 如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的 。A) 先序B) 中序C) 后序D) 层次序55. 若一个具有N个顶点，K条边的无向图是一个森林(NK)，则该森林中必有 棵树。A) KB) NC) N-KD) 156. 设F是一森林，B是由F变换得到的二叉树。若

16、F中有n个非终端结点，则B中右指针域为空的结点有 个。A) n-1B) nC) n+1D) n+257. 若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 。A) 二叉排序树B) 哈夫曼树C) 堆D) 退化二叉树58. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A1n)中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是 。 A) A2i (2inB) A2i+1) (2i+1n)C) Ai/2D) 条件不充分，无法确定59. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是 。A

17、) 4B) 5C) 6D) 760. 设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为 。A) 5B) 6C) 7D) 861. 下列有关二叉树的说法正确的是 。A) 二叉树的度为2B) 一棵二叉树度可以小于2C) 二叉树中至少有一个结点的度为2D) 二叉树中任一个结点的度都为262. 某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是 。，A) EGFACDBB) EACBDGFC) EAGCFBDD) 上面的都不对63. 设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是 。

18、 A) m-nB) m-n=1C) n+1D) 无法确定64. 对二叉排序树进行 遍历，可以得到该二叉树所有结点构成的排序序列A) 前序B) 中序C) 后序D) 按层次65. 的遍历仍需要栈的支持。A) 前序线索树B) 中序线索树C) 后序线索树D) 层次遍历66. 在一棵度为3的树中，度为3的结点数为2个，度为2结点数为1个，度为1结点数为2个,则度为0的结点数为 个。A) 4B) 5C) 6D) 767. 在一棵具有k层的满三叉树中，结点总数为 。A) (3k-1)2B) 3k-1C) (3k-1)3D) 3k68. 在一棵深度为h的完全二叉树中，所含结点的个数不小于 。A) 2hB) 2

19、h+1C) 2h-1D) 2h-169. 在一棵具有n个结点的二叉树第i层上，最多具有 个结点。A) 2iB) 2i+1C) 2i-1D) 2n70. 在下列情况中，可称为二叉树的是 。A) 每个结点至多有两棵子树的树B) 哈夫曼树C) 每个结点至多有两棵子树的有序树D) 每个结点只有一棵右子树71. 树最适合用来表示 。A) 有序数据元素B) 无序数据元素C) 元素之间具有分支层次关系的数据D) 元素之间无联系的数据72. 以下说法错误的是 。A) 一般在哈夫曼树中，权值越大的叶子离根结点越近B) 哈大曼树中没有度数为1的分支结点C) 若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n

20、-1个结点D) 若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树73. 以下说法错误的是 。A) 二叉树可以是空集B) 二叉树的任一结点都可以有两棵子树C) 二叉树与树具有相同的树形结构D) 二叉树中任一结点的两棵子树有次序之分74. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是 的二叉树。A) 空或只有一个结点B) 任一结点无左子树C) 高度等于其结点数D) 任一结点无右子树75. 设无向图的顶点个数为n，则该无向图最多有 条边。A) n-1B) n(n-1)/2C) n(n+1)/2D) 0E) n276. 用DFS遍历个无环有向图，并在DFS算法退栈返回时

21、打印出相应的顶点，则输出的顶点序列是 。A) 逆拓扑有序的B) 拓扑有序的C) 无序的77. 采用邻接表存储的图，其深度优先遍历类似于二叉树的。A) 中序遍历B) 先序遍历C) 后序遍历D) 按层次遍历78. 采用邻接表存储的图，其广度优先遍历类似于二叉树的。A) 按层次遍历B) 中序遍历C) 后序遍历D) 先序遍历 ，79. 一个图中包含有七个连通分量，若按深度优先(DFS)搜索方法访问所有结点,必须调用 次深度优先遍历算法。A) kB) 1C) k-1D) k+180. 设有无向图G (V，E)和G（V，E），如G是G的生成树，则下面不正确的说法是。A) G为G的连通分量B) G是G的无环

22、子图C) G为G的子图D) G为G的极小连通子图且V=V81. 下列说法中不正确的是A) 无向图中的极大连通子图称为连通分量B) 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D) 有向图的遍历不可采用广度优先搜索方法 82. 具有n个顶点的有向图最多有 条边。A) nB) n(n-1)C) n(n+1)D) n283. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是 。A) G中有弧B) G中有一条从Vi到Vj的路径C) G中没有弧 D) G中有一条从Vj到Vi的路径84. 一个n个顶点的连通无向

23、图，其边的个数至少为。A) n-1B) n C) n+lD) nlog2n85. 下列说法中，正确的有。A) 最小生成树也是哈夫曼树。B) 最小生成树惟一C) 普里姆(Prim)最小生成树算法时间复杂度为O(n2)D) 克鲁斯卡尔(Kruskal)最小生成树算法比普里姆算法更适合于边稠密的网86. 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用 。A) 求关键路径的方法B) 求最短路径的Dijkstra方法C) 深度优先遍历算法D) 广度优先遍历算法87. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为。A) sB) s-1C) s+lD)

24、 n88. 在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为。A) kB) k+lC) k+2D) 2k89. 一个有n个顶点的无向连通图，它所包含的连通分量个数为 。A) 0B) 1C) nD) n+190. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为。A) klB) k2C) k1-k2D) k1+k291. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为。A) klB) k2C) k1-k2D) k1+k292. 对于一个无向图，下面的说法是正确的。A) 每个顶点的入度等于出度

25、B) 每个顶点的度等于其入度与出度之和C) 每个顶点的入度为0 D) 每个顶点的出度为093. 为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用。A) 顺序存储B) 链式存储C) 索引存储D) 散列存储94. 散列函数有一个共同的性质，即函数值应当以 取其值域的每个值。A) 最大概率B) 最小概率C) 平均概率D) 同等概率95. 设有一个按各元素的值排好序的线性表且长度大于2，对给定的值X，分别用顺序查找法和二分查找法查找一个与K相等的元素，比较次数分别是s和b：在查找不成功的情况下，正确的s和b的数量关系是。A) 总有s=bB) 总有sbC) 总有sbD) 与K值大小有关9

26、6. 下面关于B-树和B+树的叙述中，不正确的结论是一。A) B-树和B+树都能有效地支持顺序查找B) B-树和B+树都能有效地支持随机查找C) B-树和B+树都是平衡的多分树D) B-树和B+树都可用于文件索引结构97. 关于杂凑查找说法不正确的有个。A) 采用链地址法解决冲突时，查找一个元素的时间是相同的B) 采用链地址法解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的C) 采用链地址法解决冲突易引起聚集现象D) 再哈希法不易产生聚集98. 对有18个元素的有序表作二分(折半)查找，则查找A3的比较序列的下标为A) 2、 3 B) 5、 2、 3C) 5、 3D) 4、 2

27、、 399. 若在线性表中采用折半查找法查找元素，该线性表应该。A) 元素按值有序B) 采用顺序存储结构C) 元素按值有序，且采用顺序存储结构D) 元素按值有序，且采用链式存储结构100. 一棵深度为K的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有个结点。A) 2k-1-1 B) 2k-1C) 2k-1+1D) 2K-1E) 2kF) 2k+1101. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行 次探测。A) k-1次B) k次C) k+1次D) k(k+1)2次102. 具有5层结点的AVL树至少有个结点。A) 10B) 12C) 15D)

28、17103. 设散列地址空间0m-1，k为关键字，用p去除k，将余数作为k的散列地址 (h(k)=k%p)，为了减少发生冲突的可能性，一般取P为。A) 小于m的最大奇数B) 小于m的最大素数C) 小于m的最大偶数D) 小于m的最大合数104. 设散列表的长m=14，散列函数为h(k)=k%11，表中已有4个记录(如图所示)如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是。0 1 2 3 4 5 6 7 8 9 10 11 12 1315386184 图 散列表A) 8B) 3C) 5D) 9105. 从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂性 。A) O

29、(n)B) O(1)C) O(log2n)D) O(n2)106. 在采用线性探测法处理冲突的闭散列表上，假定装填因子a的值为05，则查找任一元素的平均查找长度为。A) 1B) 1.5 C) 2D) 2.5107. 在采用链接法处理冲突的开散列表上，假定装填因子a的值为4，则查找任一元素的平均查找长度为。A) 3B) 3.5C) 4D) 2.5108. 下面关于二叉排序树论述中，错误的是。A) 当所有结点的权值都相等时，用这些结点构造的二叉排序树除根结点外只有右子树B) 中序遍历二叉排序树的结点就可以得到排好序的结点序列C) 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的

30、平均查找时间D) 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列是一样的109. 以下说法错误的是。A) 散列法存储的基本思想是由关键码值决定数据的存储地址B) 散列表的结点中只包含数据元素自身的信息，不包含任何指针C) 装填因子是散列法的一个重要参数，它反映了散列表的装填程度D) 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法110. 设有一个用线性探测法解决冲突得到的散列表如图所示0 1 2 3 4 5 6 7 8 9 101325801617614 图 散列表散列函数为H=11，若要查找元素14，探测的次数是A) 8B) 9C) 3D) 611

31、1. 散列表的平均查找长度。A) 与处理冲突方法有关而与表的长度无关B) 与处理冲突方法无关而与表的长度有关C) 与处理冲突方法有关且与表的长度有关D) 与处理冲突方法无关且与表的长度无关112. 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值。A) 一定都是同义词B) 一定都不是同义词C) 都相同D) 不一定都是同义词113. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是。A) 分块查找B) 顺序查找C) 折半查找D) 基于属性查找114. 有数据53，30，37，12，45，24，96，

32、从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入。A) 45,24,53，12,37,96,30B) 37,24,12,30,53,45,96C) 12,24,30,37,45,53,96D) 30,24,12,37,45,96,53115. 利用逐点插入法建立序列50，72，43，85，75，20，35，45，65，30对应的二叉排序树以后，查找元素35要进行元素间的比较A) 4次B) 5次C) 7次D) 10次116. 在非空m阶B-树上，除根结点以外的所有其他非终端结点。A) 至少有m/2下限取整棵子树B) 至多有m/2下限取整棵子树C) 至少有m/2

33、上限取整棵子树D) 至多有m/2上限取整棵子树117. 在顺序表(n足够大)中进行顺序查找，其查找不成功的平均长度是A) (n+1)2B) n2+lC) n D) n+l118. 采用二分检索方法检索长度为n的有序表，检索每个元素时的平均比较次数与对应的判定树高度(设高度2)相比较为 。A) 小于B) 大于C) 等于D) 大于等于119. 对线性表进行二分检索时，要求线性表必须 。A) 以顺序存储方式存储B) 以链式存储方式存储C) 以顺序存储方式存储且数据有序D) 以链式存储方式存储且数据有序120. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度A) nB) log

34、2nC) (h+1)2D) h121. 在一棵平衡二叉树中，每个结点的平衡因子取值范围是A) -11 B) -22 C) 12D) 01122. 在散列查找中，平均查找长度主要与有关。A) 散列表长度B) 散列元素个数C) 装填因子D) 处理冲突方法123. 若根据查找表建立长度为m的闭散列表并采用二次探测处理冲突，假定对个元素第一次计算的散列地址为d，则第四次计算的散列地址为。A) (d+1)mB) (d-1)mC) (d+4)mD) (d-4)m124. 以下说法正确的是。A) 数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字分布情况，并且键值的位数比散列地址的位数多B)

35、除余法要求事先知道全部键值C) 平方取中法需要事先掌握键值的分布情况D) 随机数法适用于键值不相等的场合125. 分块查找的时间效率。A) 低于二分查找B) 高于顺序查找而低于二分查找C) 高于顺序查找D) 低于顺序查找而高于二分查找126. 在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较个结点。A) nB) n2C) (n-1)2D) (n+1)2127. 下述命题是不成立的。A) m阶B-树中的每一个结点的子树个数都小于或等于mB) m阶B-树中的每一个结点的子树个数都大于或等于m/2上限取整C) m阶B-树中的任何一个结点的子树高度都相等D) m阶B-树具有K个子

36、树的非叶子结点含有K-1关键字128. 以下序列不是堆的是。A) (100,85,98,77,80,60,82,40,20,10,66)B) (100,98,85,82,80,77,66,60,40,20,10,)C) (10,20,40,60,66,77,80,82,85,98,100)D) (100,85,40,77,80,60,66,98,82,10,20,)129. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是A) 直接插入排序B) 冒泡排序C) 简单选择排序D) 归并排序130. 在下列算法中，算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

37、A) 堆排序B) 冒泡排序C) 插入排序D) 快速排序131. 从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为排序法。 A) 插入 B) 选择C) 希尔D) 二路归并132. 排序趟数与序列原始状态有关的排序方法是排序法。A) 插入B) 选择C) 冒泡D) 快速133. 下面给出的四种排序法中，排序是不稳定排序法。A) 插入B) 冒泡C) 二路归并D) 堆134. 快速排序在最坏情况下时间复杂度是O(n2)，比的性能差。A) 堆排序B) 起泡排序C) 选择排序135. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序

38、是稳定的，则可选择的排序法 。A) 快速排序B) 堆排序C) 归并排序D) 直接插入排序136. 对任意的7个关键字进行排序，至少要进行次关键字之间的两两比较。A) 13B) 14C) 15D) 16E) 17137. 已知待排序的n个元素可分为nk个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为。A) O(klog2k)B) O(klog2n)C) O(nlog2k)D) O(nlog2n)138. 对给出的一组关键字14，5，19，20，11，19，。若按关键字非递减排序，第一趟排序结果为14，5，19，

39、20，11，19，问采用的排序算法是。A) 简单选择排序B) 快速排序C) 希尔排序D) 二路归并排序139. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是。A) 堆排序快速排序归并排序B) 堆排序归并排序归并排序快速排序D) 堆排序快速排序归并排序E) 巳以上答案都不对140. 假设某文件经过内部排序得到27个初始归并段，若要使多路归并3趟完成，则应取归并的路数为。A) 2B) 3C) 4D) 5141. 下面排序方法中，关键字比较次数与记录的初始排列无关的是。A) 希尔(Shell)排序B) 冒泡排序C) 直接插入排序D) 直接选择排序142. 对记录的关键字集合key

40、=50，26，38，80，70，90，8，30，40，20进行排序，各趟排序结束时的结果为 50 26 38 80 70 90 8 30 40 2050 8 30 40 20 90 26 38 80 7026 8 30 40 20 80 50 38 90 708 20 26 30 38 40 50 70 80 90其使用的排序方法是A) 快速排序B) 基数排序C) 希尔排序D) 归并排序143. 一组记录的关键字为45，80，50，40，42，85则利用堆排序的方法建立的初始堆为。A) 45 50 40 42 85B) 80 50 40 42 45C) 80 50 45 42 40D) 50

41、80 42 45，40， 144. 一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为A) 25， 35， 50， 20， 40， 80， 85， 36， 70B) 25， 35， 50， 80， 20， 85， 40， 70， 36C) 25； 50， 35， 80， 85， 20， 36， 40， 70D) 25， 35， 50， 80， 20， 36， 40， 70， 85145. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为A) O(1) B) O(Log2n)C) O(

42、n2) D) O(n)146. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动 次元素(包括开始将基准元素移到临时变量的那一次)。A) n2 B) n-1C) nD) n+1147. 下述几种排序方法中，要求内存量最大的是A) 插入排序B) 选择排序C) 快速排序D) 归并排序148. 下面排序方法中，时间复杂性不是O(n2)的是 。A) 直接插入排序B) 二路归并排序C) 冒泡排序D) 直接选择排序149. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用法。A) 快速排序B) 堆排序C) 插入排序D) 二路归并排序150. 对下列4个序列用快速排序方法进行排

43、序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列。 A) 70，75，82，90，23，16，10，68 B) 70，75，68，23，10，16，90，82C) 82，75，70，16，10，90，68，23 D) 23，10，16，70，82，75，68，90151. 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 。A) O(log2n)B) O(1)C) O(n)D) O(nlog2n)152. 对下列4种排序方法，在排序中关键字比较次数同记录初始排列无关的是 。A) 直接插入B) 二分法插入C) 快速排序D) 归并排序153. 采用简单选

44、择排序，比较次数与移动次数分别是。A) O(n)，O(log2n)B) O(log2n)，O(n2)C) O(n2)，O(n)D) O(nlog2n)，O(n)154. 归并排序中，归并的趟数是。 A) O(n)B) O(log2n)C) O(nlog2n)D) O(n2)155. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。A) 插入排序B) 选择排序C) 快速排序D) 归并排序156. 直接插入排序在最好情况下的时间复杂度为。A) O(log2n)B) O(n)C) O(nlog2n)D) O(n2)157. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A

45、) nB) 2n-1C) 2nD) n-1158. 下列排序算法中，稳定的排序算法是。A) 堆排序B) 快速排序C) 基数排序D) 希尔排序159. 就平均性能而言，目前最好的内排序方法是 排序法。A) 冒泡B) 希尔插入C) 交换D) 快速160. 快速排序在情况下不利于发挥其长处。A) 待排序数据量太大B) 待排序数据相同值过C) 待排序数据已基本有序D) 待排序数据值差过大161. 在对n个元素进行直接选择排序过程中，第i趟需从 个元素中选择出最小元素。A) n-i+lB) n-iC) iD) i+1162. 若对n个元素进行直接选择排序,是进行任一趟排序的过程中，为寻找最小值元素所需要

46、的时间复杂性为。A) O(1)B) O(log2n)C) O(n2)D) O(n)163. 在下列排序方法中，空间复杂性为O(log2n)的方法是。A) 直接选择排序B) 归并排序C) 堆排序D) 快速排序164. 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为。A) 希尔排序B) 冒泡排序C) 插入排序D) 选择排序165. 从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)一端的方法称为。A) 希尔排序B) 归并排序C) 插入排序D) 选择排序166. 用ISAM和VSAM组织文件属于 。A) 顺序文件B) 索引

47、文件C) 散列文件167. 索引顺序文件是 。A) HASH文件B) ISAM文件C) 顺序文件D) 索引文件168. 删除ISAM文件记录时，一般 。A) 只需做删除标志B) 需移动记录C) 需改变指针D) 一旦删除就要做整理169. 直接存取方法是利用 进行组织的文件。A) HASH法 B) 顺序索引法C) VSAM法D) ISAM法170. 倒排文件的主要优点是 。A) 便于进行插入和删除运算B) 便于节省存储空间C) 便于进行文件合并D) 能大大提高基于非关键字的检索速度171. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，所以选择好的 方

48、法是散列文件(Hash)的关键。A) 散列函数B) 除余法中的质数C) 冲突处理D) 散列函数和冲突处理172. 倒排文件包含有若干个倒排表，倒排表的内容是 ，倒排文件检查速度快但修改、维护较难。A) 一个关键字值和该关键字的记录地址B) 一个属性值和该属性的一个记录地址C) 一个属性值和该属性的全部记录地址D) 承多个关键字值和它们相对应的某个记录地址173. 影响文件检索效率的一个重要因素是A) 逻辑记录的大小B) 物理记录的大小C) 访问外存的次数D) 设备的读写速度174. 顺序文件适于。A) 直接存取B) 成批处理C) 按关键字存取D) 随机存取175. 对散列文件，以下说法错误的是

49、一A) 散列文件插入、删除方便，不需要索引区且节省存储空间B) 散列文件只能按关键字随机存取且存取速度快C) 经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况D) 散列文件顺序存取方便176. 对于一个索引顺序文件，索引表中的每个索引项对应主文件中的 。A) 一条记录B) 多条记录C) 所有记录D) 三条以下记录177. 对于索引文件，稠密索引中的每个索引项对应被索引表中的 。A) 所有记录B) n条以下记录C) 一条记录D) 多条记录178. VSAM文件的索引集是一个 。A) 二叉排序树结构B) 散列表结构C) 线性表结构D) B+树结构179. 散列文件又称按桶散列文

50、件，若散列文件中含有m个基桶，每个桶能够存储m个记录，若不使用溢出桶，则该散列文件最多能够存储 个记录。A) m+kB) mk-1C) mk+lD) mk180. 对文件进行直接存取的依据是 。A) 按逻辑记录号去存取某个记录B) 按逻辑记录的结构去存取某个记录C) 按逻辑记录的关键字去存取某个记录D) 按逻辑记录的具体内容去存取某个记录181. 直接存取文件的特点是 。A) 记录按关键字排序B) 记录可以进行顺序存取C) 存取速度快但占用较多的存储空间D) 记录不需要排序且存取效率高182. 索引顺序文件的记录，在逻辑上按关键字的顺序排列，但物理上不一定按关键字顺序存储，故需建立一张指示逻辑

51、记录和物理记录之间一一对应关系的 。A) 索引表B) 链接表C) 符号表D) 交叉访问表183. 以下说法错误的是 。A) 在磁带上的顺序文件的最后添加新的记录时不必复制整个文件B) 索引顺序文件既能顺序访问又能随机访问C) 变更磁盘上的顺序文件记录的内容时，不一定要复制整个文件D) 索引顺序文件是一种特殊的顺序文件，因此通常放在磁带上二、 多项选择题1. 数据元素是 。A) 数据集合中的一个个体B) 数据的基本单位C) 数据的最小单位D) 一个结点E) 一个记录2. 数据结构被形式地定义为(K，R)，其中K是 的有限集，R是K上的 有限集。A) 算法B) 数据元素C) 数据操作D) 逻辑结构

52、A) 操作B) 映像C) 存储 D) 关系3. 线性表的说法错误的是 A) 每个元素都有一个直接前驱和一个直接后继B) 线性表中至少要有一个元素C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继4. 以下说法错误的是 A) 顺序存储方式的优点是存储密度大且插入、删除运算效率高B) 链表的每个结点中都恰好包含一个指针C) 线性表的顺序存储结构优于链式存储结构D) 顺序存储结构属于静态结构而链式结构属于动态结构5. 以下说法正确的是 A) 对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表B) 对简单

53、链表来说，只有从头结点开始才能扫描表中全部结点C) 双链表的特点是找结点的前趋和后继都很容易D) 对双链表中来说，结点中既存放其前趋结点指针，也存放后继结点指针6. 以下说法正确的是 。A) 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B) 顺序存储的线性表可以直接存取C) 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D) 线性表的链式存储结构优于顺序存储结构7. 便于插入和删除操作的是 A) 单链表B) 顺序表C) 双链表D) 循环链8. 从表中任一结点出发都能扫描整个链表的是 A) 单链表B) 顺序表C) 双链表D) 循环链表9. 双向

54、链表的主要优点是 。A) 不再需要头指针B) 已知某结点位置后能容易找到其直接前趋C) 在进行插入、删除运算时能保证链表不断开D) 从表中任一结点出发都能扫描整个链表10. 对顺序表的优缺点，以下说法正确的是 。A) 无需为表示结点间的逻辑关系而增加额外的存储空间B) 可以方便地随机取表中的任一结点C) 插入和删除运算较为方便D) 由于要求占用连续空间，所以存储分配只能预先进行(静态分配)11. 循环队列是 。A) 顺序存储结构B) 不会产生下溢C) 不会产生假溢D) 不会产生上溢12. 以下说法正确的是 。A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B) 二叉树是树的特殊情形C) 由树转换成二叉树，其根结点的右子树总是空的D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树13. 设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点树至少为 ，至多为 。A) 2hB) 2h-1C) 2h+1D) h+1A) 2h-1B) 2h-1C) 2h+1+1