孙夫雄数据结构习题

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

2、易读性、稳定性和确定性4. 以下属于逻辑结构的概念是 。A) 顺序表B) 哈希表C) 有序表 D) 单链表5. 具有线性结构的数据结构是 。A) 图B) 树 C) 广义表D) 栈6. 数据的存储结构包括顺序、链接、散列和 种基本类型。A) 向量B) 数组C) 集合D) 索引7. 根椐数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据组织形式。下列解释错误的是 。A) 集合中任何两个结点之间都有逻辑关系，但组织形式松散B) 线性结构中结点按逻辑关系依次存储成一行C) 树型结构具有分支、层次特性，其形态有点像自然界中的树D) 图状结构中各个结点按逻辑关系互相缠绕，任何两个结点都可以

3、邻接8. 在数据结构中，从逻辑上可以把数据结构分成 。A) 动态结构和静态结构B) 紧凑结构和非紧凑结构C) 线性结构和非线性结构D) 内部结构和外部结构9. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 。A) 存储结构B) 存储实现C) 逻辑结构D) 运算实现10. 以下说法错误的是 。A) 程序设计的实质是算法设计B) 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C) 运算实现是完成运算功能的算法或这些算法的设计D) 算法设计思想总是与数据的某种相应存储形式相联系11. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 存储方

4、式最节省运算时间。 A) 单链表B) 仅有头指针的单循环链表C) 双链表D) 仅有尾指针的单循环链表12. 单链表的主要优点是 。A) 便于随机查询B) 存储密度高C) 逻辑上相邻的元素在物理上也是相邻的D) 插入和删除比较方便13. 线性表采用链式存储时，其地址 。A) 必须连续B) 一定不连续 C) 部分连续D) 连续与否均可14. 对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该 。A) 以顺序方式存储B) 以链接方式存储C) 以散列方式存储D) 以上均可15. 若线性表中最常用的操作是取第i个的前趋元素，采用 存储方式最节省时间。A)

5、 顺序表B) 单链表C) 双链表D) 单循环链表16. 若用单链表来表示队列，则应该选用 。 A) 带尾指针的非循环链表B) 带尾指针的循环链表C) 带头指针的非循环链表D) 带头指针的循环链表17. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。从队列中出队一个元素，再进队两个元素后，rear和front的值分别为 A) 1和5B) 2和4C) 4和2D) 5和118. 设栈的输入序列是(1、2、3，4)，则 不可能输出的序列。A) 1243B) 2134C) 1432D) 431219. 一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是

6、。A) 23415B) 54132C) 23145D) 1543220. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是 。A) 6 B) 4 C) 3D) 221. 一般情况下，将递归算法转换成等价的非递增归算法应该设置 。A) 堆栈B) 队列C) 堆栈或队列D) 数组22. 设栈的输入序列是1、2、n，若输出序列的第一个元素是n，则第i个输出元素 。A) 不确定B) n-i+lC) cD) n-i23. 假定一个顺序循环队列的队首和队尾指针分别用f

7、ront和rear表示，则判队空的条件是 。A) front+1=rearB) front=rear+1C) front=OD) front=rear24. 假定一个顺序循环队列存储于数组an中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是 。A) (rear-1)n=frontB) rear=(front-1)nC) (rear+1)n=frontD) rear=(front+1)n25. 采用 数据结构设计一个判别表达式中左、右括号是否配的算法最佳。A) 线性表的顺序存储结构B) 队列C) 线性表的链式存储结构D) 栈26. 在下列算法描述中，涉及到队运算的算法是 。

8、A) 表达式求值算法B) 深度优先搜索C) 二叉树前中后序遍历D) 广度优先搜索27. 当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为 。A) N-2B) N-1C) ND) N+l28. 链栈与顺序栈相比有一个明显的优点，即 。A) 插入操作更加方便B) 通常不会出现栈满的情况C) 不会出现栈空的情况D) 删除操作更加方便29. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 。A) 所有的结点均无左孩子B) 所有的结点均无右孩子C) 只有一个叶子结点D) 是任意一棵二叉树30. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 。A) 250B)

9、 500C) 505 D) 50131. 以下说法正确的是 。A) 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B) 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C) 在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D) 在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点32. 以下说法错误的是 。A) 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍

