7.2 顺序查找和折半查找·习题

教材导航 · 返回本节知识

复习入口

7.2 顺序查找和折半查找 · 7.2.1 一般线性表的顺序查找 · 7.2.1.1 有序线性表的顺序查找 · 7.2.2 折半查找 · 7.2.3 分块查找

本节共32题:选择题25题,综合应用题7题。每题答案紧接题目折叠显示。

文字转录进度:32/32题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P274 · 解析P277 · 目视转录

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

A. 顺序存储结构或链式存储结构

B. 散列存储结构

C. 索引存储结构

D. 压缩存储结构

查看答案与解析

答案:A。

顺序查找指从表的一端开始向另一端查找,不要求查找表具有随机存取特性,可以是顺序存储结构或链式存储结构。

单项选择题 02

原书题目P274 · 解析P277 · 目视转录

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

A. 平均时间后者小

B. 平均时间两者相同

C. 平均时间前者小

D. 无法确定

查看答案与解析

答案:B。

对于顺序查找,不管表有序还是无序,成功查找第一个元素比较 1 次,第二个比较 2 次,依此类推。每个元素查找成功的比较次数只与位置有关,与是否有序无关,因此查找成功的平均时间两者相同。

单项选择题 03

原书题目P274 · 解析P278 · 目视转录

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

A. n/2

B. (n+1)/2

C. (n−1)/2

D. n/4

查看答案与解析

答案:B。

有序单链表顺序查找成功的平均查找长度,与无序顺序表或有序顺序表中顺序查找的相同,均为 (n+1)/2。

单项选择题 04

原书题目P274 · 解析P278 · 目视转录

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

A. 5/3

B. 2

C. 7/3

D. 4/3

查看答案与解析

答案:A。

三个元素的查找长度依次为 1、2、3,所以 ASL成功=12×1+13×2+16×3=53\mathrm{ASL}_{成功}=\frac12\times1+\frac13\times2+\frac16\times3=\frac53。

单项选择题 05

原书题目P274 · 解析P278 · 目视转录

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

A. 表必须有序,表可以顺序方式存储,也可以链表方式存储

B. 表必须有序且表中数据必须是整型、实型或字符型

C. 表必须有序,而且只能从小到大排列

D. 表必须有序,且表只能以顺序方式存储

查看答案与解析

答案:D。

二分查找通过下标定位中间位置元素,因此应采用顺序存储。前提是表有序,但从大到小还是从小到大不作要求。

单项选择题 06

原书题目P275 · 解析P278 · 目视转录

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

A. 必然快

B. 取决于表是递增还是递减

C. 在大部分情况下要快

D. 必然不快

查看答案与解析

答案:C。

折半查找在大部分情况下快,但某些特殊情况下顺序查找可能更快。例如查找一个含 1000 个元素的有序表中的第一个元素,顺序查找只比较 1 次,而折半查找将近 10 次。

单项选择题 07

原书题目P275 · 解析P278 · 目视转录

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

A. 最小生成树

B. 平衡二叉树

C. 完全二叉树

D. 满二叉树

查看答案与解析

答案:B。

A 显然排除。折半查找的判定树不一定是完全二叉树,也不一定是满二叉树。每次取中间元素分割,总把数组分成元素个数相差至多 1 的两个子数组,因此判定树的两子树高度差的绝对值不超过 1,是平衡二叉树。

单项选择题 08

原书题目P275 · 解析P278 · 目视转录

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

A. 相同

B. 有时不相同

C. 完全不相同

D. 无法比较

查看答案与解析

答案:B。

折半查找的平均查找长度和最大查找长度都是 O(log⁡2n)O(\log_2n)。二叉排序树的性能与数据输入顺序有关,最好情况下平均查找长度与折半查找相同,最坏形成单支树时查找长度为 O(n)O(n)。

单项选择题 09

原书题目P275 · 解析P278 · 目视转录

