数据结构之查找绪论题解

选择题

1. 顺序查找适合于存储结构为()的线性表。

A. 顺序存储结构或链式存储结构
B. 散列存储结构
C. 压缩存储结构
D. 冗余存储结构

答案: A
解释: 顺序查找从表的一端开始向另一端查找，不要求表的存储结构具有随机存取特性，因此适用于顺序存储结构和链式存储结构。

2. 由n个数据元素组成的两个表: 一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找()。

A. 平均时间后者小
B. 平均时间两者相同
C. 平均时间前者小
D. 无法确定

答案: B
解释: 对于顺序查找，无论是有序表还是无序表，成功查找的比较次数只与元素在表中的位置有关，因此两者的平均查找时间是相同的。

3. 对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为()。

A. (n-1)/2
B. (n+1)/2
C. n/4
D. n/2

答案: B
解释: 在有序单链表上做顺序查找时，查找成功的平均查找长度为 $(n+1)/2$。这是因为每个元素的查找成功的概率相等，因此查找成功的平均长度和无序表相同。

4. 对长度为3的顺序表进行查找，若查找第一个元素的概率为 1/2，查找第二个元素的概率为 1/3，查找第三个元素的概率为 1/6，则查找任一元素的平均查找长度为()。

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

答案: A
解释: 查找第一个元素的查找长度为1，查找第二个元素的查找长度为2，查找第三个元素的查找长度为3。根据概率计算平均查找长度： $ ASL = 1 + 2 + 3 = + + = + + = = $

5. 下列关于二分查找的叙述中，正确的是()。

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型、实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储

答案: D
解释: 二分查找要求表必须有序，且为顺序存储方式，以便能够通过下标快速定位中间元素。虽然表中的数据可以是整型、实型或字符型，但二分查找本身并不限制这些类型。

6. 在一个顺序存储的有序线性表上查找一个数据时，既可以采用折半查找，也可以采用顺序查找，但前者比后者的查找速度()

A. 必然快
B. 取决于表是递增还是递减
C. 在大部分情况下要快
D. 必然不快

答案: C
解释: 折半查找（也称为二分查找）在大部分情况下要快于顺序查找。虽然对于特定情况（例如查找有序表的第一个元素），顺序查找可能会更快，但总体而言，折半查找的平均时间复杂度为 $O(\log n)$，而顺序查找为 $O(n)$。

7. 折半查找过程所对应的判定树是一棵()

A. 最小生成树
B. 平衡二叉树
C. 完全二叉树
D. 满二叉树

答案: B
解释: 折半查找的判定树是平衡二叉树。在每次查找中，数组被分为两部分，导致每个节点的左右子树高度差不超过1，从而形成平衡的结构。

8. 折半查找和二叉排序树的时间性能()

A. 相同
B. 有时不相同
C. 完全不同
D. 无法比较

答案: B
解释: 折半查找的平均查找长度和最大查找长度都是 $O(\log n)$，而二叉排序树的性能依赖于树的结构。如果树是平衡的，查找性能接近折半查找；但在最坏情况下（如形成单支树），查找长度为 $O(n)$，因此二者在性能上有时会不同。

9. 在有11个元素的有序表A[1,2,…,11]中进行折半查找，查找元素A[11]时，被比较的元素下标依次是()

A. 6, 8, 10, 11
B. 6, 9, 10, 11
C. 6, 7, 9, 11
D. 6, 8, 9, 11

答案: B
解释: 折半查找的过程如下：

第一次计算中间下标: $ = = 6 $，比较 $ A[6] $（即2）和目标值（11），2 < 11，调整范围为 $ [7, 11] $。
第二次计算中间下标: $ = = 9 $，比较 $ A[9] $（即90）和11，90 > 11，调整范围为 $ [7, 8] $。
第三次计算中间下标: $ = = 10 $，比较 $ A[10] $（即115）和11，115 > 11，调整范围为 $ [11, 11] $。
第四次比较 $ A[11] $（即134）和11，134 > 11，查找成功。

10. 已知有序表(13,18,24,35,47,50,62,83,90,115,134)，当二分查找值为90的元素时，查找成功的比较次数为()

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

答案: B
解释: 查找90的过程如下：

第一次比较：中间元素是50，90 > 50，调整范围为 $ [62, 134] $。
第二次比较：中间元素是90，找到目标元素。
因此，查找成功的比较次数为2次。

11. 对表长为n的有序表进行折半查找，其判定树的高度为()

