数据结构基础题型

第一章 绪论

【考频】7/17

【考纲内容】
（一）数据结构的基本概念
（二）算法的基本概念
   算法的时间复杂度和空间复杂度

1. (2011) 设n是描述问题规模的非负整数，下列程序段的时间复杂度是 ( )。

x=2;
while(x<n/2)
  x=2*x;

A. O(log₂n)B. O(n)C. O(nlog2n)D. O(n²)

2. (2012) 求整数n（n≥0）的阶乘的算法如下，其时间复杂度是 ( )。

int fact(int n){
  if(n<=l) return 1;
  return n*fact(n-l);
}

A. O(log₂n)B. O(n)C. O(nlog2n)D. O(n²)

3. (2014) 下列程序段的时间复杂度是 ( )。

count=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=n;j++)
    count++;

A. O(log₂n)B. O(n)C. O(nlog2n)D. O(n²)

4. (2017) 下列函数的时间复杂度是 ( )。

int func(int n){
  int i=0, sum=0;
  while(sum<n) sum += ++i;
  return i;
}

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(nlog₂n)

5. (2019) 设n是描述问题规模的非负整数，下列程序段的时间复杂度是 ( )。

x=0;
while(n>=(x+1)*(x+1))
  x=x+1;

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(n²)

6. (2022) 下列程序段的时间复杂度是 ( )。

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(n²)

【分析】

算法复杂度描述，关键语句的执行次数t和问题规模n的关系。

	第1轮	第2轮	第3轮	...	第log2n轮
i	1	2	4	...	$\frac{n}{2}$
j	0	0,1	0,1,2,3	...	0,1,2,...,$\frac{n}{2}$-1
t	1	2	4	...	$\frac{n}{2}$

知道每轮的执行次数t，以及共有多少轮log₂n。所有轮循环的执行次数总和：t=(1+2+4+...+$\frac{n}{2}$)，形成log₂n项等比数列求和：

$$t=(1+2+4+\cdots +\frac{n}{2})=\frac{a_1(1-q^n)}{1-q}=\frac{1\times (1-2^{lo{g}_{2}n})}{1-2}=n.$$

---

7. (2025) 下列程序段的时间复杂度是 ( )。

A. O(log₂n)B. O(n^1/2)C. O(n)D. O(n²)

【分析】

	第1轮	第2轮	第3轮	...	第log2n轮
i	1	2	3	...	$\sqrt{n}$
j	1	1,2	1,2,3	...	1,2,3,...,$\sqrt{n}$
t	1	2	3	...	$\sqrt{n}$

$$t=(1+2+3+\cdots +\sqrt{n})=\frac{(1+\sqrt{n})\sqrt{n}}{2}=n.$$

---

第二章 线性表

【考频】5/17

【考纲内容】
（一）线性表的基本概念
（二）线性表的实现
   顺序存储；链式存储
（三）线性表的应用

1. (2023) 在下列对顺序存储的有序表（长度为n）实现给定操作的算法中，平均时间复杂度为O(1)的是 ( )。

A. 查找包含指定值元素的算法B. 插入包含指定值元素的算法

C. 删除第i (1≤i≤n) 个元素的算法D. 获取第i (1≤i≤n) 个元素的算法

2. (2016) 已知一个带有表头结点的循环双链表L，结点结构为，其中prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是 ( )。

A. p->next->prev=p->prev; p->prev->next=p->prev; free(p);

B. p->next->prev=p->next; p->prev->next=p->next; free(p);

C. p->next->prev=p->next; p->prev->next=p->prev; free(p);

D. p->next->prev=p->prev; p->prev->next=p->next; free(p);

3. (2016) 已知表头元素为c的单链表在内存中的存储状态如下表所示。

现将f存放于1014H处并插入单链表，若f在逻辑上位于a和e之间，则a、e、f的“链接地址”依次是 ( )。

A. 1010H、1014H、1004HC. 1014H、1010H、1004H

B. 1010H、1004H、1014HD. 1014H、1004H、1010H

4. (2021) 已知头指针h指向一个带头结点的非空循环单链表，结点结构为其中next是指向直接后继结点的指针，p是尾指针，g是临时指针。现要删除该链表的第一个元素，正确的语句序列是 ( )。

A. h->next=h->next->next;q=h->next;free(q);

B. q=h->next;h->next=h->next->next;free(q);

C. q=h->next;h->next=q->next;if(p!=q) p=h;free(q)

D. q=h->next;h->next=q->next;if(p==q) p=h;free(q);

5. (2023) 现有非空双链表L，其结点结构为，prev是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在工中指针p所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行语句序列“s->next=p->next;p->next=s;”后，下列语句序列中还需要执行的是 ( )。

A. s->next->prev=p; s->prev=p;

B. p->next->prev=s; s->prev=p;

C. s->prev=s->next->prev; s->next->prev=s;

D. p->next->prev=s->prev; s->next->prev=p;

6. (2024) 已知带头结点的非空单链表L的头指针为h，结点结构为其中next是指向直接后继结点的指针。现有指针p和q，若p指向L中非首且非尾的任意一个结点，则执行语句序列“q=p->next；p->next=q->next；q->next= h->next; h->next=q;”的结果是 ( )。

