【笔记】一些数据结构基础习题

断清秋 · 2025-11-13 21:53:36 · 个人记录

1、数据结构中有顺序存储结构、链式存储结构、索引存储结构、哈希存储结构这四种常用的存储结构类型。

::::info[Hint] 代表数据结构依次为数组、链表、B+ 树、哈希表。 ::::

2、在一个长度为 n 的带头结点的单链表 L 中，设有尾指针 r，则执行（C）操作与链表的表长有关。

A. 删除第一个元素

B. 在第一个元素前插入新元素

C. 删除最后一个元素

D. 在最后一个元素后插入新元素

::::info[Hint] C 操作意味着需要找到 r 的前驱结点，对于单链表需要从表头开始遍历，复杂度 O(n)。 ::::

3、已知循环队列存储在一维数组 a[0..n-1] 中，且队列非空时，front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存放在 a[0] 中，则初始时 front 和 rear 的值分别为（B）。

A. 0,0

B. 0,n-1

C. n-1,0

D. n-1,n-1

::::info[Hint] 每次入队时，尾指针先向后移动一位，然后将元素入队。本题中第一个元素入队时，尾指针先从 n-1 移动到 0，然后元素入队，此时头尾指针都指向 0，符合题意。 ::::

4、判断一个顺序栈 st（元素个数最多为 MaxSize）为空的条件可设置为（D）。

A. st->top==MaxSize/2

B. st->top!=MaxSize/2

C. st->top!=MaxSize-1

D. st->top==MaxSize-1

::::info[Hint] 这是一个向下生长的栈，栈底在地址最高处，入栈操作是地址向下移动，故栈空时 top 指针位于最高处，选 D。 ::::

5、若一个栈用数组 data[1..n] 存储，初始栈顶指针 top 为 n，则以下元素 x 进栈的操作正确的是（D）。

A. top++; data[top]=x;

B. data[top]=x;top++;

C. top--; data[top]=x

D. data[top]=x; top--;

::::info[Hint] 初始时栈为空，元素进栈存在 n 位，栈顶指针向下一位，选 D。 ::::

6、若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：

1、从 S1 中依次弹出两个操作数a和b。

2、从 S2 中弹出一个运算符op。

3、执行相应的运算b op a。

4、将运算结构压入栈S1中。

假设 S1 中的操作数依次是 5、8、3、2，其中，2 在栈顶。S2 中的运算符依次是 *、-、+，其中+位于栈顶。调用 3 次 F() 后，S1 栈顶保存的值是（C）。

A. 20

B. -15

C. 15

D. -20

::::info[Hint] 注意操作顺序是 b op a。 ::::

7、设循环队列的存储空间为 a[0..20]，且当前队头指针 f（f 指向队首元素前一个位置）和队尾指针 r（r 指向队尾元素）分别为 8 和 3，则该队列中元素个数为（B）。

A. 17

B. 16

C. 6

D. 5

::::info[Hint]

设环形队列中数组的下标是 0 \sim n-1，其队头指针为 f（指向队头元素的前一个位置），队尾指针为 r（指向队尾元素），则其元素个数为 (r-f+n) \mod n。

对于本题，元素数量为 (3-8+21) \mod 21 = 16。

直接数也行。 ::::

8、用循环单链表表示队列，下列说法中正确的是（B）。

A. 无论如何只能使入队方便，无法实现出队方便

B. 可设一个尾指针使入队、出队都方便

C. 必须设头尾指针才能使入队、出队都方便

D. 可设一个头指针使入队、出队都方便

::::info[Hint] 入队操作：只需在尾指针之后添加新节点，并更新尾指针。

出队操作：头节点是尾指针的 next 节点，因此可以通过尾指针直接访问头节点并进行出队操作。 ::::