A. $ _2(n+1) $
B. $ _2(n+1) $
C. $ _2 n $
D. $ _2 n $

答案: B
解释: 对于n个结点的判定树，其高度可以通过公式$ h =_2(n+1) $计算得出。该公式是因为每次查找将范围减半，最终达到查找元素的结果。

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

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

答案: A
解释: 在一个长度为16的顺序表中，使用折半查找查找一个不存在的元素：

最多比较次数（最坏情况）： $ _2(16 + 1) = 5 $
最少比较次数（最佳情况）：因为在查找过程中，判定树的分支高度可以相差1，至少需要4次比较。因此比较的次数至少为4次，至多为5次。

13. 具有12个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为()，折半查找查找失败的平均查找长度为()。

A. $ , $
B. $ $
C. $ $
D. $ $

答案: A
解释:

查找成功的平均查找长度（ASL）可以通过对折半查找的判定树进行分析得出： $ASL_{\text{成功}} = \frac{1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 5}{12} = \frac{37}{12}$
查找失败的平均查找长度可以通过如下计算得到： $ASL_{\text{失败}} = \frac{3 \cdot 3 + 4 \cdot 10}{13} = \frac{49}{13}$

14. 采用分块查找时，数据的组织方式为()。

A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D. 数据分成若干块，每块(除最后一块外)中数据个数需相同

答案: B
解释: 在分块查找的结构中，通常不要求每个索引块中的元素个数都相等，但块内的数据可以不必有序，块间则必须有序，并且每个块的最大（或最小）数据会组成索引块。

15. 对有2500个记录的索引顺序表（分块表）进行查找，最理想的块长为()。

A. 50
B. 125
C. 500
D. $ _2 2500 $ 答案: A
解释: 设块长为 $ b $，索引表包含 $ n/b $ 项，索引表的ASL为 $ (n/b + 1)/2 $，块内的ASL为 $ (b + 1)/2 $，总ASL为： $ = + 1 + = $ 通过均值不等式知，$ b = $ 时总ASL有最小值，因此当 $ n = 2500 $ 时，理想的块长为 $ = 50 $。 ### 16. 设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找法来确定子块，且在确定的子块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为()
A. 21
B. 23
C. 41
D. 62

答案: B
解释:

将123个元素等分为3块，每块有 $ s = = 41 $ 个元素。
分块查找的平均查找长度（ASL）为： $ ASL = + = 23 $

17. 为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行()次关键字比较。

A. 10
B. 14
C. 16
D. 21

答案: C
解释:

为使查找效率最高，每个索引块的大小应为 $ = 255 $。建立索引后，索引表中索引项的个数为255。
在对索引项和索引块内部采用折半查找的情况下，查找效率最高时的比较次数为： $ _2(255 + 1)+ _2(255 + 1)= 16 $

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

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

答案: B
解释:

在折半查找法中，当查找不成功时，关键字的比较次数最多等于树的高度。高度计算为： $ _2(n) + 1 _2(n + 1) $
在此例中，$ n = 16 $ 时，比较次数最多为5。

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

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

答案: A
解释:

选项 A的查找路径不满足。

20. 在有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位于数组中间位置

答案: B
解释:

该查找算法每次增加k的值为3，这使得它在查找接近数组结尾的元素时能更快地到达末尾。相较于折半查找，若x位于数组结尾，可能会减少比较次数。
而如果x在数组中间或接近开头，则折半查找仍然能够更快地找到该元素。

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

答案：A

折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即为所求，如下图所示。

B选项4、5相加除以2向上取整，7、8相加除以2向下取整，矛盾。C选项，3、4相加除以2向上取整，6、7相加除以2向下取整，矛盾。D选项，1、10相加除以2向下取整，6、7相加除以2向上取整，矛盾。A选项符合折半查找规则，正确。

应用题

问题01

讨论顺序查找平均查找长度的三种情况：

1) 查找失败

有序顺序表：
- 当查找失败时，查找到第一个比给定值大的元素即可终止，无需遍历整个表。
- 因此，查找失败的平均查找长度较短。
无序顺序表：
- 必须遍历整个表的所有元素才能确定查找失败。
结论：平均查找长度不同。有序顺序表在查找失败时可以提前结束，无序顺序表则需遍历整个表。

2) 查找成功，且表中只有一个关键字等于给定值k的元素