10、历序列中的第一个结点C) 己知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个D) 在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的33. 二叉树在线索化后，仍不能有效求解的问题是 。A) 前序线索二叉树中求前序后继B) 中序线索二叉树中求中序后继C) 中序线索二叉树中求中序前趋D) 后序线索二叉树中求后序后继34. 若二叉树采用链式存储结构，要交换其所有分支结点左、右子树的位置，利用 遍历方法最合适。A) 前序B) 中序C) 后序D) 层次35. 一棵有124个叶结点的完全叉树，最多有 个结点。A) 247B) 248C) 249D)

11、25036. 设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是 A) a在b的右方B) a在b的左方C) a是b的祖先D) a是b的子孙37. 在一棵具有n个结点的完全二叉树中，分枝结点的最大编号为 。A) (n+1)2)下限取整B) (n-1)2) 下限取整C) (n2) 下限取整D) (n2) 上限取整38. 在N个结点的线索二叉树中，线索的数目为 。A) N-1B) NC) N+1D) 2N39. 设深度为K的二叉树上只有度为0和2的结点，则这类二叉树上所含的结点总数至少为 。A) K+1B) 2KC) 2K-1D) 2K+140. 设有13个值，用它们组成一棵哈夫曼树

12、，则该哈夫曼树共有 个结点。A) 13B) 12C) 26D) 2541. 以下说法错误的是 。A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B) 二叉树是树的特殊情形C) 由树转换成二叉树，其根结点的右子树总是空的D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树42. 若二叉树是 则从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。A) 二叉排序树B) 哈夫曼树C) 堆D) 退化二叉树43. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A1n)中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数

13、组A中的位置是 。 A) A2i (2inB) A2i+1) (2i+1n)C) Ai/2D) 条件不充分，无法确定44. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是 。A) 4B) 5C) 6D) 745. 下列有关二叉树的说法正确的是 。A) 二叉树的度为2B) 一棵二叉树度可以小于2C) 二叉树中至少有一个结点的度为2D) 二叉树中任一个结点的度都为246. 某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是 。，A) EGFACDBB) EACBDGFC) EAGCFBDD) 上面的都不对47. 对二叉排序树进行 遍历，可以得到该二叉

14、树所有结点构成的排序序列A) 前序B) 中序C) 后序D) 按层次48. 的遍历仍需要栈的支持。A) 前序线索树B) 中序线索树C) 后序线索树D) 层次遍历49. 在一棵深度为h的完全二叉树中，所含结点的个数不小于 。A) 2hB) 2h+1C) 2h-1D) 2h-150. 在一棵具有n个结点的二叉树第i层上，最多具有 个结点。A) 2iB) 2i+1C) 2i-1D) 2n51. 树最适合用来表示 。A) 有序数据元素B) 无序数据元素C) 元素之间具有分支层次关系的数据D) 元素之间无联系的数据52. 以下说法错误的是 。A) 一般在哈夫曼树中，权值越大的叶子离根结点越近B) 哈大曼树

15、中没有度数为1的分支结点C) 若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点D) 若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树53. 以下说法错误的是 。A) 二叉树可以是空集B) 二叉树的任一结点都可以有两棵子树C) 二叉树与树具有相同的树形结构D) 二叉树中任一结点的两棵子树有次序之分54. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是 的二叉树。A) 空或只有一个结点B) 任一结点无左子树C) 高度等于其结点数D) 任一结点无右子树55. 设无向图的顶点个数为n，则该无向图最多有 条边。A) n-1B) n(n-1)/2C) n(n

16、+1)/2D) 0E) n256. 采用邻接表存储的图，其深度优先遍历类似于二叉树的 。A) 中序遍历B) 先序遍历C) 后序遍历D) 按层次遍历57. 采用邻接表存储的图，其广度优先遍历类似于二叉树的 。A) 按层次遍历B) 中序遍历C) 后序遍历D) 先序遍历 ，58. 一个图中包含有七个连通分量，若按深度优先(DFS)遍历,必须调用 次深度优先遍历算法。A) kB) 1C) k-1D) k+159. 下列说法中不正确的是 A) 无向图中的极大连通子图称为连通分量B) 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D) 有向