在有 11 个元素的有序表 A[1,2,…,11] 中进行折半查找(⌊(low+high)/2⌋\lfloor(low+high)/2\rfloor),查找元素 A[11] 时,被比较的元素下标依次是( )。

A. 6,8,10,11

B. 6,9,10,11

C. 6,7,9,11

D. 6,8,9,11

查看答案与解析

答案:B。

第一次 mid=⌊(1+11)/2⌋=6,第二次 mid=⌊(7+11)/2⌋=9,第三次 mid=⌊(10+11)/2⌋=10,第四次 mid=11。

单项选择题 10

原书题目P275 · 解析P278 · 目视转录

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

A. 1

B. 2

C. 4

D. 6

查看答案与解析

答案:B。

开始 low 指向 13,high 指向 134,mid 指向 50,比较第一次,90>50;将 low 指向 62,high 仍指向 134,mid 指向 90,第二次比较即找到。

单项选择题 11

原书题目P275 · 解析P278 · 目视转录

若有序表的关键字序列为 {b,c,d,e,f,g,q,r,s,t},则二分查找关键字 b 的过程中,进行比较的关键字依次为( )。

A. f,c,b

B. f,d,b

C. g,c,b

D. g,d,b

查看答案与解析

答案:A。

折半查找中 mid 的取值方式必须确定,要么始终向上取整,要么始终向下取整,不能混用。A 三次比较 f、c、b,均向下取整,符合要求。B 第一次 f 向下取整,第二次 d 向上取整,取法不同;C 第一次 g 向上取整,第二次 c 向下取整,不符合;D 第一次 g 向上取整,第二次 d 是正中间元素,第三次 b 向下取整,也不符合。

单项选择题 12

原书题目P275 · 解析P278 · 目视转录

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

A. ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil

B. ⌊log⁡2(n+1)⌋−1\lfloor\log_2(n+1)\rfloor-1

C. ⌊log⁡2n⌋\lfloor\log_2n\rfloor

D. ⌊log⁡2n⌋−1\lfloor\log_2n\rfloor-1

查看答案与解析

答案:A。

对 n 个结点的判定树,原书由满树结点关系 n=2h−1n=2^h-1 给出高度 h=⌈log⁡2(n+1)⌉h=\lceil\log_2(n+1)\rceil。

另解:特殊值代入法。直接代入 n=1、n=2,只有 A 满足要求。

单项选择题 13

原书题目P275 · 解析P279 · 目视转录

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

A. 4

B. 5

C. 6

D. 7

查看答案与解析

答案:A、B。

有两种方法。一是画出查找过程形成的判定树,最小、最大分支高度分别对应最少、最多比较次数。长度为 15 时判定树是满树,最多与最少次数相等。二是直接用公式求最大分支高度 H=⌈log⁡2(n+1)⌉=5H=\lceil\log_2(n+1)\rceil=5,即最多比较 5 次;判定树不是满树,且各分支高度至多相差 1,因此至少比较 4 次。

注意:求成功或失败的平均查找长度,需要画判定树。对长度为 n 的有序表,折半查找成功与失败的最多比较次数相同,均为 ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil。

单项选择题 14

原书题目P275 · 解析P279 · 目视转录

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

A. 37/12

B. 35/12

C. 39/13

D. 49/13

查看答案与解析

答案:A、D。

假设有序表为 A[0..11],折半查找判定树的根为 5,第二层为 2、8,第三层为 0、3、6、10,第四层为 1、4、7、9、11。查找成功的平均查找长度为 (1+2×2+3×4+4×5)/12=37/12;查找失败的平均查找长度为 (3×3+4×10)/13=49/13。

注意:先根据 n 画出判定树。失败结点是虚构的方形外部结点,失败 ASL 应计至它上一层的圆形结点,不把方形结点本身计入比较次数。

单项选择题 15

原书题目P275 · 解析P279 · 目视转录

下列关于查找的说法中,正确的是( )。(注:涉及下节内容。)

A. 若数据元素保持有序,则查找时就可以采用折半查找法