A. 在P所指结点后插入g所指结点B. 在g所指结点后插入P所指结点

C. 将P所指结点移至工的头结点之后D. 将g所指结点移动到L的头结点之后

第三章 栈、队列和矩阵

【考频】14/17

【考纲内容】
（一）栈和队列的基本概念
（二）栈和队列的顺序存储结构
（三）栈和队列的链式存储结构
（四）多维数组的存储
（五）特殊矩阵的压缩存储
（六）栈、队列和数组的应用

1. (2009) 设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后，立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 ( )。

A. 1B. 2C. 3D. 4

2. (2010) 若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是 ( )。

A. dcebfaB. cbdaefC. bcaefdD. afedcb

3. (2011) 元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 ( )。

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

4. (2013) 一个栈的入栈序列为1,2,3,…,n，出栈序列是P1,P2,P3,…,Pn。若P2=3，则P3可能取值的个数是 ( )。

A. n-3B. n-2C. n-1D. 无法确定

5. (2020) 对空栈S进行Push和Pop操作，入栈序列为a,b,c,d,e，经过Push、Push、Pop、Push、Pop、Push、Push、Pop操作后得到的出栈序列是 ( )。

A. b,a,cB. b,a,eC. b,c,aD. b,c,e

6. (2022) 给定有限符号集S，in和out均为S中所有元素的任意排列。对于初始为空的栈ST，下列叙述中，正确的是 ( )。

A. 若in是ST的入栈序列，则不能判断out是否为其可能的出栈序列

B. 若out是ST的出栈序列，则不能判断in是否为其可能的入栈序列

C. 若in是ST的入栈序列，out是对应in的出栈序列，则in与out一定不同

D. 若in是ST的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序

7. (2025) 己知算法A用于检查字符串中各类括号是否匹配，A执行过程中使用初始为空的栈保存遇到的括号。若栈的容量是3，则下列选项中，A不能处理的是 ( )。

A. (a+[b+(c+d)/e]+f)+g−hB. [a*((b+c)/(d-e)+f/g)−h]

C. [a*(b−(c−d)*e/(f+g))−h]D. [a−(b+[c*(d+e)−f]+g+h)]

8. (2012) 已知操作符包括“+”、“-”、“*”、“/”、“(”和“)”。将中缀表达式 a+b-a*c+d/e-f+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符。栈初始时为空时，转换过程中同时保存在栈中的操作符的最大个数是 ( )。

A. 5B. 7C. 8D. 11

9. (2014) 假设栈初始为空，将中缀表达式 a/b+cd-ef/g 转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是 ( )。