17、图的遍历不可采用广度优先搜索方法 60. 具有n个顶点的有向图最多有 条边。A) nB) n(n-1)C) n(n+1)D) n261. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是 。A) G中有弧<Vi，Vj>B) G中有一条从Vi到Vj的路径C) G中没有弧<Vi，Vj> D) G中有一条从Vj到Vi的路径62. 一个n个顶点的连通无向图，其边的个数至少为 。A) n-1B) n C) n+lD) nlog2n63. 下列说法中，正确的有 。A) 最小生成树也是哈夫曼树。B) 最小生成树惟一C) 普里姆(Prim)最小生成树算法时间

18、复杂度为O(n2)D) 克鲁斯卡尔(Kruskal)最小生成树算法比普里姆算法更适合于边稠密的网64. 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用 。A) 求关键路径的方法B) 求最短路径的Dijkstra方法C) 深度优先遍历算法D) 广度优先遍历算法65. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为 。A) sB) s-1C) s+lD) n66. 在一个无向图中，若两个顶点之间的路径长度为k条边，则该路径上的顶点数为 。A) kB) k+lC) k+2D) 2k67. 一个有n个顶点的无向连通图，它所包含的连通分量个数为 。A

19、) 0B) 1C) nD) n+168. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。A) klB) k2C) k1-k2D) k1+k269. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。A) klB) k2C) k1-k2D) k1+k270. 对于一个无向图，下面 的说法是正确的。A) 每个顶点的入度等于出度B) 每个顶点的度等于其入度与出度之和C) 每个顶点的入度为0 D) 每个顶点的出度为071. 为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用 。A) 顺序存储B)

20、 链式存储C) 索引存储D) 散列存储72. 设有一个按各元素的值排好序的线性表且长度大于2，对给定的值X，分别用顺序查找法和二分查找法查找一个与K相等的元素，比较次数分别是s和b：在查找不成功的情况下，正确的s和b的数量关系是 。A) 总有s=bB) 总有s>bC) 总有s<bD) 与K值大小有关73. 若在线性表中采用折半查找法查找元素，该线性表应该 。A) 元素按值有序B) 采用顺序存储结构C) 元素按值有序，且采用顺序存储结构D) 元素按值有序，且采用链式存储结构74. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行 次探测。A) k-1次

21、B) k次C) k+1次D) k(k+1)2次75. 设散列地址空间0m-1，k为关键字，用p去除k，将余数作为k的散列地址 (h(k)=k%p)，为了减少发生冲突的可能性，一般取P为 。A) 小于m的最大奇数B) 小于m的最大素数C) 小于m的最大偶数D) 小于m的最大合数76. 设散列表的长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) 977. 从具有n个结点的二叉排序树中查找一个元

22、素时，最坏情况下的时间复杂性 。A) O(n)B) O(1)C) O(log2n)D) O(n2)78. 下面关于二叉排序树论述中，错误的是 。A) 当所有结点的权值都相等时，用这些结点构造的二叉排序树除根结点外只有右子树B) 中序遍历二叉排序树的结点就可以得到排好序的结点序列C) 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间D) 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列是一样的79. 以下说法错误的是 。A) 散列法存储的基本思想是由关键码值决定数据的存储地址B) 散列表的结点中只包含数据元素自身的信息，不包含任何指针C) 装填

23、因子是散列法的一个重要参数，它反映了散列表的装填程度D) 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法80. 设有一个用线性探测法解决冲突得到的散列表如图所示0 1 2 3 4 5 6 7 8 9 101325801617614 图 散列表散列函数为H=11，若要查找元素14，探测的次数是 。A) 8B) 9C) 3D) 681. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是 。A) 分块查找B) 顺序查找C) 折半查找D) 基于属性查找82. 有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉排序树，

24、若希望高度最小，则应选择下面哪个序列输入 。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,5383. 建立序列50，72，43，85，75，20，35，45，65，30对应的二叉排序树以后，查找元素35要进行 元素间的比较A) 4次B) 5次C) 7次D) 10次84. 在顺序表(n足够大)中进行顺序查找，其查找不成功的平均长度是 。A) (n+1)2B) n2+lC) n D) n+l85. 对线性表进行二分检索时，要求线性表必须 。A) 以顺序存储方式存储B