B. 折半查找与二叉查找树的时间性能在最坏情况下是相同的

C. 折半查找法的平均查找长度一定小于顺序查找法

D. 折半查找法查找一个元素大约需要 O(log⁡2n)O(\log_2n) 次关键字比较

查看答案与解析

答案:D。

折半查找不仅要求元素有序,还要求顺序存储,A 错误。折半查找最坏时间为 O(log⁡2n)O(\log_2n),二叉查找树最坏为 O(n)O(n),B 错误。当各元素查找概率不同时,折半查找的平均查找长度可能大于顺序查找,C 错误。

单项选择题 16

原书题目P275 · 解析P279 · 目视转录

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

A. 数据分成若干块,每块内数据有序

B. 数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块

C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块

D. 数据分成若干块,每块(除最后一块外)中数据个数需相同

查看答案与解析

答案:B。

通常情况下,分块查找结构不要求每个索引块中的元素个数都相等。

单项选择题 17

原书题目P275 · 解析P279 · 目视转录

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

A. 50

B. 125

C. 500

D. ⌈log⁡22500⌉\lceil\log_22500\rceil

查看答案与解析

答案:A。

设块长为 b,索引表包含 n/b 项,索引表 ASL=(n/b+1)/2,块内 ASL=(b+1)/2,总 ASL=(b+n/b+2)/2。对 b+n/b,由均值不等式知 b=n/b 时最小,即 b=nb=\sqrt n。故最理想块长为 2500=50\sqrt{2500}=50。

单项选择题 18

原书题目P275 · 解析P279 · 目视转录

设顺序存储的某线性表共有 123 个元素,按分块查找要求等分为 3 块。若索引表采用顺序查找来确定子块,确定子块中也采用顺序查找,则等概率情况下分块查找成功的平均查找长度为( )。

A. 21

B. 23

C. 41

D. 62

查看答案与解析

答案:B。

索引表有 3 项,每块有 41 个元素,平均查找长度为 (3+1)/2+(41+1)/2=23。

也可按算法模拟:A 块元素的查找长度分别为 2,3,…,42;B 块比 A 块多一步,分别为 3,4,…,43;C 块分别为 4,5,…,44。所以 ASL=(2+3+…+42+3+4+…+43+4+5+…+44)/123=23。

单项选择题 19

原书题目P276 · 解析P280 · 目视转录

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

A. 10

B. 14

C. 16

D. 21

查看答案与解析

答案:C。

为使效率最高,每个索引块大小取 65025=255\sqrt{65025}=255,索引表也有 255 项。索引项和索引块内部都采用折半查找,最多比较 ⌈log⁡2(255+1)⌉+⌈log⁡2(255+1)⌉=16\lceil\log_2(255+1)\rceil+\lceil\log_2(255+1)\rceil=16 次。

单项选择题 20

原书题目P276 · 解析P280 · 目视转录

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

A. 4

B. 5

C. 6

D. 7

查看答案与解析

答案:B。

查找失败时,关键字最多比较次数为树高,即 ⌊log⁡2n⌋+1\lfloor\log_2n\rfloor+1 或 ⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil。本题 n=16,最多比较 5 次。判定树中的方形结点是虚构的,不计入比较次数。

单项选择题 21

原书题目P276 · 解析P280 · 目视转录

【2015 统考真题】下列选项中,不能构成折半查找中关键字比较序列的是( )。

A. 500,200,450,180

B. 500,450,200,180

C. 180,500,200,450

D. 180,200,500,450

查看答案与解析

答案:A。

画出查找路径图,折半查找判定树是一棵二叉排序树,应满足二叉排序树要求。A 中先从 200 进入其右侧到 450,说明目标大于 200,但之后却访问小于 200 的 180,不符合要求。

单项选择题 22

原书题目P276 · 解析P280 · 目视转录

【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 位于数组中间位置

查看答案与解析

答案:B。

