考研数据结构易错选择题

1.最坏情况下 sort, quick sort ,merge sort 的复杂度分别是多少？

A. O(n*n),O(nlogn),O(n*n)

B. O(n*n),O(n*n),O(nlogn)

C. O(n*n),O(nlogn),O(nlogn)

D. O(nlogn),O(nlogn),O(nlogn)

答案：B

【解析】：

1：简单选择 最好时间 O(n^2) 平均时间O(n^2) 最坏时间 O(n^2)

2：直接插入 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)

3：冒泡排序 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)

4：希尔排序 最好时间 O(n) 平均时间O(logn) 最坏时间 O(n^s) 1

5：快速排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(n^2)

6：堆排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)

7：归并排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)

2.三个结点可以构成多少种二叉树（ ） A、5

B、6

C、7

D、4

答案：A

【解析】：3个结点的二叉树有5种形态：两层树：根左右；三层树： 根左（第二层）左（第三层）、根左（第二层）右（第三层）、根右（第二层）左（第三层）、根右（第二层）右（第三层）。

3.下列排序算法中，其中（ ）是稳定的

A、堆排序，冒泡排序

B、快速排序，堆排序

C、直接选择排序，希尔排序

D、归并排序，冒泡排序

答案：D

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。归并排序，冒泡排序，直接插入排序是稳定的。

4.3个不同的元素依次进栈，能得到（ ）种不同的出栈序列

A、4B、5C、6D、7

答案：B

出栈序列有：123，213，321，231，132

5.下面序列哪个不可能是二叉搜索时的后序遍历结果？

A. 1,2,3,4,5

B. 3,5,1,4,2

C. 1,2,5,4,3

D. 5,4,3,2,1

答案：B

【解析】二叉搜索树，用于搜索，因此 内部节点没有重复的元素 。另外， 满足二叉树的性质，左子树都比自己小，右子树都比自己大。 那么 可想而知，如果按照后序遍历，先左后右最后自己的顺序来遍历树，数组的最后一个元素肯定是自己（父节点），然后剩余的部分分成两个部分，第一部分都比自己小（左子树部分），第二部分都比自己大（右子树部分），因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。

6.对22 个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字

A、3B、4C、5D、6

答案：B

【解析】22 个记录的有序表，其折半查找的判定树深度为log2 (22) + 1=5 ，且该判定树不是满二叉树，即查找失败时至多比较5 次，至少比较4 次

7.假设利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top == -1 表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（ ）

A、a[--top] = x;

B、a[top--] = x;

C、a[++top] = x;

D、a[top++] = x;

答案：C

【解析】top == -1 表示栈空，top = 0时，还没有存值，所以得出结论：先指针加1，再赋值，即C。

8.在一个有向图中，所有顶点的度数之和等于所有弧数的（）倍

A、3

B、2

C、1

D、1/2

答案：B

【解析】有向图的某个顶点v，把以v为终点的边的数目，称为v的入度；以v为始点的边的数目，称为v的出度；v的度则定义为该顶点的入度和出度之和。显然，在一个有向图中，所有顶点的度数之和等于所有弧数的2倍。

9.已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是（ ）

I.普利姆算法

II.克鲁斯卡尔算法

III.图的广度优先搜索

A、仅 IB、仅 IIIC、仅 II 和 ID、I,II,III

答案：B

【解析】无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可以用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比算法更加高效。III正确。I 和 II 是最小生成树算法，也可直接排除

10.修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点， 则输出的顶点序列是 G 的：（ ）

A、拓扑有序序列

B、逆拓扑有序序列

C、广度优先搜索序列

D、深度优先搜索序列

答案：B

【解析】DFS 是一个递归算法,在遍历的过程中,先访问的点被压入栈底。拓扑有序是指如果点 U 到点 V 有一条弧,则在拓扑序列中 U 一定在 V 之前，深度优先算法搜索路径恰恰是一条弧，栈的输 出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点，所以是逆拓扑有序序列。

11.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。

A、单链表B、静态链表C、顺序表D、双链表

答案：B

【解析】静态链表的特点：不需要移动元素，只需要修改指针；需要一次性分配较大量空间，存储结构可以反应数据之间的逻辑关系。

12.若三叉树 T 中有 244 个结点（叶结点的高度为 1)， 则 T 的高度至少是( )

A、8

B、7

C、6

D、5

答案：C

【解析】

13.在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是（）

A．5

B．6

C．10

D．15

答案：D

【解析】关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根 据 4 阶 B 树的定义，根结点最少含 1 个关键字，非根结点中最少含（4/2）-1=1 个关键字，所 以每个结点中，关键字数量最少都为 1 个，即每个结点都有 2 个分支，类似与排序二叉树， 而 15 个结点正好可以构造一个 4 层的 4 阶 B 树，使得叶子结点全在第四层，符合 B 树定义，因此选 D。

14.一个具有8个顶点的连通无向图（没有自环），最多有（）条边