25、) 以链式存储方式存储C) 以顺序存储方式存储且数据有序D) 以链式存储方式存储且数据有序86. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度A) nB) log2nC) (h+1)2D) h87. 在散列查找中，平均查找长度主要与 有关。A) 散列表长度B) 散列元素个数C) 装填因子D) 处理冲突方法88. 若根据查找表建立长度为m的散列表并采用二次探测处理冲突，假定对个元素第一次计算的散列地址为d，则第四次计算的散列地址为 。A) (d+1)mB) (d-1)mC) (d+4)mD) (d-4)m89. 以下说法正确的是 。A) 数字分析法需事先知道所有可能出现

26、的键值及所有键值的每一位上各数字分布情况，并且键值的位数比散列地址的位数多B) 除余法要求事先知道全部键值C) 平方取中法需要事先掌握键值的分布情况D) 随机数法适用于键值不相等的场合90. 分块查找的时间效率 。A) 低于二分查找B) 高于顺序查找而低于二分查找C) 高于顺序查找D) 低于顺序查找而高于二分查找91. 在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较 个结点。A) nB) n2C) (n-1)2D) (n+1)292. 以下序列不是堆的是 。A) (100,85,98,77,80,60,82,40,20,10,66)B) (100,98,85,82,80

27、,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,)93. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是 A) 直接插入排序B) 冒泡排序C) 简单选择排序D) 归并排序94. 在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A) 堆排序B) 冒泡排序C) 插入排序D) 快速排序95. 从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为

28、 排序法。 A) 插入 B) 选择C) 希尔D) 二路归并96. 下面给出的四种排序法中， 排序是不稳定排序法。A) 插入B) 冒泡C) 二路归并D) 堆97. 快速排序在最坏情况下时间复杂度是O(n2)，比 的性能差。A) 堆排序B) 冒泡排序C) 选择排序D) 二路归并98. 对给出的一组关键字14，5，19，20，11，19。若按关键字非递减排序，第一趟排序结果为14，5，19，20，11，19，问采用的排序算法是 。A) 简单选择排序B) 快速排序C) 希尔排序D) 二路归并排序99. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 。A) 堆排序<快速排序&l

29、t;归并排序B) 堆排序<归并排序<快速排序C) 堆排序>归并排序>快速排序D) 堆排序>快速排序>归并排序E) 巳以上答案都不对100. 假设某文件经过内部排序得到27个初始归并段，若要使多路归并3趟完成，则应取归并的路数为 。A) 2B) 3C) 4D) 5101. 下面排序方法中，关键字比较次数与记录的初始排列无关的是 。A) 希尔(Shell)排序B) 冒泡排序C) 直接插入排序D) 直接选择排序102. 对记录的关键字集合key=50，26，38，80，70，90，8，30，40，20进行排序，各趟排序结束时的结果为：50 26 38 80 70

30、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) 归并排序103. 一组记录的关键字为45，80，50，40，42，85则利用堆排序的方法建立的初始堆为 。A) 45 50 40 42 85B) 80 50 40 42 45C) 80 50 45 42 40D) 50 80 42 45，40， 104. 一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其

31、中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为 。A) 15，25，35，50，20，40，80，85，36，70B) 15，25，35，50，80，20，85，40，70，36C) 15，25；50，35，80，85，20，36，40，70D) 15，25，35，50，80，20，36，40，70，85105. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为 。A) O(1) B) O(Log2n)C) O(n2) D) O(n)106. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动 次元素(包括开始将基准元素移到临时变量的那一次)。A) n

32、2 B) n-1C) nD) n+1107. 下述几种排序方法中，要求内存量最大的是 。A) 插入排序B) 选择排序C) 快速排序D) 归并排序108. 下面排序方法中，时间复杂性不是O(n2)的是 。A) 直接插入排序B) 二路归并排序C) 冒泡排序D) 直接选择排序109. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用 法。A) 快速排序B) 堆排序C) 插入排序D) 二路归并排序110. 对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列 。 A) 70，75，82，90，23，16，10，68