有序顺序表：
- 查找到关键字等于给定值的元素时即可终止。
无序顺序表：
- 查找到关键字等于给定值的元素时同样可以终止。
结论：平均查找长度相同。两者在查找成功时都会在找到该元素后立即结束。

3) 查找成功，且表中有若干关键字等于给定值k的元素

有序顺序表：
- 因为相同关键字的元素在有序顺序表中是连续排列的，查找到第一个等于k的元素后，可以顺序找到其他相同的元素，因此查找时间较短。
无序顺序表：
- 必须遍历整个表才能确定所有等于k的元素，因此查找时间较长。
结论：平均查找长度不同。有序顺序表在找到第一个相同元素后能快速找到其余的，无序顺序表则需查找整个表。

问题02

对有序顺序表的折半查找问题：

给定顺序表：$17, 94, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908$

查找成功的平均查找长度 (ASL成功)：

根据查找路径和查找到的节点，计算成功的平均查找长度。公式如下：

展开计算：

$ ASL_{} = = = $
查找失败的平均查找长度 (ASL失败)：

在查找失败的情况下，失败的节点（方形节点）是虚构的，最后一次的比较是与其父结点（圆形结点）。计算公式为：

$ ASL_{} = $

展开计算：

$ ASL_{} = $

问题03

设计一个 k 分查找算法（k 为大于 2 的整数），该算法类似于二分查找：
首先检查第 $ n/k $ 处（$ n $ 为查找表的长度）的元素是否等于要搜索的值，然后检查第 $ 2n/k $ 处的元素，以此类推。这样，或者找到要查找的元素，或者将集合缩小到原来的 $ 1/k $。如果还没有找到，则继续在缩小后的集合上进行 k 分查找，直到找到目标元素或查找失败。

试求：

查找成功时的时间复杂度是多少？
查找失败时的时间复杂度是多少？
查找成功的时间复杂度
查找过程可以用 k叉树 来描述。在最坏情况下，从第 2 层开始，每一层都需要进行 $ k-1 $ 次关键字比较，树的深度为 $ _k n $。所以在查找成功时，比较次数最多为：

$ = (k-1) _k n $

因此，查找成功的时间复杂度为：

$ O((k-1) _k n) O(_k n) $
查找失败的时间复杂度
查找失败时的过程类似于查找成功的情况，也需要经历 $ _k n $ 的深度，每一层进行 $ k-1 $ 次比较。因此，查找失败的时间复杂度同样为：

$ O((k-1) _k n) O(_k n) $

问题04

已知一个有序顺序表 $ A[0...8n-1] $，表长为 $ 8n $，并且表中没有关键字相同的数据元素。现设计一个查找算法来查找关键字等于给定值 $ x $ 的数据元素。查找方法如下：

初步查找：先在 $ A[7], A[15], A[23], , A[8k-1], , A[8n-1] $ 中进行顺序查找。如果查找成功，则报告成功位置并返回。
缩小范围后折半查找：如果初步查找失败，且满足 $ A[8k-1] < x < A[8(k+1)-1] $，则确定一个缩小的查找范围 $ A[8k] $ 到 $ A[8(k+1)-2] $，然后在这个范围内执行折半查找。

要求：

设计查找的判定树，并标出查找成功时的关键字比较次数。
在等查找概率下，计算查找成功时的平均查找长度。

相应的判定树如下图所示。

查找成功的平均查找长度公式的推导：

1. 总体思路

公式中的 $ ASL_{} $ 表示查找成功时的平均查找长度。设顺序表长度为 $ 8n $，其中每个关键字查找成功的概率是 $ $。查找策略分为两个阶段：

第一阶段：在 $ A[7], A[15], A[23], , A[8n-1] $ 中进行顺序查找。查找到位置 $ 8k-1 $ 时，直接成功。
第二阶段：若关键字在缩小的范围内，在范围 $ A[8k] $ 到 $ A[8(k+1)-2] $ 内执行折半查找。

2. 查找次数 $ C_i $

查找成功的平均查找长度是每个关键字查找所需的比较次数的平均值。记第 $ i $ 个元素的查找长度为 $ C_i $，可以分解成以下几部分：

$ ASL_{} = _{i=0}^{8n-1} C_i $

查找的次数 $ C_i $ 可以根据不同区间依次计算：

第 1 个区间（0 ~ 7）：顺序查找 1 次，然后进行折半查找（查找深度为 2、3 或 4 次）。
第 2 个区间（8 ~ 15）：顺序查找 2 次，然后折半查找。
以此类推，每个区间的顺序查找次数随着 $ i $ 的增大而增加，折半查找的次数相应减少。