程序采用跳跃式顺序查找法查找升序数组中的 x。显然,x 越靠前,比较次数越少。

单项选择题 23

原书题目P276 · 解析P280 · 目视转录

【2017 统考真题】下列二叉树中,可能成为折半查找判定树(不含外部结点)的是( )。

A. 候选树A

B. 候选树B

C. 候选树C

D. 候选树D

查看答案与解析

答案:A。

给定有序查找表,其折半查找判定树确定且唯一。若 mid 向上取整,表长 2n+1 时左右子树各有 n 个元素,表长 2n 时左子树 n 个、右子树 n−1 个,即左子树元素数与右子树相等或多一个;若 mid 向下取整,则左子树元素数与右子树相等或少一个。

A 中每个左子树都与右子树结点数相等或多一个,符合向上取整。B、C、D 中,有的左子树多一个,有的少一个,不符合统一的取整规则。

单项选择题 24

原书题目P276 · 解析P280 · 目视转录

【2023 统考真题】对含 600 个元素的有序顺序表进行折半查找,关键字间的比较次数最多是( )。

A. 9

B. 10

C. 30

D. 300

查看答案与解析

答案:B。

最多比较次数不超过判定树高度 h=⌈log⁡2(n+1)⌉h=\lceil\log_2(n+1)\rceil,代入 n=600 得 10。

单项选择题 25

原书题目P276 · 解析P280 · 目视转录

【2024 统考真题】下列数据结构中,不适合直接使用折半查找的是( )。

Ⅰ.有序链表 Ⅱ.无序数组 Ⅲ.有序静态链表 Ⅳ.无序静态链表

A. 仅Ⅰ、Ⅲ

B. 仅Ⅱ、Ⅳ

C. 仅Ⅱ、Ⅲ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

查看答案与解析

答案:D。

折半查找必须满足两个条件:① 数组或顺序表。相邻两次查找可能距离很远,如依次访问下标 n/2、n/4、n/8,…;若用链表或静态链表,会使时间复杂度很高。② 有序。只有有序才能根据上一次比较情况舍弃一半序列。

综合应用题

综合应用题 01

原书题目P276 · 解析P281 · 目视转录

对有 n 个元素的有序顺序表和无序顺序表进行顺序查找,试就下列三种情况讨论两者在相等查找概率时平均查找长度是否相同。

  1. 查找失败。
  2. 查找成功,且表中只有一个关键字等于给定值 k 的元素。
  3. 查找成功,表中有若干关键字等于给定值 k 的元素,要求一次查找能找出所有元素。
查看答案与解析
  1. 不同。有序表找到关键字比查找值大的元素时就停止并报告失败,不必查到表尾;无序表必须查到表尾才能确定失败。
  2. 相同。两者找到关键字等于给定值的元素时都停止查找。
  3. 不同。有序表中相同关键字元素相邻排列,找到第一个就可连续找到其他相同元素;无序表必须查找全表才能找出所有相同关键字元素,因此时间不同。

综合应用题 02

原书题目P277 · 解析P281 · 目视转录

有序顺序表中的元素依次为 017,094,154,170,275,503,509,512,553,612,677,765,897,908。

  1. 画出折半查找的判定树。
  2. 查找 275 或 684 时,依次与表中哪些元素比较?
  3. 计算查找成功和查找不成功的平均查找长度。
查看答案与解析
  1. 判定树如下,空指针位置可补上外部失败结点。
                   509
              /           \
            154           677
           /   \         /   \
         017   275     553    897
           \   / \     / \    / \
           094 170 503 512 612 765 908
  1. 查找 275,依次比较 509、154、275,共 3 次;查找 684,依次比较 509、677、897、765,共 4 次。
  2. 成功时到达某个实际结点,ASL成功=(1+2×2+3×4+4×7)/14=45/14\mathrm{ASL}_{成功}=(1+2\times2+3\times4+4\times7)/14=45/14。失败时到达虚构的外部结点,最后一次比较的是其父结点,所以 ASL不成功=(3×1+4×14)/15=59/15\mathrm{ASL}_{不成功}=(3\times1+4\times14)/15=59/15。