33、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，90111. 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 。A) O(log2n)B) O(1)C) O(n)D) O(nlog2n)112. 对下列4种排序方法，在排序中关键字比较次数同记录初始排列无关的是 。A) 直接插入B) 二分法插入C) 快速排序D) 归并排序113. 采用简单选择排序，比较次数与移动次数分别是 。A) O(n)，O(log2n)B) O(log2n)，O(n2)C) O(n2)，O(n)D) O(n

34、log2n)，O(n)114. 归并排序中，归并的趟数是 。 A) O(n)B) O(log2n)C) O(nlog2n)D) O(n2)115. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。A) 插入排序B) 选择排序C) 快速排序D) 归并排序116. 直接插入排序在最好情况下的时间复杂度为 。A) O(log2n)B) O(n)C) O(nlog2n)D) O(n2)117. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。A) nB) 2n-1C) 2nD) n-1118. 下列排序算法中，稳定的排序算法是 。A) 堆排序B) 快速排序C) 基数排序D

35、) 希尔排序119. 就平均性能而言，目前最好的内排序方法是 排序法。A) 冒泡B) 希尔插入C) 交换D) 快速120. 快速排序 在情况下不利于发挥其长处。A) 待排序数据量太大B) 待排序数据相同值过C) 待排序数据已基本有序D) 待排序数据值差过大121. 在对n个元素进行直接选择排序过程中，第i趟需从 个元素中选择出最小元素。A) n-i+lB) n-iC) iD) i+1122. 若对n个元素进行直接选择排序,是进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为 。A) O(1)B) O(log2n)C) O(n2)D) O(n)123. 在下列排序方法中，空间复杂性为O

36、(log2n)的方法是 。A) 直接选择排序B) 归并排序C) 堆排序D) 快速排序124. 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。A) 希尔排序B) 冒泡排序C) 插入排序D) 选择排序125. 从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)一端的方法称为 。A) 希尔排序B) 归并排序C) 插入排序D) 选择排序126. 用ISAM和VSAM组织文件属于 。A) 顺序文件B) 索引文件C) 散列文件127. 索引顺序文件是 。A) HASH文件B) ISAM文件C) 顺序文件D) 索引文件128.

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

38、文件包含有若干个倒排表，倒排表的内容是 ，倒排文件检查速度快但修改、维护较难。A) 一个关键字值和该关键字的记录地址B) 一个属性值和该属性的一个记录地址C) 一个属性值和该属性的全部记录地址D) 承多个关键字值和它们相对应的某个记录地址133. 影响文件检索效率的一个重要因素是 。A) 逻辑记录的大小B) 物理记录的大小C) 访问外存的次数D) 设备的读写速度134. 顺序文件适于 。A) 直接存取B) 成批处理C) 按关键字存取D) 随机存取135. 对散列文件，以下说法错误的是 。A) 散列文件插入、删除方便，不需要索引区且节省存储空间B) 散列文件只能按关键字随机存取且存取速度快C)

39、经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况D) 散列文件顺序存取方便136. 对于一个索引顺序文件，索引表中的每个索引项对应主文件中的 。A) 一条记录B) 多条记录C) 所有记录D) 三条以下记录137. 对于索引文件，稠密索引中的每个索引项对应被索引表中的 。A) 所有记录B) n条以下记录C) 一条记录D) 多条记录138. VSAM文件的索引集是一个 。A) 二叉排序树结构B) 散列表结构C) 线性表结构D) B+树结构139. 散列文件又称按桶散列文件，若散列文件中含有m个基桶，每个桶能够存储m个记录，若不使用溢出桶，则该散列文件最多能够存储 个记录。A)

40、m+kB) m×k-1C) m×k+lD) m×k140. 对文件进行直接存取的依据是 。A) 按逻辑记录号去存取某个记录B) 按逻辑记录的结构去存取某个记录C) 按逻辑记录的关键字去存取某个记录D) 按逻辑记录的具体内容去存取某个记录141. 直接存取文件的特点是 。A) 记录按关键字排序B) 记录可以进行顺序存取C) 存取速度快但占用较多的存储空间D) 记录不需要排序且存取效率高142. 索引顺序文件的记录，在逻辑上按关键字的顺序排列，但物理上不一定按关键字顺序存储，故需建立一张指示逻辑记录和物理记录之间一一对应关系的 。A) 索引表B) 链接表C) 符号表D

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

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

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