3. 公式推导

公式逐步推导为：

$ ASL_{} = ( {i=1}^{n} i + {i=2}^{n+1} i + 2{i=3}^{n+2} i + 4{i=4}^{n+3} i ) $

这可以理解为不同查找区间中每个区间内的折半查找次数与顺序查找次数的总和。

经过计算化简，最终得到：

$ ASL_{} = {i=1}^{n} (8i + 17) = {i=1}^{n} i + = + $

问题05

设计一个递归的折半查找算法。假设查找的初始边界是 low=1，high=ST.length，查找的关键字为 key。要求在有序表中查找 key 是否存在，若存在则返回其下标，若不存在则返回查找失败。

答案：

折半查找（也称二分查找）的基本思想是：每次将查找的范围一分为二，通过比较中间位置元素与待查找元素的大小，确定在哪一部分继续查找。递归版本的折半查找通过不断缩小查找范围，最终找到目标元素或确定元素不存在。

// 定义查找表的数据结构
typedef struct {
    ElemType* elem;  // 存储空间基址，建表时按实际长度分配，0号留空
    int length;      // 表的长度
} SsTable;

// 折半查找的递归算法
int BinSearchRec(SsTable ST, ElemType key, int low, int high) {
    if (low > high) {  // 递归终止条件，未找到元素
        return -1;     // 查找失败，返回-1
    }
    
    int mid = (low + high) / 2;  // 计算中间位置
    
    if (key == ST.elem[mid]) {   // 查找成功，返回中间位置
        return mid;
    } 
    else if (key < ST.elem[mid]) {
        // 递归在前半部分查找
        return BinSearchRec(ST, key, low, mid - 1);
    } 
    else {
        // 递归在后半部分查找
        return BinSearchRec(ST, key, mid + 1, high);
    }
}

解释：

数据结构：
查找表 SsTable 结构中包含一个指向元素数组的指针 elem 和一个 length 来表示表的长度。
递归查找过程：
- 计算中间位置 mid，比较中间元素 ST.elem[mid] 与要查找的 key：
  - 如果相等，则查找成功，返回元素的位置 mid；
  - 如果 key 小于中间元素，则递归在左半部分（low 到 mid-1）继续查找；
  - 如果 key 大于中间元素，则递归在右半部分（mid+1 到 high）继续查找。
- 如果 low > high，表示查找范围已经缩小为无效区间，此时返回 -1，表示查找失败。

问题06

在一个线性表中，各个节点的检索概率不相等时，可以通过找到指定节点后将其与前驱节点交换的方法提高顺序查找效率。请设计在顺序表和链表上实现这一策略的顺序查找算法，要求每次查找到目标节点后，若有前驱节点，则交换该节点与前驱节点。

答案：

算法基本思想：
- 检索时从表头开始向后顺序扫描。
- 找到指定的节点后，将该节点和其前驱节点（若存在）交换。
- 这样可以提高那些经常被查找的节点的访问效率，使它们逐渐向表的前端移动。

顺序表的实现：

在顺序表的存储结构中，假设表 R 中存储了记录类型 RcdType，其中 key 是用于查找的关键字，n 表示顺序表的长度。查找并交换的顺序查找算法如下：

// 顺序查找并交换算法：顺序表实现
int seqSrch(RcdType R[], ElemType k, int n) {
    int i = 0;
    
    // 从表头开始顺序查找指定节点
    while ((R[i].key != k) && (i < n)) {
        i++;
    }
    
    // 若找到指定节点
    if (i < n) {
        // 若存在前驱节点，交换该节点与前驱节点
        if (i > 0) {
            RcdType temp = R[i];
            R[i] = R[i - 1];
            R[i - 1] = temp;
            return i - 1;  // 返回交换后的位置
        } else {
            return i;  // 若在第一个位置找到，直接返回当前位置
        }
    } else {
        return -1;  // 查找失败
    }
}

链表的实现：

在链表存储结构中，我们需要维护指向前驱节点的指针，因为链表不能像顺序表那样直接访问前驱节点。假设链表中每个节点类型 Node 包含关键字 key 和指向下一个节点的指针 next。查找并交换的链表顺序查找算法如下：

// 链表的节点定义
typedef struct Node {
    ElemType key;
    struct Node* next;
} Node, *LinkList;