A. 28

B. 7

C. 26

D. 8

答案：A

【解析】无向连通图最少边为n-1，最多边为n*(n-1)/2

15.100个元素的排序数组分别进行二分查找和顺序查找，在查找失败的情况下，（ ）的比较次数较多

A、二分查找

B、顺序查找

C、一样多

D、不一定 答案：B

【解析】100个元素的排序数组分别进行二分查找和顺序查找，在查找失败的情况下，顺序查找最多比较100次，二分查找最多比较7次。

16.现有长度为 5，初始为空的散列表 HT，散列表函数 H(K)=(k+4)%5 用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT 中，然后删除关键字 25，则 HT 中查找失败的平均查找长度（）。

A、1

B、1.6

C、1.8

D、2.2

答案：C

【解析】

17.设F 是一个森林， B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针域为空的结点有（ ）个 A、n- 1B、nC、n + 1D、n + 2

答案：C

【解析】森林转换为二叉树,"兄弟相连、长兄为父、孩子靠左、头根为根 "，F有n个非终端节点,所以转换为二叉树后所有的空的右指针域就是n个根节点没有兄弟,根结点的右指针域也为空，二叉树中右指针域为空的节点有(n+1)个。

18.对于无向图G=(V,E)，下列选项中， 正确的是（）

A、当 IVl ＞IEI时， G 一定是连通的

B、当 IVl < IEI时， G 一定是连通的

C、当 IVl = IEl-1 时，G 一定是不连通的

D、当 IVl > IEl+1 时，G 一定是不连通的

答案：D

【解析】

19.以下属于逻辑结构的是（ ）

A、顺序表B、哈希表C、有序表D、单链表

答案：C

【解析】有序表是表中元素有顺序，并没有具体要求如何存取，所以是逻辑结构

20.在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3,4,5,6,8,10，为 S 构造的哈夫曼树的加权平均长度为（ ）

A、2.4

B、2.5

C、2.67

D、2.75

答案：B

【解析】构建哈夫曼树：

每个关键字的查找长度为：

注意，题目要求求加权平均长度，这里的权重就是频次。

加权平均长度为(3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5。

如果不考虑权重，会错误计算为(3+3+3+3+2+2)/6≈2.67，从而误选C。

本题选B。

21.在二路归并排序中归并的趟数是。

A. n

B. log2n

C. log2n+1

D. n2

答案:B

22.n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？

A. m-n

B. m-n+1

C. m-n-1

D. m-2n

答案：B

【解析】n个顶点的树一定有n-1条边，所以需要去掉m-(n-1)=m-n+1条边

23.广义表(a,b,c)的表尾是（ ）

A. b,c B. (b,c)C. cD. (c)

答案：B

24.在一个具有n个顶点的有向图中，构成强连通图时至少有 条边。

A. n

B. n +1

C. n - 1

D. n/2

答案：A

【解析】边数最少的有向强连通图是一个环,其边数=n

25.设串长为n，模式串长为m，则KMP算法所需的附加空间为（）

A. O(m)B. O(n)C. O(m*n)D. O()

答案：A

26.已知字符串S为“”，模式串t为“”。采用KMP算法进行匹配，第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，则下次开始匹配时，i和j的值分别是（ ）

A. i = 1, j = 0

B. i = 5, j = 0

C. i = 5, j = 2

D. i = 6, j = 2

答案：C

【解析】第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，隐藏含义是主串和模式串下标都从0开始，这个条件非常重要。

方法一：计算 next 数组后模拟

第一步：计算出模式串的next数组。

本人自编口诀优化前的next数组：第一格负一，第二格零，前缀等于后缀取最长。

这里由于主串和模式串下标都从0开始，没必要用优化后的next数组求解。优化后的next数组增加的1和下标都从0开始相比下标都从1开始减少的1正好相抵。

第二步：遍历主串对模式串进行匹配。

第一次匹配在模式串下标为5的位置出现失配，找到之前匹配的子串为abaab，最长相同前缀与后缀为ab，将前缀的ab移动到后缀ab的位置。

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，已匹配字符数为5，移动位数 = 已匹配字符数 - 失配位置对应的匹配值= 5 - 2 = 3。模式串向后移动3格，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，j指针直接跳转到模式串下标为2的位置，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

本题选C。

方法三：贪心

贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，从失配位置开始重新进行匹配，很容易看到i = 5, j = 2。

本题选C。

补充本人对本题完整KMP匹配过程的模拟。

27.折半搜索与二叉排序树的时间性能（）

A、相同

B、完全不同

C、有时不相同

D、数量级都是O(log 2n)

答案:C

【解析】二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系，但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的。

只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。

28.现有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）

A. 根结点的度一定为2

B. 树中最小元素一定是叶结点

C. 最后插入的元素一定是叶结点

D. 树中最大元素一定是无左子树

答案：D

【解析】A选项中，根结点的度不一定为2，A错误。

B选项中，一棵平衡二叉树是一棵二叉搜索树，由于中序遍历可得到一个降序序列，树中最小元素一定是最右结点，即无右子树，但可能有左子树，所以不一定是叶结点，B错误。

C选项中，AVL树的插入分两步，第一步是按照二叉搜索树的规则插入元素，该元素此时是叶结点，第二步是调整二叉搜索树为AVL树，如果此时二叉搜索树不平衡，需要进行旋转，旋转后该元素所在结点不一定是叶结点，C错误。

D正确。故本题选D。

29.采用共享栈的好处是（ ）

A、减少存取时间，降低发生上溢的可能

B、节省存储空间，降低发生上溢的可能

C、减少存取时间，降低发生下溢的可能

D、节省存储空间，降低发生下溢的可能

答案：B

【解析】与普通顺序栈相比，他们的存取时间都是O(1)，随机存取，好处是节省了存储空间，两个站一起使用空间，利用率更高；因为一次可以申请更大空间，所以上溢的可能性降低，下溢肯定是不变的，没元素了还出元素，就是下溢。

30.已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a,b,c,d,e,f，后根遍历序列是 b,a,d,f,e,c 则 T 的后遍历序列是：（ ）

A、b,a,d,f,e,c

B、b,d,f,e,c,a

C、b,f,e,d,c,a

D、f,e,d,c,b,a

答案：C

【解析】森林的先根遍历对应它自己转化后二叉树的先序遍历，森林的后根遍历对应它自己转化后 二叉树的中序遍历，所以先根和后根可以唯一确定森林转化后的二叉树，如下：

后序遍历为：b,f,e,d,c,a

31.设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不超过（ ）。

(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)

答案：A

32.引入二叉线索树的目的是（ ）

A、加快查找结点的前驱或后继的速度

B、为了能在二叉树中方便的进行插入与删除

C、为了能方便的找到双亲

D、使二叉树的遍历结果唯一

答案：A

【解析】以二叉链表作为存储结构时，只能得到节点的左右孩子信息，结点的任意序列中的前驱和后继信息只能在遍历的动态过程中才能得到，为了查找结点的前驱或后继，引入线索二叉树。

33.下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是？

A. 哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)

