1. 设置哨兵可以在数量级上提高顺序查找的时间性能，这个说法是否正确（）。
- A. 正确
- B. 错误
答案：B. 错误
解析： 设置哨兵可以优化顺序查找，通过将循环内部的两个判断（一个判断是否越界，一个判断是否相等）减少到一个判断，从而提高效率。但这只是优化了常数时间，其时间复杂度仍然是O(n)，并未在数量级上（例如从O(n)到O(log n)）提高性能。
2. 假设数组元素升序排列，采用折半查找技术，将待查值k与区间［low， high］的中间元素相比，若k的值较小，则修改语句是（ ）。
- A.
low = mid； - B.
low = mid + 1； - C.
high = mid； - D.
high = mid - 1；
答案：D. high = mid - 1；
解析： 在升序排列的数组中进行折半查找，当待查值k小于中间元素 A[mid] 时，说明k若存在，必定在区间的左半部分 [low, mid-1] 中。因此，需要将查找区间的上界 high 修改为 mid - 1 以缩小查找范围。
3. 具有13个结点的折半查找判定树，第4层有（）个结点。
- A. 4
- B. 5
- C. 6
- D. 7
答案：C. 6
解析： 折半查找的判定树是一棵形态上接近完全二叉树的二叉排序树。
- 第1层有 21−1=1 个结点。
- 第2层有 22−1=2 个结点。
- 第3层有 23−1=4 个结点。
- 前3层共有 1 + 2 + 4 = 7 个结点。
- 总共有13个结点，所以剩下的 13 - 7 = 6 个结点位于第4层。
4. 折半查找的平均时间复杂度是（）。
- A. O(1)
- B. O(n)
- C. O(log₂n)
- D. O(nlog₂n)
答案：C. O(log₂n)
解析： 折半查找（或称二分查找）的核心思想是每次将查找范围缩小一半。这种分治策略导致其查找次数与元素总数n的关系是对数级别的。因此，其平均时间复杂度和最坏情况下的时间复杂度都是O(log₂n)。
5. 若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点，这个说法是否正确（）。
- A. 正确
- B. 错误
答案：B. 错误
解析： 在二叉排序树中，最小元素是没有左子树的结点，但它可能有右子树。同理，最大元素是没有右子树的结点，但它可能有左子树。只有当最小元素的结点没有右子树，或最大元素的结点没有左子树时，它们才是叶子结点。所以这个说法不是绝对正确的。
6. 在闭散列表中有可能出现堆积，开散列表一定不会出现堆积，这个说法是否正确（）。
- A. 正确
- B. 错误
答案：A. 正确
解析： “堆积”或“聚集”是指在散列表中，哈希到不同地址的元素，因冲突解决策略而竞争同一个后续空闲位置的现象。
- 闭散列（开放地址法）如线性探测，当发生冲突时会探查下一个地址，这很容易导致关键字连成一片，形成堆积。
- 开散列（链地址法）为每个哈希地址维护一个独立的链表，所有冲突的元素都放入同一个链表。不同哈希地址的冲突互不影响，因此不会产生堆积现象。
7. 静态查找与动态查找的根本区别在于（）。
- A. 它们的逻辑结构不一样
- B. 施加在其上的操作不同
- C. 数据元素的类型不一样
- D. 存储实现不一样
答案：B. 施加在其上的操作不同
解析：
- 静态查找表：数据集合是固定的，只进行查找操作。
- 动态查找表：在查找过程中，还会涉及插入和删除元素的操作，数据集合是动态变化的。 因此，两者最根本的区别在于所支持的操作集合不同。
8. 能够有效实现动态查找的数据结构是（）。
- A. 有序表
- B. 双链表
- C. 循环链表
- D. 二叉查找树
答案：D. 二叉查找树
解析： 动态查找要求数据结构能高效地支持查找、插入和删除。
- 二叉查找树（及其平衡变种如AVL树、红黑树）在平均情况下的查找、插入、删除操作的时间复杂度都是O(log n)，效率很高。
- 有序表插入删除慢（O(n)），链表查找慢（O(n)），都不适合作为高效的动态查找结构。
9. 假定查找成功与不成功的可能性相同，在查找成功的情况下每个记录的查找概率相同，则顺序查找的平均查找长度为（）。
- A. 0.5(n+1)
- B. 0.25(n+1)
- C. 0.5(n-1)
- D. 0.75n+0.25
答案：D. 0.75n＋0.25
解析：
- 查找成功的平均查找长度 (ASL_succ)：每个元素被查到的概率是1/n，查找第i个元素需要比较i次。所以 ASL_succ = (1+2+…+n)/n = (n(n+1)/2)/n = (n+1)/2。
- 查找不成功的平均查找长度 (ASL_unsucc)：当查找不成功时，需要与所有n个元素都比较一遍才能确定，所以 ASL_unsucc = n。
- 综合平均查找长度 (ASL)：题目假定成功和不成功的概率各为0.5。 ASL = P(成功) × ASL_succ + P(不成功) × ASL_unsucc ASL = 0.5 × ((n+1)/2) + 0.5 × n = (n+1)/4 + 2n/4 = (3n+1)/4 = 0.75n + 0.25。
10. 对具有14个元素的有序表R[14]进行折半查找，查找R[3]时比较需要比较（）。
- A. R[0] R[1] R[2] R[3]
- B. R[6] R[2] R[4] R[3]
- C. R[0] R[13] R[2] R[3]
- D. R[6] R[4] R[2] R[3]
答案：B. R[6] R[2] R[4] R[3]
解析： 对有序表 R[0…13] 进行折半查找，目标是R[3]的值。
low=0,high=13,mid = (0+13)//2 = 6。比较R[3]和R[6]。因为表有序，R[3] < R[6]，所以查找范围变为左半部分。low=0,high=5,mid = (0+5)//2 = 2。比较R[3]和R[2]。R[3] > R[2]，查找范围变为右半部分。low=3,high=5,mid = (3+5)//2 = 4。比较R[3]和R[4]。R[3] < R[4]，查找范围变为左半部分。low=3,high=3,mid = (3+3)//2 = 3。比较R[3]和R[3]。找到。 依次比较的元素下标是6, 2, 4, 3。
11. 已知10个元素（54, 28, 16, 73, 62, 95, 60, 26, 43），按照依次插入的方法生成一棵二叉查找树，查找值为62的结点所需比较次数为（）。
- A. 2
- B. 3
- C. 4
- D. 5
答案：B. 3
解析： 构造二叉查找树并查找62的过程如下：
- 插入54作为根。
- 插入28 (<54)，成为54的左孩子。
- 插入16 (<28)，成为28的左孩子。
- 插入73 (>54)，成为54的右孩子。
- 插入62 (>54, <73)，成为73的左孩子。 …后续插入不影响查找62的路径。 查找62：
- 与根结点54比较，62 > 54，查找右子树。(第1次比较)
- 与结点73比较，62 < 73，查找左子树。(第2次比较)
- 与结点62比较，找到该结点。(第3次比较) 共需比较3次。
12. 已知数据序列为 {34, 76, 45, 18, 26, 54, 92, 65}，按照依次插入结点的方法生成一棵二叉查找树，该树的深度为（）。
- A. 5
- B. 6
- C. 7
- D. 8
答案：A. 5
解析： 依次插入结点构造二叉查找树，并记录每个结点的深度（根为1）：
34(深度1)76(>34) -> 右孩子 (深度2)45(<76) -> 左孩子 (深度3)18(<34) -> 左孩子 (深度2)26(>18) -> 右孩子 (深度3)54(>45) -> 右孩子 (深度4)92(>76) -> 右孩子 (深度3)65(>54) -> 右孩子 (深度5) 最长的路径是34 -> 76 -> 45 -> 54 -> 65，包含了5个结点，因此树的深度为5。
13. 在二叉查找树上查找关键码为28的结点（假设存在），则依次比较的关键码有可能是（）。
- A. 30, 36, 28
- B. 38, 48, 28
- C. 48, 18, 38, 28
- D. 60, 30, 50, 40, 38, 36
答案：C. 48, 18, 38, 28
解析： 在二叉查找树中查找必须遵循“小则向左，大则向右”的规则。
- 选项A：28<30应向左，但下一个是36，不符。
- 选项B：28<38应向左，但下一个是48，不符。
- 选项C：比较48 (28<48,向左) -> 比较18 (28>18,向右) -> 比较38 (28<38,向左) -> 比较28 (找到)。此路径完全符合规则。
- 选项D：比较60 (28<60,向左) -> 比较30 (28<30,应向左)，但下一个是50，不符。
14. 设散列表表长m=14，散列函数H(k) = k mod 11。表中已有15、38、61、84四个元素，用线性探测法处理冲突，则元素49的存储地址是（）。
- A. 8
- B. 3
- C. 5
- D. 9
答案：A. 8
解析：
- 先确定已存在元素的地址（表下标0-13）：
- H(15) = 15 mod 11 = 4.
T[4] = 15 - H(38) = 38 mod 11 = 5.
T[5] = 38 - H(61) = 61 mod 11 = 6.
T[6] = 61 - H(84) = 84 mod 11 = 7.
T[7] = 84
- H(15) = 15 mod 11 = 4.
- 插入元素49：
- H(49) = 49 mod 11 = 5。
- 地址5被占用（冲突）。线性探测下一个地址：(5+1)%14 = 6。
- 地址6被占用（冲突）。线性探测下一个地址：(6+1)%14 = 7。
- 地址7被占用（冲突）。线性探测下一个地址：(7+1)%14 = 8。
- 地址8为空，存入49。所以地址是8。
15. 为一组关键码（87, 73, 25, 55, 90, 28, 31, 17, 101, 22, 3, 62）构造散列表，设散列函数为H(key) = key mod 11，在用链地址法处理后位于同一链表中的是（）。
- A. 81, 90
- B. 31, 101
- C. 3, 78
- D. 62, 73
答案：D. 62, 73
解析： 链地址法将哈希地址相同的关键字放在同一个链表中。我们只需计算选项中哪一组关键码的 mod 11 余数相同即可。
- A. H(81)=4, H(90)=2
- B. H(31)=9, H(101)=2
- C. H(3)=3, H(78)=1
- D. H(62) = 62 mod 11 = 7, H(73) = 73 mod 11 = 7。两者哈希值相同。 因此，62和73会位于同一个链表中。