44、直接前趋C) 在进行插入、删除运算时能保证链表不断开D) 从表中任一结点出发都能扫描整个链表10. 对顺序表的优缺点，以下说法正确的是 。A) 无需为表示结点间的逻辑关系而增加额外的存储空间B) 可以方便地随机取表中的任一结点C) 插入和删除运算较为方便D) 由于要求占用连续空间，所以存储分配只能预先进行(静态分配)11. 循环队列是 。A) 顺序存储结构B) 不会产生下溢C) 不会产生假溢D) 不会产生上溢12. 以下说法正确的是 。A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B) 二叉树是树的特殊情形C) 由树转换成二叉树，其根结点的右子树总是空的D) 在二叉树只有一棵

45、子树的情况下也要明确指出该子树是左子树还是右子树13. 设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点树至少为 ，至多为 。A) 2hB) 2h-1C) 2h+1D) h+1A) 2h-1B) 2h-1C) 2h+1+1D) 2h+114. 对于前序遍历与中序遍历结果相同的 F 。前序遍历与后序遍历结果相同的二叉树为 B 。A) 一般二叉树B) 只有根结点的二叉树C) 根结点无左孩子的二叉树D) 根结点无右孩子的二叉树E) 所有结点只有左子树的二叉树F) 所有结点只有右子树的二叉树15. 完全二叉树 。A) 适合于用顺序结构存储B) 叶子结点可在任一层出现C) 某些结点有左子树则必有

46、右子树D) 某些结点有右子树则必有左子树16. 下列有关二叉树的说法错误的是 。A) 二叉树的度为2B) 一棵二叉树度可以小于2C) 二叉树中至少有一个结点的度为2D) 二叉树中任一个结点的度都为217. 下面哪一个方法可以判断出一个有向图中是否有环(回路)。A) 深度优先遍历B) 拓扑排序C) 求最短路径D) 求关键路径18. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为(1)，所有顶点的邻接表的结点总数为(2)。 (1) A)n B)n+1 C)n-1 D)n+e (2) A)e2 B)e C)2e D)n+e19. 图的应用算法有 。A) 克鲁斯卡尔算法B)

47、哈夫曼算法C) 拓扑排序算法D) 迪杰斯特拉算法20. 对初始状态为递增序列的表按递增序列排序，最省时间的是(1 C )算法，最费时间的是（2 B ）算法A) 堆排序B) 快速排序C) 插入排序D) 归并排序21. 在下述排序算法中，所需辅助存储量最多的是 (B)，所需辅助存储量最少的是(C)，平均速度最快的是(A)A) 快速排序B) 归并排序C) 堆排序22. 在堆排序过程中，由n个待排序的记录建成初始堆需要(B)次筛选：由初始堆到排序结束需要进行(D)上次筛选运算；在每次筛选运算的过程中，记录的比较和移动次数的数量级为(E)，堆排序算法的时间复杂度为(G)。A) nB) n2C) log2

48、nD) n-1E) O(log2n)F) O(n)G) O(nlog2n)H) O(n2)23. 下面的排序算法中不稳定的是 。A) 起泡排序B) 折半插入排序C) 简单选择排序D) 希尔排序E) 基数排序F) 堆排序24. 稳定的排序方法有 。A) 希尔排序法B) 归并排序法C) 直接选择法D) 直接插入法E) 冒泡排序法25. 下列那些排序算法的时间复杂度是O(n2)的有 。A) 冒泡法B) 归并法C) 堆排序D) 直接插入E) 直接选择26. 在排序算法中实施过程中，使用辅助存储空间为O(1)的有 。A) 直接插入排序法B) 快速排序递归算法C) 归并排序法D) 堆排序法27. 如果待排

49、序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的， 就是不稳定的排序算法。 A) 起泡排序B) 归并排序C) Shell排序D) 直接插入排序E) 简单选择排序28. 堆排序是(E)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(G)。A) 插入B) 交换C) 归并D) 基数E) 选择F) 0(n2)和O(1)G) O(nlog2n)和O(1)H) O(nlog2n)和O(n)I) O(n2)和O(n)29. 直接插入排序和冒泡排序的时间复杂度为(D)，若初始数据有序(即正序)，则时间复杂度为(A)。A) O(n)B) O(log2n)C) O(nlog2n)D) O(n2)30. 在直接选择排序中，记录比较次数为(C)数量级，记录的移动次数为(A)数量级。A) O(n)B) O(log2nC) O(n2)D) O(nlog2n)31. 在平均情况下，快速排序的时间复杂度为(C)，空间复杂性为(B)，在最坏情况下(如初始记录已有序)，快速排序的时间复