9、设目标串 s 为 "abcaabbcaaabababaabca"，模式串 t 为 "babab"，则该模式串的 nextval 数组为（[-1,0,-1,0,-1]）；第一趟匹配从 i=0,j=0 开始，第二趟匹配从 i=0,j=−1 开始，则第 5 趟匹配从 i=(2)，j=(0) 开始。

::::info[Hint] 先计算 next 数组。next[j] 表示第 0 \ldots j-1 个字符中前缀和后缀的最长公共长度。

可以求出 next[0\ldots4]=[-1,0,0,1,2]。

再求 nextval 数组。当 t_j=t_{next[j]} 时，nextval[j]=nextval[next[j]]；反之，则 nextval[j]=next[j]。

可以求出 nextval[0\ldots4]=[-1,0,-1,0,-1]。

然后模拟 KMP 过程。若 j=-1 或 s_i=t_j，则 i \leftarrow i+1,j \leftarrow j+1；否则 j \leftarrow nextval[j]。

前 5 次匹配依次是 i=0,j=0 \Rightarrow i=0,j=-1 \Rightarrow i=1,j=0 \Rightarrow i=2,j=1 \Rightarrow i=2,j=0。 ::::

10、假设 L=(a_1,a_2,...,a_n) 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是（\dfrac{n}{2}）；若元素插在 a_i 与 a_{i+1} 之间 (0≤i≤n−1) 的概率为 \frac{2(n−i)}{n(n+1)}，则插入一个元素需要移动元素的个数是（\dfrac{2n+1}{3}）

::::info[Hint]

B. \log_2 h

C. \dfrac{h}{2}

D. h

::::info[Hint] 森林转二叉树的规则：森林中第一棵树的根作为二叉树的根，第二棵树的根作为第一棵树根的“右孩子”，第三棵树的根作为第二棵树根的“右孩子”，依此类推。

逆向思考（二叉树转森林）：二叉树的根结点是森林中第一棵树的根；二叉树根结点的右指针链（一直往右走的路径）上的每一个结点，依次是森林中后续每一棵树的根。 ::::

12、有一棵 3 次树，其中 n_3=2,n_2=2,n_1=1，当该树采用孩子兄弟链存储结构时，其中非空指针域数占总指针域数的比例约为（B）。

A. 10%

B. 45%

C. 70%

D. 90%

::::info[Hint] 孩子兄弟链存储结构：每个节点记录它的孩子和旁边的一个兄弟。（本质上是把树转化为二叉树）

本题中，可以求出 n_0=7，共有 12 个节点，11 条边，故所求值等于 \dfrac{11}{24}。 ::::

13、按照二叉树的定义，具有 4 个结点的二叉树，有（A）种形态。

A. 14

B. 12

C. 10

D. 16

::::info[Hint] 就是 Catlan 数 C_4=14。 ::::

14、一棵 124 个叶子结点的完全二叉树，最多有（B）个结点。

A. 247

B. 248

C. 249

D. 250

::::info[Hint] 二叉树中有 n_0=n_2+1，故 n_2=123。

又 n_1=0 或 1，取 n_1=1，则总结点数最大，为 248。 ::::

15、如果一棵有序树 T 转换为二叉树 B，那么 T 中结点的先根遍历序列就是 B 中结点的（先序）序列，T 中结点的后根遍历序列就是 B 中结点的（中序）序列，T 中结点的层次遍历序列就是 B 中结点的（无法确定）序列。

::::info[Hint] 把有序树 T 转换为二叉树 B 的方法：B 中的每个结点的左孩子是 T 中该结点的第一个孩子，右孩子是 T 中该结点的第一个兄弟。

转换为 B 就是：根 \rightarrow 左孩子 \rightarrow 右孩子 \ldots，即先序遍历。

转换为 B 就是：左孩子 \rightarrow 根，即中序遍历。（注意，B 中根没有右孩子） ::::

16、一棵含有 n 个结点的 k(k≥2) 次树，可能达到的最大高度为 n-1，最小高度为 \log_k (n(k-1)+1)。

