第8章 线性数据结构
本章在原教材中以 练习题/选择题 为主，没有单独的知识讲解部分。以下内容按教材原有顺序整理，并将答案做成 Docusaurus/MDX 可折叠形式。
1. 哈希表：线性探查
设有一个含有 13 个元素的 Hash 表（地址 0~12），Hash 函数是：
H(key) = key % 13
其中 % 是求余数运算。
用线性探查法解决冲突，则对于序列：
(2、8、31、20、19、18、53、27)
18 应放在第几号格中（ ）。
- A. 5
- B. 9
- C. 4
- D. 0
查看答案
答案：B
2. 哈希表：冲突处理
给定地址区间为 0~9 的哈希表，哈希函数为：
h(x) = x % 10
采用线性探查的冲突解决策略：出现冲突时，向后探查第一个空地址存储；若地址 9 冲突，则从地址 0 重新开始探查。
哈希表初始为空表，依次存储：
(71, 23, 73, 99, 44, 79, 89)
请问 89 存储在哈希表哪个地址中（ ）。
- A. 9
- B. 0
- C. 1
- D. 2
查看答案
答案：D
3. 哈希表：mod 函数
现有一个地址区间为 0~10 的哈希表。出现冲突时，向后找第一个空地址存储；到地址 10 冲突后，从 0 开始向后探查。
现在依次存储：
(0, 1, 2, 3, 4, 5, 6, 7)
哈希函数为 mod。
请问 7 存储在哈希表哪个地址中（ ）。
- A. 5
- B. 6
- C. 7
- D. 8
查看答案
答案：C
4. 字符串的非空子串
设字符串：
S = "Olympic"
S 的非空子串的数目是（ ）。
- A. 29
- B. 28
- C. 16
- D. 17
查看答案
答案：B
5. 字符串
以下关于字符串的判定语句中正确的是（ ）。
- A. 字符串是一种特殊的线性表
- B. 串的长度必须大于零
- C. 字符串不可以用数组来表示
- D. 空格字符组成的串就是空串
查看答案
答案：A
6. 字符串相邻交换
定义一种字符串操作为：交换相邻两个字符。
将：
DACFEB
变为：
ABCDEF
最少需要（ ）次上述操作。
- A. 7
- B. 8
- C. 9
- D. 6
查看答案
答案：A
7. 链表特点
链表不具有的特点是（ ）。
- A. 插入删除不需要移动元素
- B. 不必事先估计存储空间
- C. 所需空间与线性表长度成正比
- D. 可随机访问任一元素
查看答案
答案：D
8. 双向链表查询复杂度
在含有 n 个元素的双向链表中，查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ ）。
- A.
O(1) - B.
O(log n) - C.
O(n) - D.
O(nlogn)
查看答案
答案：C
9. 链表的存储地址
线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。
- A. 必须连续
- B. 部分地址必须连续
- C. 一定不连续
- D. 连续不连续均可
查看答案
答案：D
10. 栈：入栈顺序
已知元素：
(8，25，14，87，51，90，6，19，20)
问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：
8在51前面90在87后面20在14后面25在6前面19在90后面
（ ）。
- A.
20，6，8，51，90，25，14，19，87 - B.
51，6，19，20，14，8，87，90，25 - C.
19，20，90，8，6，25，51，14，87 - D.
6，25，51，8，20，19，90，87，14
查看答案
答案：D
11. 栈：合法出栈序列
对于入栈顺序为：
a, b, c, d, e, f, g
的序列，下列（ ）不可能是合法的出栈序列。
- A.
a, b, c, d, e, f, g - B.
a, d, c, b, e, g, f - C.
a, d, b, c, g, f, e - D.
g, f, e, d, c, b, a
查看答案
答案：C
12. 栈和队列
设栈 S 和队列 Q 的初始状态为空。
元素：
e1, e2, e3, e4, e5, e6
依次通过栈 S，一个元素出栈后即进入队列 Q。
若出队的顺序为：
e2, e4, e3, e6, e5, e1
则栈 S 的容量至少应该为（ ）。
- A. 2
- B. 3
- C. 4
- D. 5
查看答案
答案：B
13. 数制运算
(2070)<sub>16</sub> + (34)<sub>8</sub> 的结果不正确的是（ ）。
- A.
(8332)<sub>10</sub> - B.
(208C)<sub>16</sub> - C.
(100000000110)<sub>2</sub> - D.
(20214)<sub>8</sub>
查看答案
答案：C
14. 【多选】哈希函数
将：
(2, 6, 10, 17)
分别存储到某个地址区间为 0~10 的哈希表中。
如果哈希函数 h(x) 为（ ），将不会产生冲突。
其中 a mod b 表示 a 除以 b 的余数。
- A.
x mod 11 - B.
x^2 mod 11 - C.
2^x mod 11 - D.
⌊√x⌋ mod 11
查看答案
答案：C、D
15. 【多选】栈的出栈序列
设栈 S 的初始状态为空，元素：
a, b, c, d, e, f, g
依次入栈。
以下出栈序列不可能出现的有（ ）。
- A.
a, b, c, e, d, f, g - B.
b, c, a, f, e, g, d - C.
a, e, c, b, d, f, g - D.
g, e, f, d, c, b, a
查看答案
答案：C、D