B. 线性表实现相对比较简单

C. 平衡二叉树的各项操作的时间复杂度为O(log(n))

D. 平衡二叉树的插入节点比较快

答案：D

【解析】哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树

34.一颗完全二叉树第六层有8个叶结点（根为第一层），则结点个数最多有（）个

A. 39

B. 72

C. 104

D. 111

答案：D

【解析】二叉树第k层最多有2的(k-1)次方个节点

第六层最多有32个节点

第五层最多有16个节点

第四层最多有8个节点

第三层最多有4个节点

第二层最多有2个节点

第一层最多有1个节点

完全二叉树的叶节点只可能出现在后两层

如果完全二叉树有6层，则前5层是满二叉树，总节点数目为16+8+4+2+1+8=39

如果完全二叉树有7层，则前6层是满二叉树，

前六层总节点数目为32+16+8+4+2+1=63

第六层有8个叶子节点，则有32-8=24个非叶子节点

第七层最多有24*2个叶子节点

总节点数目为63+24*2=111

35.修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点， 则输出的顶点序列是 G 的：（ ）

A、拓扑有序序列

B、逆拓扑有序序列

C、广度优先搜索序列

D、深度优先搜索序列

答案：B

【解析】DFS 是一个递归算法,在遍历的过程中,先访问的点被压入栈底。拓扑有序是指如果点 U 到点 V 有一条弧,则在拓扑序列中 U 一定在 V 之前，深度优先算法搜索路径恰恰是一条弧，栈的输 出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点，所以是逆拓扑有序序列。

36.在一棵深度为h的完全二叉树中，所含结点个数不大于（ ）

A、2^h

B、2^(h+1)

C、2^h-1

D、2^(h-1)

答案：C

【解析】在一棵深度为h的完全二叉树中，所含结点个数不大于2^h -1。回答此题可以用实例来验证，例如当h=2时，完全二叉树最多有3个结点。

37.在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（）

A.5

B. 7

C. 8

D. 14

答案：A

【解析】一棵高度为 2 的 5 阶 B 树，根结点只有到达 5 个关键字的时候才能产生分裂，成为高度为 2 的 B 树。

38.下列关于非空 B 树的叙述中，正确的是（ ）

①插入操作可能增加树的高度

②删除操作一定会导致叶结点的变化

③查找某关键字一定是要查找到叶结点

④插入的新关键字最终位于叶结点中

A、仅 1

B、仅 12

C、仅 34

D、仅 124

答案：B

【解析】I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高度加一。I 正确。

II.如果删除的关键字位于叶结点：

在叶结点中删除该关键字，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果删除该结点后关键字个数 n≥⌈m/2⌉−1，没有后续操作，如果该结点删除关键字后关键字个数 n