// 链表顺序查找并交换算法
Node* seqSrchLink(LinkList head, ElemType k) {
    Node *prev = NULL, *cur = head;
    
    // 从表头开始顺序查找指定节点
    while (cur != NULL && cur->key != k) {
        prev = cur;
        cur = cur->next;
    }
    
    // 若找到指定节点
    if (cur != NULL) {
        // 若存在前驱节点，交换当前节点与前驱节点
        if (prev != NULL) {
            prev->next = cur->next;
            cur->next = head;
            return cur;  // 返回当前节点指针（交换后是头节点）
        }
    }
    
    return cur;  // 返回找到的节点或 NULL（若未找到）
}

解释：

顺序表的实现：
- 使用顺序扫描从表头依次查找，找到目标关键字后，检查是否有前驱节点。
- 若有前驱节点，则交换当前节点和前驱节点的位置，并返回新的节点位置。
链表的实现：
- 链表无法通过索引直接访问前驱节点，因此我们需要在查找过程中记录前驱节点。
- 一旦找到目标节点，检查是否有前驱节点，如果有，则交换前驱节点和当前节点，并使当前节点成为链表的新头节点。

问题07

设包含 4 个数据元素的集合 $ S = { , , , } $，各元素的查找概率依次为 $ p_1 = 0.35 $，$ p_2 = 0.15 $，$ p_3 = 0.15 $，$ p_4 = 0.35 $。集合存储在长度为 4 的顺序表中，采用折半查找时，查找成功的平均查找长度为 2.2。

若采用顺序存储结构保存 $ S $，且要求平均查找长度更短，元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
若采用链式存储结构保存 $ S $，且要求平均查找长度更短，元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

解答：

1. 使用顺序存储结构时的解答：

基本思想：
折半查找要求数据元素有序存储，而查找概率不同的情况下，折半查找未必优于顺序查找。为了缩短查找成功时的平均查找长度，可以使用顺序查找，并按元素的查找概率降序排列。
排列方式：
将集合 $ S $ 按照查找概率从高到低排列。根据给出的查找概率，集合元素应按以下顺序排列： $ S = { , , , } $ 其中，查找概率最高的元素 do 和 while 排在最前面。
查找方法：
使用顺序查找。顺序查找可以利用查找概率高的元素排在前面的优势，使得经常查找的元素被尽早访问，从而降低平均查找长度。
查找成功时的平均查找长度：
设查找成功时，元素出现在位置 $ i $ 的概率为 $ p_i $，查找成功的平均查找长度 $ L_{} $ 为： $ L_{} = p_1 + p_4 + p_2 + p_3 $ 代入概率： $ L_{} = 0.35 + 0.35 + 0.15 + 0.15 = 2.1 $ 所以查找成功时的平均查找长度为 2.1，明显比折半查找的 2.2 更短。

2. 使用链式存储结构时的解答：

答案一：顺序查找

基本思想：
在链表中，元素只能顺序查找，无法像顺序表那样使用索引直接访问，因此必须逐个扫描节点，直到找到目标元素。为了提高效率，可以按照查找概率的降序排列元素。
排列方式：
类似于顺序表，元素仍然按查找概率降序排列，顺序为： $ S = { , , , } $
查找方法：
使用链表结构的顺序查找。因为链表没有随机访问功能，只能顺序查找。
查找成功时的平均查找长度：
与顺序表的情况相同，查找成功的平均查找长度为： $ L_{} = 0.35 + 0.35 + 0.15 + 0.15 = 2.1 $

答案二：二叉排序树

基本思想：
若采用链式存储结构，还可以将集合构造成二叉排序树（Binary Search Tree，BST）的形式。二叉排序树的查找效率依赖于树的结构，通过合理构造树的形态，可以进一步优化查找效率。
排列方式：
将集合 $ S $ 构造成二叉排序树，元素按照查找概率的高低分布在树的不同节点。为实现最优平均查找长度，应构造如下的二叉排序树（下图只是示意，不涉及具体代码）：
查找方法：
采用二叉排序树的查找方法。每次比较当前节点的关键字与目标关键字，决定向左子树还是右子树递归查找。
查找成功时的平均查找长度：
若节点的层次越低，则查找它所需的比较次数越多。计算查找成功的平均查找长度： $ L_{} = 0.15 + 0.35 + 0.35 + 0.15 = 2.0 $ 使用二叉排序树的查找方法，成功时的平均查找长度降低至 2.0。