综合应用题 03

原书题目P277 · 解析P281 · 目视转录

已知有序顺序表 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],在其中折半查找。特殊情况:若 X>A[8n−1],则查找失败。

  1. 画出该过程的判定树。
  2. 计算相等查找概率下查找成功的平均查找长度。
查看答案与解析
  1. 先在 A[7],A[15],…,A[8n−1] 内顺序查找,再在区间内折半查找。判定树可用每个区间的结点关系表示如下(括号内为查找成功的比较次数)。第 i 块(i=1,…,n),端点 A[8i−1] 比较 i 次;块内折半树为:
           A[8i-5] (i+1)
           /           \
 A[8i-7] (i+2)     A[8i-3] (i+2)
     /      \           /      \
 A[8i-8] A[8i-6]   A[8i-4] A[8i-2]
  (i+3)   (i+3)     (i+3)   (i+3)

例如第一块的树根为下标 3,子结点为 1、5,叶结点为 0、2、4、6;第二块树根为 11,子结点为 9、13,叶结点为 8、10、12、14。索引下标 7、15、…、8n−1 依次比较 1、2、…、n 次。

  1. 每个关键字的成功查找概率为 1/(8n)。第一块端点比较 1 次,块内各层比较 2、3、4 次;第二块先顺序比较 2 次,再进入折半查找;依此类推。因此
ASL成功=18n∑i=1n[i+(i+1)+2(i+2)+4(i+3)]=18n∑i=1n(8i+17)=1n∑i=1ni+178=n+12+178.\begin{aligned} \mathrm{ASL}_{成功} &=\frac1{8n}\sum_{i=1}^{n}\bigl[i+(i+1)+2(i+2)+4(i+3)\bigr]\\ &=\frac1{8n}\sum_{i=1}^{n}(8i+17) =\frac1n\sum_{i=1}^{n}i+\frac{17}{8} =\frac{n+1}{2}+\frac{17}{8}. \end{aligned}

综合应用题 04

原书题目P277 · 解析P282 · 目视转录

写出折半查找的递归算法。初始调用时,low 为 1,high 为 ST.length。

查看答案与解析

整理注记

原书递归折半查找代码的递归调用前漏写return。左右分支都应返回递归调用的结果,否则外层函数无法可靠地返回查找位置。

根据起始与终止位置将序列一分为二,判断关键字在哪一部分,再用新序列的起止位置递归求解。原书代码如下。

typedef struct {
    ElemType *elem;                 // 按实际长度分配,0 号留空
    int length;
} SSTable;

int BinSearchRec(SSTable ST, ElemType key, int low, int high) {
    if (low > high)
        return 0;
    int mid = (low + high) / 2;
    if (key > ST.elem[mid])
        BinSearchRec(ST, key, mid + 1, high);
    else if (key < ST.elem[mid])
        BinSearchRec(ST, key, low, mid - 1);
    else
        return mid;
}

规模为 n 的问题经多次递归变为规模减半的子问题,时间复杂度为 O(log⁡2n)O(\log_2n)。递归工作栈规模与递归深度有关,空间复杂度也为 O(log⁡2n)O(\log_2n)。

转录核对:原书两个递归分支前漏写了 return。实际使用时应分别写成 return BinSearchRec(...),将递归结果返回调用者。

综合应用题 05

原书题目P277 · 解析P282 · 目视转录

线性表各结点检索概率不等时,可用如下策略提高顺序检索效率:若找到指定结点,将该结点与其前驱结点(若存在)交换,使经常被检索的结点尽量位于表前端。试设计在顺序结构和链式结构的线性表上实现此策略的顺序检索算法。

查看答案与解析

整理注记

顺序扫描条件应先判断i<n,再访问R[i],避免未找到时越界;命中首元素i=0时也应返回其有效位置,不能落入“未找到”的-1分支。可仅在i>0时交换,并在所有命中情形返回交换后的位置。

