数据结构试题库

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

1、精选优质文档-倾情为你奉上数据结构试题库一、单项选择题1. 下列程序段所代表的算法的时间复杂度为（D）。x=n;y=0;while (x=(y+1)*(y+1) y+;(A) O(n)(B)O(n 2)(C)O(log 2n)(D)O(n )2. 在一个长度为n 的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ） 。(A) n2(B)(n-1)/2(C)(n+1)/2(D)n/23. 在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（ C）。(A) HS-next=s;(B)s-next=HS-next;

2、HS-next=s;(C)s-next=HS;HS=s;(D)s-next=HS;HS=HSnext;4. 假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front ，不设队列尾指针。 若要进队一个元素*s ，则在下列程序算法的空白处应添加的操作语句是（A ） 。void AddQueue(struct linkqueue Q)p=Q-front;while(p-next!=Q-front) p=p-next;(A)p-next=s;s-next=Q-front; (B)Q-front-next=s;Q-front=s; (C)s-next=p;p-next=Q-front;(D)

3、Q-front-next=s;s-next=p;5. 设高度为h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（B ） 。(A)2 h-1(B)2 h-1 +1(C)2 h-1(D)2 h-1 -36现有数据集 53,30,37,12,45,24,96，从空二叉树逐个插入数据形成二叉排序树，专心-专注-专业若希望查找此二叉树中任一结点的平均查找长度最小，则应选择下面哪个序列输入（C）。(A)45,24,53,12,37,96,30(B) 30,24,12,37,45,96,53(C) 37,24,12,30,53,45,96(D) 12,24,30,37,45,

4、53,967. 有一组数值5,12,9,20,3，用以构造哈夫曼树，则其带权路径长度WPL值为（ D）。(A)93(B)96(C)123(D)1038. 已知一个有向图G 的顶点v=v1,v2,v3,v4,v5,v6，其邻接表如下图所示，根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点遍历序列是（ B ） 。(A)v1,v2,v3,v6,v4,v5(B)v1,v2,v3,v6,v5,v4(C)v1,v2,v5,v6,v3,v4(D)v1,v2,v5,v3,v4,v6v5v4v1v2v5v2v3v3v6v6v3v4v5v4v69. 设有 m=2 n-1 个关键字， 假设对每个关键字

5、查找的概率相等，查找失败的概率为0 ，若采用二分法查找一个关键字，则平均查找长度为（D ） 。(A)n-1(B) n-n/m(C) (n-1)-n/m(D) (n-1)+n/m10 已知一个待散列存储的线性表18,81,58,34,26,75,67,49,93，散列函数为h(k)=k%11 ，散列地址空间为010 。若采用线性探查法解决冲突，则平均查找长度为（A ） 。(A)5/3(B)13/9(C)16/9(D)3/211. 下列程序段所代表的算法的时间复杂度为（C ） 。y=n;x=1;nwhile(xnext=NULL(C)head-next=head(D)head!=NULL15. 若

6、链队列HQ中只有一个结点，则队列的头指针和尾指针满足下列条件（ D）。(A) HQ-rear-next=HQ-front(B)HQ-front-next=HQ-rear-next (C)HQ-front=HQ-rear(D)HQ-front-next=HQ-rear16. 从一个栈顶指针为HS 的链栈中删除一个结点时，用x 保存被删除结点的值， 则应执行操作为（A ） 。(A) x=HS-data; HS=HS-next;(B)x=HS-data;HS-NEXT=NULL; (C)HS=HS-next;x=HS-data;(D)x=HS-data; HS=NULL;17. 一棵有n 个结点的满

7、二叉树，有m 个叶子结点，深度为h，那么 n、m 和 h满足条件（D）。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-118. 一 棵左 、右子树均不为空 的二 叉树在先序线索化 后， 其空指针域数为（ B ） 。(A)0(B)1(C)2(D) 不确定 有一组数值 5,12,9,20,3，用以构造哈夫曼树，则其带权路径长度WPL值为（ C）。(A)49(B)96(C)103(D)1251920. 在一个 n 个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值为（A ） 。(A) n(B)n/2(C)log 2 n(D)n*log 2 n21. 已知有向图G=(V,

8、E) ，其中 V=v1,v2,v3,v4,v5,v6，则下列边集合E 中（ A ）所对应的有向图没有拓扑序列。(A) E=, (B) E=, (C) E=,(D) E=,22. 冒泡排序算法在最好情况下的时间复杂度为（B ） 。(A)O(log 2n)(B)O(n)(C)O(1)(D)O(n 2)23. 在下列内部排序方法中，排序时不稳定的， 而且关键字的比较次数与记录的初始排列次序无关的是（D）。(A) 快速排序(B) 冒泡排序(C) 归并排序(D) 堆排序24 已知一个待散列存储的线性表18,81,58,34,26,75,67,49,93，散列函数为(A)5/3(B)13/9(C)16/9

9、(D)3/2 下列程序段所代表的算法的时间复杂度为（D ） 。i=1;j=0;while(inext=p-next;p-next=s;(B)s-next=head;p-next=s; (C)s-next=p-next;p-next=head;(D)s-next=p-next; s-next=p;29. 已知用循环链表表示的队列长度为n，若只设头指针，则出队和入队一个元素的时间复杂度分别是（B）。(A)O(1) 和 O(1)(B)O(1) 和 O(n)(C)O(n) 和 O(1)(D)O(n)和 O(n)30. 设链队列Q 的头指针和尾指针分别为front 和 rear ，初始时队列为空，若向队

10、列插入一个元素*s ，则应执行的指针操作为（C ） 。(A)Q-front-next=s;s-next=Q-rear;Q-rear=NULL; (B)s-next=Q-front;Q-rear-next=s;Q-rear=NULL; (C)Q-rear-next=s;Q-rear=s;s-next=NULL;(D)Q-front-next=s;Q-rear=s;s-next=NULL;31. 已知一个带权图的顶点集V 和边集 G 分别为：V=1,2,3,4,5,6,7,8;E=(3,1)6 ， (3,4)7 ， (3,7)5 ， (1,2)3 ， (1,4)4 ， (4,7)8 ， (4,5)

11、4 ， (7,8)5 ， (2,6)3 ，(2,5)5, (5,8)8, (5,6)5, (8,6)6,则该图的最小生成树的权值为（C） 。 (A)24(B)29(C)30(D)3132. 当待排序的关键字个数n 很小，且初始排列为逆序时，采用下列排序方法中的（ D），算法的时间复杂度最小。(A) 直接插入排序(B) 简单选择排序(C) 冒泡排序(D) 快速排序33. 对二叉排序树进行（ C ）遍历， 可以得到该二叉树所有结点构成的排序序列。(A) 层次(B) 前序(C) 中序(D) 后序34 已知一个长度为12 的线性表（ 8， 2， 5， 7 ，12， 3， 10，4 ， 1， 6， 9，

12、 11 ），并将线性表中的元素依次插入到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为（A）。(A)10/3(B)13/3(C)37/12(D)13/235 一组关键字序列15 ，92 ，124 ，5 ， 27， 28， 18， 6 ，36 ，34 ，30 ， 26 ， 32，259 ，将它们用散列函数H(key)=keyMOD11按顺序散列到HASH表 HT（ 0:10 ）中，用链地址解决冲突。假设查找每一个元素的概率相同，则查找该HASH表中任一元素的平均查找长度为（C）。(A)3/2(B)10/7(C)11/7(D)9/736. 以数

13、据集 4 ， 5 ， 6， 7， 12 ， 18， 10 为结点权值所构造的哈夫曼树，则其带权路径长度WPL 为（A ） 。(A)165(B)203(C)124(D)18737. 假定对线性表R0n-1 进行分块查找， 若将表均匀地分为b 块，每块含有n/b个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL 最小，则分块数b 的值应为（B ） 。n(B)n(A)+1(C) log 2n(D) log 2 n+138. 对 n 个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别是（C ） 。(A)n(n+1)/2和 n(B)n(n

14、-1)/2和 n-1(C) n(n+1)/2-1和 n-1(D)n 2 和 n39. 若在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是（）。2(A) O(1)(B)O(n 2 )(C)O(nlog n)(D)O(n)40. 在一个头结点为head 的空循环链表中插入一个结点s，则指针s 应执行操作（）。(A)head-next=s;s-next=NULL; (B)s-next=head;head-next=NULL;(C)head-next=s;s-next=head-next;(D)s-next=head;head-next=s;41. 设链队列Q 的头指

15、针和尾指针分别为front 和 rear ，队中元素个数为n(n1) ， 指针 *p 指向队首元素m。若删除元素m，则应进行的指针操作为（）。(A) Q-front-next=p-next(B)Q-rear=Q-front(C)Q-front=p-rear(D)Q-rear=p-next42. 假设二叉树T 中有 n 个叶子结点，且所有非叶子结点都有左、右子树，那么二叉树 T 共有（）个结点。(A)2n(B)2n-1(C)2n+1(D)2n+243. 已知有向图G 的邻接矩阵如下所示，则下列序列中（）不可能是图G 的拓扑序列。(A)v1,v6,v3,v4,v2,v5(B)v1,v6,v4,v3

16、,v2,v5(C)v1,v3,v2,v4,v6,v5(D)v1,v3,v6,v4,v5,v201110000000001001000001000000000011044. 已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下表所示，则该二叉树的后序遍历序列为（）。123456789101112131415161718192021EAFDGCJIHB (A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH45. 若 T 为 n 个结点的完全二叉树，则T 的叶子结点数为（）。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/2

17、46. 有一组数值14,21,32,15,28，用以构造huffman树，则其WPL 值为（）。(A)267(B)189(C)110(D)29447. 采用折半插入排序，关键字的比较次数与移动次数分别为（）。(A) O(n),O(log2n)(B)O(n 2),O(log 2n)(C)O(log 2 n),O(n 2)(D)O(nlog 2 n),O(n 2 )48 假设结点序列为60,30,90,50,95,70,40,80，以此构成一棵二叉排序树，则在该二叉排序树上查找一个结点的平均查找长度为（）。(A)23/8(B)11/4(C)9/2(D)449. 下面程序段的时间复杂性的量级为（D）

18、。for(i=1;i n; i+) for(j=1;j m; j+)cij=0;for(k=1;k w;k+) cij+=aik*bkj(A) O(i*j*k)(B)O(n*m*k)(C)O(n*j*k)(D)O(n*m*w)50. 在一个长度为n 的线性表中， 删除值为 x 的元素时需要比较元素和移动元素的总次数为（C）。(A) （ n+1 ） /2(B)n/2(C)n(D)n+151. 利用 3， 6， 8， 12 ，5， 7 这六个值作为叶子结点的权，生成一棵哈夫曼树， 该树的深度为（B ） 。(A)3(B)4(C)5(D)652. 一棵二叉树的广义表表示为a(b(c,d),e(,f(g

19、),则得到的层次遍历序列为（ D）。(A) a,b,c,d,e,f,g(B)c,b,d,a,e,g,f(C)c,d,b,g,f,e,a(D)a,b,e,c,d,f,g53. 若长度为n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（）。(1 in+1)(A)O(0)(B)O(1)(C)O(n)(D)O(n2)54. 若在线性表中采用折半查找法查找元素，该线性表应该（）。(A) 元素按值有序(B) 采用顺序存储结构(C) 元素按值有序，且采用顺序存储结构(D) 元素按值有序，且采用链式存储结构55. 已知一算术表达式的中缀形式为AB *C-D/E ，后缀形式为A

20、BC *+DE/-，其前缀形式为（）。(A) A+B*C/DE(B) A+B*CD/E (C)-+*ABC/DE(D)-+A*BC/DE56. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。(A) 前序(B) 中序(C) 后序(D) 按层次57. 对二叉排序树进行（）遍历，可以得到该二叉树所有结点构成的排序序列。(A) 前序(B) 中序(C) 后序(D) 按层次58. 具有 n 个顶点的有向图最多有（）条边。(A)n(B)n(n 1)C n(n+1)(D)n259. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序

21、列的合适位置，该排序方法称为（）排序法。(A) 插入(B) 选择(C)shell(D) 二路归并60. 排序趟数与序列的原始状态有关的排序方法是（）排序法。(A) 插入(B) 选择(C) 冒泡(D) 快速61. 下面给出的四种排序法中（）排序法是不稳定性排序法。(A) 插入(B) 冒泡(C) 二路归并(D) 堆62. 一个对象序列的排序码为46 ， 79 ， 56， 38 ， 40， 84 ，采用快速排序以位于(A)38 ， 46 ，79 ， 56， 40， 84(B)38 ， 79， 56， 46 ，40 ， 84(C)40 ， 38， 46 ， 56， 79， 84(D)38 ， 46 ，

22、56 ， 79， 40 ，84 线性链表不具有的特点是（）。(A) 随机访问(B) 不必事先估计所需存储空间大小(C) 插入与删除时不必移动元素(D) 所需空间与线性表长度成正比最左位置的对象为基准而得到的第一次划分结果为（）。6364. 设 F 是一个森林， B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则B中右指针域为空的结点有（）个。(A)n-1(B)n(C)n+1(D)n+265. 具有 65 个结点的完全二叉树的高度为（）。（根的层次号为0 ） (A)8(B)7(C)6(D)566. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用 （）方法比较次数最少。(A)

23、直接插入排序(B) 快速排序(C) 归并排序(D) 直接选择排序67. 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。(A)3(B)2(C)1(D)1/268. 对有 14 个数据元素的有序表R14 进行折半搜索，搜索到R3 的关键码等于给定值，此时元素比较顺序依次为（）。(A)R0 ，R1 ， R2 ， R3(B)R0 ， R13 ， R2 ，R3(C)R6 ， R2 ， R4 ，R3(D)R6 ， R4 ， R2 ，R369. 若度为 m 的哈夫曼树中 ,其叶结点个数为n, 则非叶结点的个数为（）。(A)(n+1)/(m+1)-1(B)n/m-1(C)(n-1)/(m-1)(D)

24、n/(m-1)-170. 下面关于算法说法错误的是（）。(A) 算法最终必须由计算机程序实现(B) 为解决某问题的算法同为该问题编写的程序含义是相同的(C) 算法的可行性是指指令不能有二义性(D) 以上几个都是错误的71. 以下与数据的存储结构无关的术语是（）。(A) 循环队列(B) 链表(C) 哈希表(D) 栈72. 以下数据结构中，哪一个是线性结构（）。(A) 广义表(B) 二叉树(C) 稀疏矩阵(D)串73. 以下那一个术语与数据的存储结构无关？（）(A) 栈(B) 哈希表(C) 线索树(D)双向链表74. 在下面的程序段中，对x 的赋值语句的频度为（）。FOR i:=1TOnDO FO

25、R j:=1TOnDOx:=x+1;(A) O(2n)(B)O(n)(C)O(n2)(D)O(log 2 n)75. 以下哪个数据结构不是多型数据类型（）。(A) 栈(B) 广义表(C) 有向图(D) 字符串76. 连续存储设计时，存储单元的地址（）。(A) 一定连续(B) 一定不连续(C) 不一定连续(D) 部分连续，部分不连续77. 一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（A ） 。(A)0(B)1(C)2(D) 不确定78. 设图 G 采用邻接表存储，则拓扑排序算法的时间复杂度是（B ） 。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)7

26、9. 下列排序算法中，时间复杂度为O(nlog2n) 且占用额外空间最少的是（A ） 。(A) 堆排序(B) 冒泡排序(C) 快速排序(D)SHELL排序80. 已知数据表A 中每个元素距其最终位置不远，则采用（B ）排序算法最节省时间。(A) 堆排序(B) 插入排序(C) 快速排序(D) 直接选择排序81. 串是（D）。(A) 不少于一个字母的序列(B) 任意个字母的序列(C) 不少于一个字符的序列(D) 有限个字符的序列82. 一个栈的输入序列为12345 ，则下列序列中是栈的输出序列的是（A ） 。(A)23415(B)54132(C)31245(D)1425383. 设循环队列中数组的

27、下标范围是1n ，其头尾指针分别为f 和 r，则其元素个数为（D）。(A) r-f(B)r-f+1(C)(r-f) mod n +1(D)(r-f+n) mod n84. 二叉树在线索化后，仍不能有效求解的问题是（D ） 。(A) 先序 线 索 二 叉 树中 求 先 序 后 继(B) 中 序 线 索 二 叉 树 中求 中 序 后 继(C) 中序线索二叉树中求中序前驱(D) 后序线索二叉树中求后序后继85. 求最短路径的FLOYD 算法的时间复杂度为（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)86. 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B ） 。(

28、A)0(B)1(C)2(D) 不确定87. 数组 A1.5,1.6的每个元素占5 个单元，将其按行优先顺序存储在起始地址为 1000 的连续的内存单元中，则元素A5,5 的地址为（A ） 。(A)1140(B)1145(C)1120(D)112588. 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ A ） 。(A) 快速排序(B) 希尔排序(C) 冒泡排序(D) 堆排序89 对有18个元素的有序表做折半查找，则查找A3 的比较序列的下标依次为（ D）。(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-390. 下列排序算法中，某一趟结束后未必能选出

29、一个元素放在其最终位置上的是（ D）。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 直接插入排序91. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知 A 的左孩子的平衡因子为-1 ，右孩子的平衡因子为0，则做（B ）型调整以使其平衡。(A) LL(B)LR(C)RL(D)RR92. 下列各式中，按增长率由小至大的顺序正确排列的是（）。n(A),n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n, logn, nlogn, n3/2(D)2100, logn, 2n, nn93. 若要在单链表中的结点*p 之后插入一个结点*s ，则应执行的

30、语句是（）。(A) s- next=p- next; p- next=s;(B) p- next=s; s- next=p- next(C) p- next=s- next; s- next=p; (D)s- next=p;p- next=s- next;94. 若要在 O（ 1 ）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）。(A) 各自的头结点(B) 各自的尾结点(C) 各自的第一个元素结点(D) 一个表的头结点，另一个表的尾结点95. 栈的两种常用存储结构分别为（）。(A) 顺序存储结构和链式存储结构(B) 顺序存储结构和散列存储结构(C) 链式

31、存储结构和索引存储结构(D) 链式存储结构和散列存储结构96. 已知循环队列的存储空间为数组data21 ，且当前队列的头指针和尾指针的值分别为 8 和 3 ，则该队的当前长度为（）。(A)5(B)6(C)16(D)1797. 已知在如下定义的链串结点中，每个字符占1 个字节，指针占4 个字节，则该链串的存储密度为（）。typedef struct node char date8;struct node * next; LinkStrNode;(A)1/4(B)1/2(C)2/3(D)3/498. 应用简单的匹配算法对主串s= “BDBABDABDAB”与子串t=“BDA ”进行模式匹配，在匹

32、配成功时，进行的字符比较总次数为（）。(A)7(B)9(C)10(D)1299. 二维数组A2010 采用列优先的存储方法，若每个元素占2 个存储单元，且第 1 个元素的首地址为200 ，则元素A89 的存储地址为（）。(A)574(B)576(C)578(D)580100. 对广义表L=(a,b),c,d) 进行操作tail (head (L)的结果是（）。(A)(c,d )(B)(d )(C)b(D)(b)101. 已知一棵树的前序序列为ABCDEF ，后序序列为CEDFBA ，则对该树进行层次遍历得到的序列为（）。(A) ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE

33、102. 一个含 n 个顶点和e 条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）。(A)O(n)(B)O(e)(C)O(n+e)(D)O(n2)103在关键字序列（12， 23 ， 34， 45 ， 56， 67 ， 78， 89 ， 91 ）中二分查找关键字为 45， 89 和 12 的结点时，所需进行的比较次数分别为（）。(A)4 ， 4， 3(B)4 ， 3， 3(C)3 ， 4 ，4(D)3 ， 3 ， 4104. 下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（）。(A) 冒泡排序(B) 直接选择排序(C) 堆排序(D) 归并排序105

34、. 已知含 10 个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）。(A)1.0(B)2.9(C)3.4(D)5.5106. 在下列各种文件中，不能进行顺序查找的文件是（）。(A) 顺序文件(B) 索引文件(C) 散列文件(D) 多重表文件107. 下面带有 标记的语句的频度(n10) 是（）。for(int i=0;in-1;i+)for(int j=i+1;jn;j+)coutijendl;(A)n*(n-1)/2(B)n*n/2(C) n*(n+1)/2(D) 不确定108. 已知使用顺序表存储数据，表长为n，假设在表中的任意位置插入元素的概

35、率相等，则插入一个元素，平均需要移动的元素个数（）。(A)(n-1)/2(B)n/2(C)(n+1)/2(D) 不确定109. 在双向链表p 所指结点之后插入s 所指结点的操作是（）。(A) p right=s;s left=p;p right left=s;s right=p right; (B)p right=s;p right left=s;s left=p;s right=p right; (C)s left=p;s right=p right;p right=s;p right left=s; (D)s left=p;s right=p right;p right left=s;p

36、right=s;110字符串相等的充分必要条件是（）。(A) 串长度相等(C) 串相同位置对应的字符相等(B) 串使用相同的存储结构(D)A 和 C111. 将一个递归算法改为对应的非递归算法时，通常需要使用（）。(A) 数组 (B)栈(C)队列 (D) 二叉树112. 一个栈的入栈序列1, 2, 3, 4, 5,则栈的不可能的输出序列是（）。(A) 12345(B)54321(C)32514(D)12354113. 设循环队列中数组的下标范围是1n ，其头尾指针分别为f 和 r，则其元素个数为（）。(A) r-f(B)r-f+1(C)(r-f) mod n +1(D)(r-f+n) mod

37、n114. 某二叉树的前序遍历结点访问顺序是ABDEFCGH,中序遍历的结点访问顺序是 DBFEAGHC,则其后序遍历的结点访问顺序是（）。(A) DFEBHCGA(B)DFEBHGCA(C)DEFBHGCA(D)DFEHBGCA115. 正则二叉树是只有度为0 和 2 的结点的二叉树，已知正则二叉树的叶子结点个数为n，则该二叉树总得结点数为（）。(A)n+1(B)2*n(C) 2*n+1(D)2*n-1116. 下面关于排序的说法错误的是（）。(A) 快速排序、归并排序都是一种不稳定的排序方法(B) 直接插入排序和折半插入排序移动元素的次数相同(C) 简单选择排序移动元素的次数最少(D) 根

38、据排序需要的平均时间，快速排序是目前最好的一种内部排序方法117折半查找有序表（3 ，4，5 ，10 ，13 ，14 ，20，30），若查找元素3 ，则被比较的元素依次为（）。(A)10,20,30(B)10,14,30(C)13,3(D)10, 4, 3118下面关于栈和队列的说法正确的是（）。(A) 栈是先进先出的线性表，队列是后进先出的线性表(B) 栈是先进先出的线性表，队列也是先进先出的线性表(C) 栈是后进先出的线性表，队列是先进先出的线性表(D) 栈是后进先出的线性表，队列也是后进先出的线性表119两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是（）。(A)n(B)2n

39、-1(C)2n(D)n-1120. 设循环队列中数组的下标范围是0 n-1 ， f 表示队首元素的前驱位置，r 表示队尾元素的位置，则队列中元素个数为（）。(A) r-f(B)r-f 1(C)(r-f 1)mod n(D)(r-f n)mod n121. 一个 5 行 6 列的二维数组s 采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a 中，s 和 a 的下标均从0 开始， 则 s33 在 a 中的下标是（）。(A)7(B)8(C)9(D)10122. 设只含根结点的二叉树的高度为1 ，则高度为n 的二叉树中所含叶子结点的个数最多为（）个。(A)2n(B)n(C)2n -1(D)

40、2n-1123. 设高度为h 的二叉树上只有度为0 和度为 2 的结点，则此二叉树中所包含的结点数至少为（）个（设只含根结点的二叉树的高度为1）。(A)2h(B)2h-1(C)2h+1(D)h+1124. 对一棵二叉检索树进行（） 得到的结点序列是一个有序序列。(A) 前序周游(B) 中序周游(C) 后序周游(D) 层次周游125. 一棵前序序列为1 ， 2 ，3， 4 的二叉树，其中序序列不可能是（） 。(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1126. 在含 n 个顶点和e 条边的有向图的邻接矩阵中，零元素的个数为（）。(A)e(B)2e(C)n2-e

41、(D)n2-2e127. 具有 n 个顶点和e 条边的图的深度优先搜索算法的时间复杂度为（）。(A)O(n)(B)O(n3)(C)O(n2)(D)O(n e)128. 如果具有n 个顶点的图是一个环，则它有（）棵生成树。(A) n(B)n l(C)n-l(D)2n129. 堆排序算法在平均情况下的时间复杂度为（）。(A) O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)130. 在待排序数据已基本有序的前提下，下述排序方法中效率最高的是（）。(A) 直接插入排序(B) 直接选择排序(C) 快速排序(D) 归并排序131. 在理想情况下，散列表中查找元素所需的比较次数为（）。(

42、A)n(B)O(C)n 2(D)1132. 在一棵 m 阶 B 树中，若在某结点中插入一个新关键字而引起该结点分裂， 则此结点中原有的关键字的个数是（）。(A)m(B)m +1(C)m-l(D)m 2133. 设顺序循环队列Q0 ： M-1 的头指针和尾指针分别为F 和 R，头指针F 总是指向队头元素的前一位置，尾指针R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。(A) R-F(B) F-R(C) (R-F+M) M(D) (F-R+M) M134. 设某棵二叉树的中序遍历序列为ABCD ，前序遍历序列为CABD ，则后序遍历该二叉树得到序列为（A ） 。(A) BADC(

43、B) BCDA(C) CDAB(D) CBDA135. 设某完全无向图中有n 个顶点，则该完全无向图中有（A ）条边。(A) n(n-1)/2(B) n(n-1)(C) n2(D) n2-1136. 设某棵二叉树中有2000 个结点，则该二叉树的最小高度为（C）。(A) 9(B) 10(C) 11(D) 12137. 设某有向图中有n 个顶点，则该有向图对应的邻接表中有（B ）个表头结点。(A) n-1(B) n(C) n+1(D) 2n-1138. 设一组初始记录关键字序列(5 ，2，6 ，3 ，8) ，以第一个记录关键字5 为基准进行一趟快速排序的结果为（C ） 。(A) 2 ，3 ， 5

44、 ，8， 6(B) 3 ，2 ， 5，8 ， 6(C) 3 ，2 ， 5， 6， 8(D) 2 ，3 ， 6， 5， 8139设某数据结构的二元组形式表示为A=(D ，R) ，D=01 ，02 ，03， 04 ， 05，06， 07 ，08 ， 09 ，R=r ， r= ， ， ， ， ， ， ， ，则数据结构A 是（B）。(A) 线性结构 (B)树型结构 (C) 物理结构 (D)图型结构140. 下面程序的时间复杂为（B ）for （ i=1 ， s=0 ； i=n ； i+） t=1 ；for(j=1 ； jnext； p-data=q-data；p-next=q-next； free(q

45、) ；(B) q=p-next； q-data=p-data； p-next=q-next； free(q) ；(C) q=p-next；p-next=q-next；free(q) ；(D) q=p-next；p-data=q-data； free(q) ；142. 设有n 个待排序的记录关键字，则在堆排序中需要（A）个辅助记录单元。(A) 1(B) n(C) nlog2n(D) n2143设一组初始关键字记录关键字为(20， 15 ，14，18 ，21，36 ，40 ，10) ，则以 20 为基准记录的一趟快速排序结束后的结果为（A ） 。(A) 10 ， 15 ，14 ， 18， 20 ，

46、 36 ，40 ， 21 (B) 10 ， 15 ，14 ， 18， 20， 40 ， 36， 21(C) 10 ， 15， 14 ， 20， 18， 40 ，36 ， 2l (D) 15 ， 10， 14 ， 18， 20， 36 ，40 ， 21144. 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ） 。(A) O(1) (B) O(log2n)(C) log2n(D) O(n2)145. 设无向图G 中有 n 个顶点 e 条边， 则其对应的邻接表中的表头结点和表结点的个数分别为（D ） 。(A) n ，e (B) e ，n (C) 2n ， e(D) n ， 2e

47、146. 设某强连通图中有n 个顶点，则该强连通图中至少有（C ）条边。(A) n(n-1)(B) n+1(C) n(D) n(n+1)147. 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录关键字，则用下列（B ）方法可以达到此目的。(A) 快速排序 (B)堆排序(C)归并排序 (D)插入排序148. 下列四种排序中（D ）的空间复杂度最大。(A) 插入排序 (B)冒泡排序 (C) 堆排序(D)归并排序149. 设一维数组中有n 个数组元素，则读取第i 个数组元素的平均时间复杂度为（C ） 。(A) O(n) (B) O(nlog2n)(C) O(1) (

48、D) O(n2)150. 设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。(A) 2k-1(B) 2k(C) 2k-1 (D) 2k-1151. 设某无向图中有n个顶点e 条边，则该无向图中所有顶点的入度之和为（ D）。(A) n(B) e(C) 2n(D) 2e152. 在二叉排序树中插入一个结点的时间复杂度为（B ） 。(A) O(1) (B) O(n) (C) O(log2n)(D) O(n2)153. 设某有向图的邻接表中有n 个表头结点和m 个表结点， 则该图中有 （ C ） 条有向边。(A) n(B) n-1(C) m(D) m-1154设一组初始记录关键字序列为(345

49、， 253 ， 674 ， 924 ， 627) ，则用基数排序需要进行（A ）趟的分配和回收才能使得初始关键字序列变成有序序列。(A) 3(B) 4(C) 5(D) 8155. 设用链表作为栈的存储结构则退栈操作（B ） 。(A) 必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别156. 下列四种排序中（A ）的空间复杂度最大。(A) 快速排序 (B)冒泡排序 (C) 希尔排序 (D)堆157. 设某二叉树中度数为0 的结点数为N 0，度数为 1 的结点数为N l，度数为 2的结点数为N2，则下列等式成立的是（C ） 。(A) N0=N1+1(B) N0

50、=Nl+N2(C) N0=N2+1( D) N0=2N1+l158. 设有序顺序表中有n 个数据元素，则利用二分查找法查找数据元素X 的最多比较次数不超过（A ） 。(A) log2n+1(B) log2n-1 ( C) log2n(D) log2(n+1)159. 数据的最小单位是（A ） 。(A) 数据项(B)数据类型 (C) 数据元素 (D)数据变量160设一组初始记录关键字序列为(50 ，40 ，95 ，20， 15 ，70，60 ，45)，则以增量 d=4 的一趟希尔排序结束后前4 条记录关键字为（B）。(A) 40 ， 50 ，20 ， 95(B) 15 ， 40 ， 60， 20

51、(C) 15 ， 20， 40 ， 45(D) 45 ， 40 ， 15， 20161设一组初始记录关键字序列为(25 ， 50， 15， 35 ，80 ， 85， 20， 40 ，36 ，70) ，其中含有5 个长度为2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（A ） 。(A) 15 ， 25 ， 35， 50 ， 20， 40 ， 80， 85， 36 ，70 (B) 15 ， 25 ， 35， 50 ， 80， 20 ， 85， 40， 70 ，36 (C) 15 ， 25 ，35 ， 50 ， 80， 85 ，20 ， 36， 40 ，70 (D) 15

52、 ， 25 ，35 ， 50 ， 80， 20 ，36 ， 40， 70 ，85162. 设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ） 。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)163. 设一棵 m 叉树中度数为0 的结点数为N 0，度数为 1 的结点数为Nl， 度数为 m 的结点数为Nm ，则 N0 =（ B ）。(A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm (C) N2+2N3+3N4+(m-1)Nm (D) 2Nl+3N2+(m+1)Nm164. 设有序表中有1000 个元素，则用二分查找查找元素X 最多需要比较 （ B ） 次。(A) 25(B) 10(C) 7(D) 1165设连通图G 中的边集E=(a ，b) ，(a，e) ，(a ，c) ，(b ，e) ，(e ，d) ，(d ，f)，(f， c)，则从顶点a 出发可以得到一种深度优先遍历的顶点序列为（B ） 。(A) abedfc(B) acfebd(C) aebdfc(D) a