::::info[Hint] 树退化成链的时候有最大高度。 ::::

17、线索二叉树中，先序/中序/后序线索树指：对于树中的每个结点，若其左孩子为空则令其指向树的先序/中序/后序遍历序列中该结点的前驱，若其右孩子为空则令其指向树的先序/中序/后序遍历序列中该结点的后继。

::::info[Hint]

B. n(n+1)

C. \dfrac{n(n−1)}{2}

D. n(n−1)

::::info[Hint] 无向图中每条边在邻接表内会被存两次。 ::::

20、若一个具有 n 个顶点、m 条边的无向图是一个森林，则该森林中必有（C）棵树。

A. n

B. m

C. n-m

D. 1

::::info[Hint] 设有 k 棵树，每棵树有 n_i 个结点和 n_i-1 条边，则 \sum\limits_{i=1}^kn_i=n,\sum\limits_{i=1}^k(n_i-1)=m，解得 k=n-m。 ::::

21、在采用顺序查找方法查找长度为 n 的线性表时，不成功查找的平均查找长度为（A）

A. n

B. \dfrac{n}{2}

C. \dfrac{n+1}{2}

D. \dfrac{n-1}{2}

::::info[Hint] 诈骗。不成功查找意味着元素不在表中，无论如何都要找 n 次。 ::::

22、关键路径是时间结点网络中（从源点到汇点的最长路径）。

23、以下不能构成折半查找中关键字比较序列的是（A）

A. 500,200,450,180

B. 500,450,200,180

C. 180,500,200,450

D. 180,200,500,450

::::info[Hint] 题意是问二分查找时不可能出现的序列是哪个。 ::::

24、有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需的平均比较次数为（B）

A. \dfrac{35}{12}

B. \dfrac{37}{12}

C. \dfrac{39}{12}

D. \dfrac{41}{12}

::::info[Hint] 考虑建立二叉树，所有结点的深度之和即为总查找次数。本题中总次数为 1\times 1+2 \times 2+4 \times 3+5\times 4=37.

实际上，查找成功所需总次数加上元素个数即为查找失败所需总次数（相当于在二叉树上对每个节点多访问了一次空指针） ::::

25、在含有 27 个结点的二叉排序树上查找关键字为 35 的结点，则依次比较的关键字序列有可能是（D）

A. 28,36,18,46,35

B. 18,36,28,46,35

C. 46,28,18,36,35

D. 46,36,18,28,35

::::info[Hint] 维护当前合法区间。以 D 选项为例。46 > 35，进入左子树，合法区间 (-\infty,46)；36>35，进入左子树，合法区间 (-\infty,36)；18<35，进入右子树，合法区间 (18,36)；28<35，进入右子树，合法区间 (28,36)；最终找到 35，合法路径。 ::::

26、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（A）

A. 95,22,91,24,94,71

B. 92,20,91,34,88,35

C. 21,89,77,29,36,38

D. 12,25,71,68,33,34

::::info[Hint] 维护当前合法区间。以 A 选项为例，95 \to 22，进入左子树，合法区间为 (-\infty,95)；22 \to 91，进入右子树，合法区间为 (22,95)；91 \to 24，进入左子树，合法区间为 (22,91)；24 \to 94，94 不在合法区间中，故该序列不合法。 ::::

27、含有 8 个关键字的 3 阶 B 树最多有（7）个内部结点，最少有（4）个内部结点。

::::info[Hint]

::::

28、已知一棵 3 阶 B 树中有 2047 个关键字，则树的最大高度是（B）。

A. 11

B. 12

C. 13

D. 14

::::info[Hint] 注意外部节点也要算作一层，每个内部节点带 1 个关键字，内部节点有 h 层的话有 2^h-1 \le 2047，h_{\max}=11，树高为 12。 ::::

29、下面有关哈希表的叙述中正确的是（B）

A. 哈希查找的时间与规模 n 成正比