检索时从表头开始向后顺序扫描,找到指定结点后与前趋结点交换。顺序存储算法如下。

int SeqSrch(RecType R[], ElemType k) {
    int i = 0;
    while ((R[i].key != k) && (i < n))
        i++;
    if (i < n && i > 0) {
        temp = R[i];
        R[i] = R[i - 1];
        R[i - 1] = temp;
        return --i;                // 返回交换后的位置
    }
    else return -1;
}

链表实现请读者自行思考:基本思想与上述相似,但交换两个结点前,需要保存指向前一结点的指针。

转录核对:以上保留原书流程。实际代码应先判断 i<n 再访问 R[i],避免越界;若在首元素找到,也应返回成功位置 0。n 和 temp 需由调用环境提供或显式声明。

综合应用题 06

原书题目P277 · 解析P282 · 目视转录

已知一个 n 阶矩阵 A 和目标值 k。矩阵无重复元素,每行从左到右升序,每列从上到下升序。请设计一个时间上尽可能高效的算法,判断矩阵中是否存在 k。例如矩阵

[147258369]\begin{bmatrix}1&4&7\\2&5&8\\3&6&9\end{bmatrix}

目标值为 8,判定存在。要求:

  1. 给出基本设计思想。
  2. 用 C 或 C++ 描述算法,关键处注释。
  3. 说明时间和空间复杂度。
查看答案与解析
  1. 从矩阵右上角(最右列)开始比较。若当前元素小于目标值,向下找更大元素;若大于目标值,从其左侧依次比较。若目标存在,只可能在保留的区域中。
  2. 原书算法如下。
bool findkey(int A[][], int n, int k) {
    int i = 0, j = n - 1;
    while (i < n && j >= 0) {        // 离开边界时查找结束
        if (A[i][j] == k) return true;
        else if (A[i][j] > k) j--;   // 向左移动
        else i++;                   // 向下移动
    }
    return false;
}
  1. 比较次数不超过 2n,时间复杂度为 O(n)O(n),空间复杂度为 O(1)O(1)。

转录核对:原书形参 int A[][] 省略了列维度;实际 C/C++ 程序需按矩阵的具体存储方式补充列维度或相应类型。

综合应用题 07

原书题目P277 · 解析P283 · 目视转录

【2013 统考真题】设包含 4 个数据元素的集合 S={‘do’,‘for’,‘repeat’,‘while’},各元素查找概率为 p₁=0.35、p₂=0.15、p₃=0.15、p₄=0.35。将 S 保存在长度为 4 的顺序表中,采用折半查找,查找成功的平均查找长度为 2.2。

  1. 若采用顺序存储且要求平均查找长度更短,元素应如何排列?采用何种查找方法?查找成功 ASL 是多少?
  2. 若采用链式存储且要求平均查找长度更短,元素应如何排列?采用何种方法?查找成功 ASL 是多少?
查看答案与解析
  1. 折半查找要求元素有序顺序存储,字符串默认按字典序排列:从左到右逐位比较,某位比出大小后不再比较后续字符,如 abd<acd、abc<abcd。本题 do<for<repeat<while。各元素概率不同,折半查找未必优于顺序查找。采用顺序查找时,元素按查找概率降序排列,ASL 最小。因此可排列为 do、while、for、repeat(同概率元素可交换),采用顺序查找,成功 ASL=0.35×1+0.35×2+0.15×3+0.15×4=2.1,比折半查找短。
  2. 答案一:构成按查找概率降序排列的单链表,采用顺序查找,与顺序表性能一样,成功 ASL=2.1。

答案二:采用二叉链表构造二叉排序树,使用二叉排序树的查找方法。可采用下列两种树形。

      for                 repeat
     /   \                /    \
   do   while            do    while
        /                  \
     repeat                for

两者成功 ASL 均为 0.15×1+0.35×2+0.35×2+0.15×3=2.0。