A. +(*-B. +(-*C. /+(*-*D. /++*

10. (2015) 已知程序如下：

int S(int n) { return (n<=0) ? 0: S(n-1)+n; }
void main() { cout << S(1); }

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是 ( )。

A. main→S(1)→S(0)B. S(0)→S(1)→main

C. main→S(0)→S(1)D. S(1)→S(0)→main

11. (2016) 设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为1~9，则n至少是 ( )。

A. 2B. 3C. 4D. 5

12. (2017) 下列关于栈的叙述中，错误的是 ( )。

Ⅰ. 采用非递归方式重写递归程序时必须使用栈

Ⅱ. 函数调用时，系统要用栈保存必要的信息

Ⅲ. 只要确定了入栈次序，即可确定出栈次序

Ⅳ. 栈是一种受限的线性表，允许在其两端进行操作

A. 仅ⅠB. 仅Ⅰ、Ⅱ、ⅢC. 仅Ⅰ、Ⅲ、ⅣD. 仅Ⅱ、Ⅲ、Ⅳ

13. (2010) 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是 ( )。

A. b,a,c,d,eB. d,b,a,c,eC. d,b,c,a,eD. e,c,b,a,d

14. (2011) 已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 ( )。

A. 0,0B. 0,n-1C. n-1,0D. n-1,n-1

15. (2014) 循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是 ( )。

A. 队空: end1 == end2；队满: end1 == (end2+1) mod M

B. 队空: end1 == end2；队满: end2 == (end1+1) mod (M-1)

C. 队空: end2 == (end1+1) mod M；队满: end1 == (end2+1) mod M

D. 队空: end1 == (end2+1) mod M；队满: end2 == (end1+1) mod (M-1)

16. (2018) 现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是 ( )。

A. 1,2,5,6,4,3B. 2,3,4,5,6,1C. 3,4,5,6,1,2D. 6,5,4,3,2,1

17. (2021) 初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是 ( )。

A. 5,4,3,1,2B. 5,3,1,2,4C. 4,2,1,3,5D. 4,1,3,2,5

18. (2009) 为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 ( )。

A. 栈B. 队列C. 树D. 图

19. (2016) 有一个100阶的三对角矩阵M，其元素m_i,j（1≤i,j≤100）按行优先依次压缩存入下标从0开始的一维数组N中。元素m_30,30在N中的下标是 ( )。

A. 86B. 87C. 88D. 89

20 (2017) 适用于压缩存储稀疏矩阵的两种存储结构是 ( )。

A. 三元组表和十字链表

B. 三元组表和邻接矩阵

C. 十字链表和二叉链表

D. 邻接矩阵和十字链表

21. (2018) 设有一个12×12的对称矩阵M，将其上三角部分的元素m_i,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m_6,6在N中的下标是 ( )。

A. 50B. 51C. 55D. 66

22. (2020) 将一个10×10对称矩阵M的上三角部分的元素m_i,j（1≤i≤j≤10）按列优先存入C语言的一维数组N中，元素m_7,2在N中的下标是 ( )。

A. 15B. 16C. 22D. 23

23. (2021) 二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是 ( )。

A. 295B. 300C. 301D. 306

24. (2023) 若采用三元组表存储结构存储稀疏矩阵M，则除三元组表外，下列数据中还需要保存的是 ( )。

Ⅰ. M的行数 Ⅱ. M中包含非零元素的行数

Ⅲ. M的列数 Ⅳ. M中包含非零元素的列数

A. 仅Ⅰ、ⅢB. 仅Ⅰ、ⅣC. 仅Ⅱ、ⅣD. Ⅰ、Ⅱ、Ⅲ、Ⅳ

第四章 串

【考频】3/17

【考纲内容】
  字符串模式匹配

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

A. i = 1, j = 0B. i = 5, j = 0C. i = 5, j = 2D. i = 6, j = 2

2. (2019) 设主串T='abaabaabcabaabc'，模式串S='abaabc'，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是 ( )。

A. 9B. 10C. 12D. 15

3. (2024) KMP算法使用修正后的next数组进行模式匹配，模式串为S='aabaab'，当主串的某个字符与S的某个字符失配时，S向右滑动的最长距离是 ( )。

A. 5B. 4C. 3D. 2

第五章 树

【考频】17/17

【考纲内容】
（一）树的基本概念
（二）二叉树
   二叉树的定义及其主要特征；二叉树的顺序存储结构和链式存储结构；
   二叉树的遍历；线索二叉树的基本概念和构造
（三）树、森林
   树的存储结构；森林与二叉树的转换；树和森林的遍历
（四）树与二叉树的应用
   哈夫曼（Huffman）树和哈夫曼编码；并查集及其应用；堆及其应用

1. (2009) 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是 ( )。

A. 39B. 52C. 111D. 119

2. (2010) 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是 ( )。

A. 41B. 82C. 113D. 122

3. (2011) 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是 ( )。

A. 115B. 116C. 1895D. 1896

4. (2011) 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是 ( )。

A. 257B. 258C. 384D. 385

5. (2018) 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是 ( )。

A. 2k-1B. 2kC. k²D. 2^k-1

6. (2020) 对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是 ( )。

A. 31B. 16C. 15D. 10

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

A. 8B. 7C. 6D. 5

8. (2025) 若二叉树的结点值均为正整数，采用顺序存储方式保存在数组R中，用-1表示结点不存在，则下列数组中，不能表示一棵二叉树的是 ( )。

A. R[]={20, 15, 40, −1, −1, 35}B. R[]={15, 40, 10, 18, 35, −1, −1}

C. R[]={15, 40, 10, −1, −1, −1, 12}D. R[]={17, 20, 35, −1, 18, 45, −1, −1, 19, 27}

9. (2009) 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3175624，则其遍历方式是 ( )。

A. LRNB. NRLC. RLND. RNL

10. (2011) 一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，该二叉树的中序遍历序列不会是 ( )。

A. 1,2,3,4B. 2,3,4,1C. 3,2,4,1D. 4,3,2,1

11. (2012) 若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点 ( )。

A. 只有eB. 有e、bC. 有e、cD. 无法确定

12. (2015) 先序序列为a, b, c, d的不同二叉树的个数是 ( )。

A. 13B. 14C. 15D. 16

13. (2017) 某二叉树的树形如下图所示，其后序序列为e,a,c,b,d,g,f，树中与结点a同层的结点是 ( )。

A. cB. dC. fD. g

14. (2017) 要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是 ( )。

A. 只有左子树B. 只有右子树C. 结点的度均为1D. 结点的度均为2

15. (2022) 若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是 ( )。

Ⅰ. q是p的双亲 Ⅱ. q是p的右孩子

Ⅲ. q是p的右兄弟 Ⅳ. q是p的双亲的双亲

A. 仅ⅠB. 仅ⅢC. 仅Ⅱ、ⅢD. 仅Ⅱ、Ⅳ

16. (2023) 已知一棵二叉树的树形如下图所示，若其后序遍历序列为f,d,b,e,c,a，则其先序遍历序列是 ( )。

A. a,e,d,f,b,cB. a,c,e,b,d,fC. c,a,b,e,f,dD. d,f,e,b,a,c

17. (2024) 若p、q和v均为二叉树T中的结点，v有两个孩子结点，T的中序遍历序列形如“..., p, v, q,...”，则在下列叙述中，正确的是 ( )。

A. p没有右孩子，q没有左孩子B. p没有右孩子，q有左孩子

C. p有右孩子，q没有左孩子D. p有右孩子，q有左孩子

18. (2010) 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是 ( )。

19. (2013) 若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是 ( )。

A. X的父结点B. 以Y为根的子树的最左下结点

C. X的左兄弟结点YD. 以Y为根的子树的最右下结点

20 (2014) 若对下图所示的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是 ( )。

A. e,cB. e,aC. d,cD. b,a

21. (2009) 将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是 ( )。

Ⅰ. 父子关系

Ⅱ. 兄弟关系

Ⅲ. u的父结点与v的父结点是兄弟关系

A. 只有ⅡB. Ⅰ和ⅡC. Ⅰ和ⅢD. Ⅰ、Ⅱ和Ⅲ

22. (2014) 将森林F转换为对应的二叉树T，F中叶结点的个数等于 ( )。

A. T中叶结点的个数B. T中度为1的结点个数

C. T中左孩子指针为空的结点个数D. T中右孩子指针为空的结点个数

23. (2016) 若森林F有15条边、25个结点，则F包含树的个数是 ( )。

A. 8B. 9C. 10D. 11

24. (2019) 若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是 ( )。

A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历

25. (2020) 已知森林F及与之对应的二叉树T，若F的先根遍历序列是a,b,c,d,e,f，中根遍历序列是b,a,d,f,e,c，则T的后根遍历序列是 ( )。

A. b,a,d,f,e,cB. b,d,f,e,c,aC. b,f,e,d,c,aD. f,e,d,c,b,a

26. (2021) 某森林F对应的二叉树为T，若T的先序遍历序列是a,b,d,c,e,g,f，中序遍历序列是b,d,a,e,g,c,f，则F中树的棵数是 ( )。

A. 1B. 2C. 3D. 4

27. (2010) n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是 ( )。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任意一个非叶结点的权值一定不小于下一层任意一个结点的权值

28. (2014) 5个字符有如下4种编码方案，不是前缀编码的是 ( )。

A. 01, 0000, 0001, 001, 1B. 011, 000, 001, 010, 1

C. 000, 001, 010, 011, 100D. 0, 100, 110, 1110, 1100

29. (2015) 下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是 ( )。

A. 24,10,5 和 24,10,7B. 24,10,5 和 24,12,7

C. 24,10,10 和 24,14,11D. 24,10,5 和 24,14,6

30. (2017) 已知字符集{a,b,c,d,e,f,g,h}，若各字符的哈夫曼编码依次是0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列0100011001001011110101的译码结果是 ( )。

A. acgabfhB. adbagbbC. afbeagdD. afeefgd

31. (2018) 已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6,3,8,2,10,4，则对应字符集中各字符的哈夫曼编码可能是 ( )。

A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01

C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 000

32. (2019) 对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是 ( )。

A. 56B. 57C. 58D. 60

33. (2021) 若某二叉树有5个叶结点，其权值分别为10, 12, 16, 21, 30，则其最小的带权路径长度(WPL)是 ( )。

A. 89B. 200C. 208D. 289

34. (2022) 对任意给定的含n(n>2)个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2。下列叙述中，正确的是 ( )。

A. T1与T2的结点数相同

B. T1的高度大于T2的高度

C. 出现频次不同的字符在T1中处于不同的层

D. 出现频次不同的字符在T2中处于相同的层

35. (2023) 在由6个字符组成的字符集S中，各字符出现的频次分别为3,4,5,6,8,10，为S构造的哈夫曼编码的加权平均长度为 ( )。

A. 2.4B. 2.5C. 2.67D. 2.75

第六章 图

【考频】17/17

【考纲内容】
（一）图的基本概念
（二）图的存储及基本操作
   邻接矩阵；邻接表；邻接多重表；十字链表
（三）图的遍历
   深度优先搜索；广度优先搜索
（四）图的基本应用
   最小（代价）生成树；最短路径；拓扑排序；关键路径

1. (2009) 下列关于无向连通图特性的叙述中, 正确的是 ( )。

Ⅰ. 所有顶点的度之和为偶数

Ⅱ. 边数大于顶点个数减1

Ⅲ. 至少有一个顶点的度为1

A. 只有ⅠB. 只有ⅡC. Ⅰ和ⅡD. Ⅰ和Ⅲ

2. (2010) 若无向图G=(V,E)中含有7个顶点, 要保证图G在任何情况下都是连通的, 则需要的边数最少是 ( )。

A. 6B. 15C. 16D. 21

3. (2017) 已知无向图G含有16条边, 其中度为4的顶点个数为3, 度为3的顶点个数为4, 其他顶点的度均小于3。图G所含的顶点个数至少是 ( )。

A. 10B. 11C. 13D. 15

4. (2022) 对于无向图G=(V,E), 下列选项中正确的是 ( )。

A. 当|V| > |E| 时, G 一定是连通的

B. 当|V| < |E| 时, G 一定是连通的

C. 当|V| = |E| - 1 时, G 一定是不连通的

D. 当|V| > |E| + 1 时, G 一定是不连通的

5. (2025) 下列关于图的叙述中，正确的是 ( )。

A. 有向图必存在入度为0的顶点

B. 有向无环图的拓扑有序序列存在且唯一

C. 各顶点的度均大于等于2的无向图必有回路

D. 可用BFS算法求出带权图中每一对顶点间的最短路径

6. (2013) 设图的邻接矩阵A如下所示, 各顶点的度依次是 ( )。

A. 1,2,1,2B. 2,2,1,1C. 3,4,2,3D. 4,4,2,2

7. (2024) 若无向图G=(V,E)的邻接多重表如下图所示, 则G中顶点b与d的度分别是 ( )。

A. 0,2B. 2,4C. 2,5D. 3,4

8. (2012) 对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历, 其算法的时间复杂度是 ( )。

A. O(n)B. O(e)C. O(n+e)D. O(ne)

9. (2013) 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是 ( )。

A. h,c,a,b,d,e,g,fB. e,a,f,g,b,h,c,dC. d,b,c,a,h,e,f,gD. a,b,c,d,h,e,f,g

10. (2015) 设有向图 G=(V,E)，顶点集 V={V₀, V₁, V₂, V₃}，边集 E={ <v₀, v₁>, <v₀, v₂>, <v₀, v₃>, <v₁, v₃> }。若从顶点 V₀ 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是 ( )。

A. 2B. 3C. 4D. 5

11. (2016) 下列选项中，不是下图深度优先搜索序列的是 ( )。

A. V₁, V₅, V₄, V₃, V₂B. V₁, V₃, V₂, V₅, V₄

C. V₁, V₂, V₅, V₄, V₃D. V₁, V₂, V₃, V₄, V₅

12. (2010) 对下图进行拓扑排序，可得不同拓扑序列的个数是 ( )。

A. 4B. 3C. 2D. 1

13. (2012) 下列关于最小生成树的叙述中，正确的是 ( )。

Ⅰ. 最小生成树的代价唯一

Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ. 使用Prim算法从不同顶点开始得到的最小生成树一定相同

Ⅳ. 使用Prim算法和Kruskal算法得到的最小生成树总不相同

A. 仅ⅠB. 仅ⅡC. 仅Ⅰ、ⅢD. 仅Ⅱ、Ⅳ

14. (2012) 对下图所示的有向带权图，若采用Dijkstra算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是 ( )。

A. d,e,fB. e,d,fC. f,d,eD. f,e,d

15. (2012) 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 ( )。

A. 存在，且唯一B. 存在，且不唯一

C. 存在，可能不唯一D. 无法确定是否存在

16. (2013) 下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是 ( )。

A. c和eB. d和cC. f和dD. f和h

17. (2014) 对下图所示的有向图进行拓扑排序，得到的拓扑序列可能是 ( )。

A. 3,1,2,4,5,6B. 3,1,2,4,6,5C. 3,1,4,2,5,6D. 3,1,4,2,6,5

18. (2015) 求下面的带权图的最小（代价）生成树时，可能是Kruskal算法第2次选中但不是Prim算法（从V4 开始）第2次选中的边是 ( )。

A. (V1, V3)B. (V1, V4)C. (V2, V3)D. (V3, V4)

19. (2011) 下列关于图的叙述中，正确的是 ( )。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路

A. 仅ⅡB. 仅Ⅰ、ⅡC. 仅ⅢD. 仅Ⅰ、Ⅲ

20. (2016) 使用Dijkstra算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是 ( )。

A. 5,2,3,4,6B. 5,2,3,6,4C. 5,2,4,3,6D. 5,2,6,3,4

21. (2016) 若对n个顶点、e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是 ( )。

A. O(n)B. O(n+e)C. O(n^2)D. O(ne)

22. (2018) 下列选项中，不是如下有向图的拓扑序列的是 ( )。

A. 1, 5, 2, 3, 6, 4B. 5, 1, 2, 6, 3, 4C. 5, 1, 2, 3, 6, 4D. 5, 2, 1, 6, 3, 4

23. (2019) 下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是 ( )。

A. 3 和7B. 12 和12C. 12 和14D. 15 和15

24. (2019) 用有向无环图描述表达式(x+y)((x+y)/x)，需要的顶点个数至少是 ( )。

A. 5B. 6C. 8D. 9

25. (2020) 已知无向图G如下所示，使用Kruskal算法求图G的最小生成树，加到最小生成树中的边依次是 ( )。

A. (b,f),(b,d),(a,e),(c,e),(b,e)B. (b,f),(b,d),(b,e),(a,e),(c,e)

C. (a,e),(b,e),(c,e),(b,d),(b,f)D. (a,e),(c,e),(b,e),(b,f),(b,d)

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

A. 拓扑有序序列B. 逆拓扑有序序列C. 广度优先搜索序列D. 深度优先搜索序列

27. (2020) 若使用AOE网估算工程进度，则下列叙述中正确的是 ( )。

A. 关键路径是从源点到汇点边数最多的一条路径

B. 关键路径是从源点到汇点路径长度最长的路径

C. 增加任意一个关键活动的时间不会延长工程的工期

D. 缩短任意一个关键活动的时间将会缩短工程的工期

28. (2021) 给定如下有向图，该图的拓扑有序序列的个数是 ( )。

A. 1B. 2C. 3D. 4

29. (2021) 使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2,3,4,5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新为 ( )。

A. 26, 3, 14, 6B. 25, 3, 14, 6C. 21, 3, 14, 6D. 15, 3, 14, 6

30. (2022) 下图是一个有10个活动的AOE网，时间余量最大的活动是 ( )。

A. cB. gC. hD. j

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

Ⅰ. Prim算法

Ⅱ. Kruskal算法

Ⅲ. 图的广度优先搜索算法

A. 仅ⅠB. 仅ⅢC. 仅Ⅰ、ⅡD. Ⅰ、Ⅱ、Ⅲ

第七章 查找

【考频】16/17

【考纲内容】
（一）查找的基本概念
（二）顺序查找法
（三）分块查找法
（四）折半查找法
（五）树形查找
   二叉搜索树；平衡二叉树；红黑树
（六）B树及其基本操作、B+树的基本概念
（七）散列（Hash）表
（八）查找算法的分析及应用

1. (2010) 已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是 ( )。

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

2. (2015) 下列选项中，不能构成折半查找中关键字比较序列的是 ( )。

A. 500, 200, 450, 180B. 500, 450, 200, 180C. 180, 500, 200, 450D. 180, 200, 500, 450

3. (2016) 在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。

k=0;
while(k<n 且 A[k]<x) k=k+3;
if(k<n 且 A[k]==x) 查找成功;
else if(k-1<n 且 A[k-1]==x) 查找成功;
else if(k-2<n 且 A[k-2]==x) 查找成功;
else 查找失败;

本算法与折半查找算法相比，有可能具有更少比较次数的情形是 ( )。

A. 当x不在数组中B. 当x接近数组开头处

C. 当x接近数组结尾处D. 当x位于数组中间位置

4. (2017) 下列二叉树中，可能成为折半查找判定树（不含外部结点）的是 ( )。

5. (2023) 对含600个元素的有序顺序表进行折半查找，关键字间的比较次数最多是 ( )。

A. 9B. 10C. 30D. 300

6. (2024) 下列数据结构中，不适合直接使用折半查找的是 ( )。

Ⅰ. 有序链表

Ⅱ. 无序数组

Ⅲ. 有序静态链表

Ⅳ. 无序静态链表

A. 仅Ⅰ、ⅢB. 仅Ⅱ、ⅣC. 仅Ⅱ、Ⅲ、ⅣD. Ⅰ、Ⅱ、Ⅲ、Ⅳ

7. (2009) 下列二叉排序树中，满足平衡二叉树定义的是 ( )。

8. (2010) 在下图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是 ( )。

A. 13, 48B. 24, 48C. 24, 53D. 24, 90

9. (2011) 对下列关键字序列，不可能构成某二叉排序树中一条查找路径的是 ( )。

A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,34

10. (2012) 若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为 ( )。

A. 12B. 20C. 32D. 33

11. (2013) 在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是 ( )。

Ⅰ. 若v是T1的叶结点，则T1与T3不同

Ⅱ. 若v是T1的叶结点，则T1与T3相同

Ⅲ. 若v不是T1的叶结点，则T1与T3不同

Ⅳ. 若v不是T1的叶结点，则T1与T3相同

A. 仅Ⅰ、IIIB. 仅Ⅰ、IVC. 仅ⅠⅠ、IIID. 仅ⅠⅠ、IV

12. (2013) 若将关键字1,2,3,4,5,6,7依次插入初始为空的平衡二叉树T，则T中平衡因子为0的分支结点的个数是 ( )。

A. 0B. 1C. 2D. 3

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

A. 根结点的度一定为2B. 树中最小元素一定是叶结点

C. 最后插入的元素一定是叶结点D. 树中最大元素一定是无左子树

14. (2018) 已知二叉排序树如下图所示，元素之间应满足的大小关系是 ( )。

A. x1 < x2 < x5B. x1 < x4 < x5C. x3 < x5 < x4D. x4 < x3 < x5

15. (2019) 在任意一棵非空平衡二叉树(AVL树)T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是 ( )。

Ⅰ. 若v是T1的叶结点，则T1与T3可能不相同

Ⅱ. 若v不是T1的叶结点，则T1与T3一定不相同

Ⅲ. 若v不是T1的叶结点，则T1与T3一定相同

A. 仅ⅠB. 仅ⅡC. 仅Ⅰ、ⅡD. 仅Ⅰ、Ⅲ

16. (2020) 下列给定的关键字输入序列中，不能生成如下二叉排序树的是 ( )。

A. 4, 5, 2, 1, 3B. 4, 5, 1, 2, 3C. 4, 2, 5, 3, 1D. 4, 2, 1, 3, 5

17. (2021) 给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是 ( )。

A. 16B. 20C. 23D. 25

18. (2024) 一棵二叉搜索树如下图所示，k1, k2, k3分别是对应结点中保存的关键字。子树T的任意一个结点中保存的关键字x满足的是 ( )。

A. x < k1B. x > k2C. k1 < x < k3D. k3 < x < k2

19. (2009) 下列叙述中，不符合m阶B树定义要求的是 ( )。

A. 根结点至多有m棵子树B. 所有叶结点都在同一层上

C. 各结点内关键字均升序或降序排列D. 叶结点之间通过指针链接

20 (2012) 已知一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，其最右叶结点中的关键字是 ( )。

A. 60B. 60, 62C. 62, 65D. 65

21. (2013) 在一棵高度为2的5阶B树中，所含关键字的个数至少是 ( )。

A. 5B. 7C. 8D. 14

22. (2014) 在一棵有15个关键字的4阶B树中，含关键字的结点个数最多是 ( )。

A. 5B. 6C. 10D. 15

23. (2016) B+树不同于B树的特点之一是 ( )。

A. 能支持顺序查找B. 结点中含有关键字

C. 根结点至少有两个分支D. 所有叶结点都在同一层上

24. (2017) 下列应用中，适合使用B+树的是 ( )。

A. 编译器中的词法分析B. 关系数据库系统中的索引

C. 网络中的路由表快速查找D. 操作系统的磁盘空闲块管理

25. (2018) 高度为5的3阶B树含有的关键字个数至少是 ( )。

A. 15B. 31C. 62D. 242

26. (2020) 依次将关键字5, 6, 9, 13, 8, 2, 12, 15插入初始为空的4阶B树后，根结点中包含的关键字是 ( )。

A. 8B. 6, 9C. 8, 13D. 9, 12

27. (2021) 在一棵高度为3的3阶B树中，根为第1层，若第2层中有4个关键字，则该树的结点数最多是 ( )。

A. 11B. 10C. 9D. 8

28. (2022) 在下图所示的5阶B树T中，删除关键字260之后需要进行必要的调整，得到新的B树T1。下列选项中，不可能是T1根结点中关键字序列的是 ( )。

A. 60, 90, 280B. 60, 90, 350C. 60, 85, 110, 350D. 60, 90, 110, 350

29. (2023) 下列关于非空B树的叙述中，正确的是 ( )。

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

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

Ⅲ. 查找某关键字总是要查找到叶结点

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

A. 仅ⅠB. 仅Ⅰ、ⅡC. 仅Ⅲ、ⅣD. 仅Ⅰ、Ⅱ、Ⅳ

30 (2011) 为提高散列表的查找效率，可以采取的正确措施是 ( )。

Ⅰ. 增大装填(载)因子

Ⅱ. 设计冲突(碰撞)少的散列函数

Ⅲ. 处理冲突(碰撞)时避免产生聚集(堆积)现象

A. 仅ⅠB. 仅ⅡC. 仅Ⅰ、ⅡD. 仅ⅠⅠ、Ⅲ

31. (2014) 用哈希（散列）方法处理冲突（碰撞）时，可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是 ( )。

A. 存储效率B. 散列函数C. 装填(装载)因子D. 平均查找长度

32. (2018) 现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22, 43, 15依次插入HT后，查找成功的平均查找长度是 ( )。

A. 1.5B. 1.6C. 2D. 3

33. (2019) 现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突。将关键字序列87, 40, 30, 6, 11, 22, 98, 20依次插入HT后，HT查找失败的平均查找长度是 ( )。

A. 4B. 5.25C. 6D. 6.29

34. (2022) 下列因素中，影响散列(哈希)方法平均查找长度的是 ( )。

Ⅰ. 装填因子

Ⅱ. 散列函数

Ⅲ. 冲突解决策略

A. 仅Ⅰ、ⅡB. 仅Ⅰ、ⅢC. 仅ⅠⅠ、ⅢD. Ⅰ、Ⅱ、Ⅲ

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

A. 1B. 1.6C. 1.8D. 2.2

第八章 排序

【考频】15/17

【考纲内容】
（一）排序的基本概念
（二）插入排序
   直接插入排序；折半插入排序；希尔排序（shell sort）
（三）交换排序
   冒泡排序（bubble sort）；快速排序
（四）选择排序
   简单选择排序；堆排序
（五）二路归并排序（merge sort）
（六）基数排序
（七）外部排序
（八）排序算法的分析和应用

1. (2012) 对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 ( )。

A. 排序的总趟数B. 元素的移动次数

C. 使用辅助空间的数量D. 元素之间的比较次数

2. (2014) 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是 ( )。

A. 2B. 3C. 4D. 5

3. (2015) 希尔排序的组内排序采用的是 ( )。

A. 直接插入排序B. 折半插入排序C. 快速排序D. 归并排序

4. (2018) 对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔）依次是 ( )。

A. 3, 1B. 3, 2C. 5, 2D. 5, 3

5. (2010) 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是 ( )。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后，先处理较长的分区可以减少递归次数

C. 每次划分后，先处理较短的分区可以减少递归次数

D. 递归次数与每次划分后得到的分区的处理顺序无关

6. (2011) 为实现快速排序算法，待排序序列宜采用的存储方式是 ( )。

A. 顺序存储B. 散列存储C. 链式存储D. 索引存储

7. (2014) 下列选项中，不可能是快速排序第2趟排序结果的是 ( )。

A.2,3,5,4,6,7,9B.2,7,5,6,4,3,9C.3,2,5,4,7,6,9D.4,2,3,5,7,6,9

8. (2019) 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是 ( )。

A.5,2,16,12,28,60,32,72B.2,16,5,28,12,60,32,72

C.2,12,16,5,28,32,72,60D.5,2,12,28,16,32,72,60

9. (2023) 使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68,11,70,23,80,77,48,81,93,88，则该次划分的枢轴是 ( )。

A. 11B. 70C. 80D. 81

10. (2024) 使用快速排序算法对含n(n≥3)个元素的数组M进行排序，若第一趟排序将M中除枢轴外的n-1个元素划分为均不为空的P和Q两块，则下列叙述中，正确的是 ( )。

A. P与Q块间有序B. P与Q均块内有序

C. P和Q的元素个数大致相等D. P中和Q中均不存在相等的元素

11. (2009) 若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序算法之一得到的第二趟排序后的结果，则该排序算法只能是 ( )。

A. 冒泡排序B. 插入排序C. 选择排序D. 二路归并排序

12. (2010) 对一组数据(2, 12, 16, 88, 5, 10)进行排序，若前3趟排序结果如下：
第一趟排序结果: 2, 12, 16, 5, 10, 88
第二趟排序结果: 2, 12, 5, 10, 16, 88
第三趟排序结果: 2, 5, 10, 12, 16, 88
则采用的排序算法可能是 ( )。

A. 冒泡排序B. 希尔排序C. 归并排序D. 基数排序

13. (2012) 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每趟排序结束都至少能够确定一个元素最终位置的方法是 ( )。

Ⅰ. 简单选择排序

Ⅱ. 希尔排序

Ⅲ. 快速排序

Ⅳ. 堆排序

Ⅴ. 二路归并排序

A. 仅Ⅰ、Ⅲ、ⅣB. 仅Ⅰ、Ⅲ、ⅤC. 仅ⅠⅠ、Ⅲ、ⅣD. 仅Ⅲ、Ⅳ、Ⅴ

14. (2017) 在内部排序时，若选择了归并排序而未选择插入排序，则可能的理由是 ( )。

Ⅰ. 归并排序的程序代码更短

Ⅱ. 归并排序的占用空间更少

Ⅲ. 归并排序的运行效率更高

A. 仅ⅡB. 仅ⅢC. 仅Ⅰ、ⅡD. 仅Ⅰ、Ⅲ

15. (2017) 下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是 ( )。

Ⅰ. 插入排序 Ⅱ. 选择排序 Ⅲ. 起泡排序 Ⅳ. 希尔排序 Ⅴ. 堆排序

A. 仅Ⅰ、ⅡB. 仅Ⅱ、ⅢC. 仅Ⅲ、ⅣD. 仅Ⅳ、Ⅴ

16. (2019) 选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是 ( )。

Ⅰ. 数据的规模

Ⅱ. 数据的存储方式

Ⅲ. 算法的稳定性

Ⅳ. 数据的初始状态

A. 仅ⅢB. 仅Ⅰ、ⅡC. 仅ⅠⅠ、Ⅲ、ⅣD. Ⅰ、Ⅱ、Ⅲ、IⅣ

17. (2020) 对大部分元素已有序的数组排序时，直接插入排序比简单选择排序效率更高，其原因是 ( )。

Ⅰ. 直接插入排序过程中元素之间的比较次数更少

Ⅱ. 直接插入排序过程中所需的辅助空间更少

Ⅲ. 直接插入排序过程中元素的移动次数更少

A. 仅ⅠB. 仅ⅢC. 仅Ⅰ、ⅡD. Ⅰ、Ⅱ和Ⅲ

18. (2022) 对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是 ( )。

Ⅰ. 大部分元素已有序

Ⅱ. 待排序元素数量很少

Ⅲ. 要求空间复杂度为O(1)

Ⅳ. 要求排序算法是稳定的

A. 仅Ⅰ、ⅡB. 仅Ⅲ、ⅣC. 仅Ⅰ、Ⅱ、ⅣD. Ⅰ、Ⅱ、Ⅲ、Ⅳ

19. (2023) 下列排序算法中，不稳定的是 ( )。

Ⅰ. 希尔排序

Ⅱ. 归并排序

Ⅲ. 快速排序

Ⅳ. 堆排序

Ⅴ. 基数排序

A. 仅Ⅰ、IIB. 仅ⅠⅠ、ⅤC. 仅Ⅰ、Ⅲ、ⅣD. 仅Ⅲ、Ⅳ、Ⅴ

20. (2013) 已知三叉树T中6个叶结点的权分别是2,3,4,5,6,7，T的带权（外部）路径长度最小是 ( )。

A. 27B. 46C. 54D. 56

21. (2016) 对10TB的数据文件进行排序，应使用的方法是 ( )。

A. 希尔排序B. 堆排序C. 快速排序D. 归并排序

22. (2019) 设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是 ( )。

A. 1B. 2C. 3D. 4

23. (2024) 在外排序中，利用败者树对初始为升序的归并段进行多路归并，败者树中记录“冠军”的结点保存的是 ( )。

A. 最大关键字B. 最小关键字

C. 最大关键字所在的归并段号D. 最小关键字所在的归并段号