B. 不管是开放地址法还是拉链法，查找时间都与装填因子 \alpha 有关

C. 开放地址法存在堆积现象，而拉链法不存在堆积现象

D. 在拉链法中装填因子 \alpha 必须小于 1

::::info[Hint]

装填因子 \alpha=\dfrac{n}{m}，其中 n 为哈希表内已存储元素数量，m 为哈希表长度。

我们认为拉链法如果冲突过多的话，链表可能过长，某种程度上也属于堆积。

开放地址法的平均探测次数是 \alpha 的函数，拉链法的平均查找长度约为 1+\alpha，因此 B 正确。 ::::

30、有一个序列（48, 36, 68, 99, 75, 24, 28, 52）进行快速排序，要求结果从小到大排序，则进行一次划分之后结果为（B）

A. [24 28 36] 48 [52 68 75 99]

B. [28 36 24] 48 [75 99 68 52]

C. [36 88 99] 48 [75 24 28 52]

D. [28 36 24] 48 [99 75 68 52]

::::info[Hint]

::::

31、用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时元素序列的变化情况如下：

（1）25,84,21,47,15,27,35,68,20

（2）21,25,47,84,15,27,35,68,20

（3）15,21,25,27,35,47,68,84,20

（4）15,20,21,25,27,35,47,68,84

其所采用的排序方法是（C）

A. 简单选择排序

B. 希尔排序

C. 二路归并排序

D. 快速排序

::::info[Hint]

::::

32、若一组元素的关键字序列为（46,79,56,38,40,84），则利用快速排序的方法，以第 1 个元素为基准得到的一次划分结果为（C）

A. 38,40,46,56,79,84

B. 40,38,46,79,56,84

C. 40,38,46,56,79,84

D. 40,38,46,84,56,79

::::info[Hint]

By Gemini 3 Flash.

快速排序的一次划分过程通常采用“双指针法”。

初始序列： (46, 79, 56, 38, 40, 84)

基准值 (Pivot)： 46（第 1 个元素）

详细划分步骤：

1. 设置指针： low 指向起始位置（索引 1，值 46），high 指向末尾位置（索引 6，值 84）。将基准值 46 暂存。
2. high 向左移动： 寻找比 46 小的元素。
   • high 指向 84，84 > 46，继续。
   • high 指向 40，40 < 46，停止。将 40 填入 low 所指的位置。
   • 此时序列：(40, 79, 56, 38, 40, 84)，low 为 1，high 为 5。
3. low 向右移动： 寻找比 46 大的元素。
   • low 指向 40，40 < 46，继续。
   • low 指向 79，79 > 46，停止。将 79 填入 high 所指的位置。
   • 此时序列：(40, 79, 56, 38, 79, 84)，low 为 2，high 为 5。
4. high 再次向左移动：
   • high 指向 79，79 > 46，继续。
   • high 指向 38，38 < 46，停止。将 38 填入 low 所指的位置。
   • 此时序列：(40, 38, 56, 38, 79, 84)，low 为 2，high 为 4。
5. low 再次向右移动：
   • low 指向 38，38 < 46，继续。
   • low 指向 56，56 > 46，停止。将 56 填入 high 所指的位置。
   • 此时序列：(40, 38, 56, 56, 79, 84)，low 为 3，high 为 4。
6. high 再次向左移动：
   • high 指向 56，56 > 46，继续。
   • high 指向 3，此时 low == high，移动停止。
7. 填入基准值： 将暂存的 46 填入 low（即索引 3）的位置。

最终划分结果： (40, 38, 46, 56, 79, 84) ::::

33、在下列排序方法中，某一趟结束后不一定能选出一个元素放在其最终位置上的是（C）。

A. 堆排序

B. 冒泡排序

C. 直接插入排序

D. 快速排序

::::info[Hint] 快速排序每次会选出一个基准元素，它一定是在正确位置上的。插入排序维护一个有序的前缀，但不保证是否在正确位置上。 ::::