题目

设包含 4 个数据元素的集合 S = {"do", "for", "repeat", "while"}，各元素的查找概率依次为：p₁ = 0.35, p₂ = 0.15, p₃ = 0.15, p₄ = 0.35。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2。请回答：

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

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

解析

预备：ASL 公式回顾

平均查找长度 ，其中 是元素 i 的查找概率， 是查找该元素时的比较次数。

题面已给折半查找 ASL = 2.2（按字典序 do, for, repeat, while 排成顺序表后的折半判定树，比较次数 c = 2, 3, 1, 2 → ASL = 0.35×2 + 0.15×3 + 0.15×1 + 0.35×2 = 2.2）。要求 (1) 和 (2) 都得到比 2.2 更短的 ASL。

(1) 顺序存储 + 顺序查找

答案：将元素按查找概率非升序排列，例如顺序为 do (0.35), while (0.35), for (0.15), repeat (0.15)；用顺序查找；ASL = 2.10。

为什么按概率非升序排？

顺序查找时，第 i 位元素的比较次数 = i（从 1 起）。ASL = 。要使 ASL 最小，概率大的位置应小——即把高概率元素放最前面。这就是经典的"按概率降序排列"贪心：

位置 i	元素		比较次数
1	do	0.35	1	0.35
2	while	0.35	2	0.70
3	for	0.15	3	0.45
4	repeat	0.15	4	0.60

ASL = 0.35 + 0.70 + 0.45 + 0.60 = 2.10（< 2.2 ✓）。

两个 0.35 的元素谁前谁后无所谓（do 和 while 互换，ASL 不变）；两个 0.15 同理。

(2) 链式存储 + 二叉排序树查找

答案：用二叉链表存一棵二叉排序树（BST），按概率分布构造一棵让"加权深度和最小"的最优 BST；例如以 for 为根的下列 BST，ASL = 2.00。

            for (0.15)
           /         \
       do (0.35)   while (0.35)
                   /
              repeat (0.15)

为什么链式存储更优？

链式存储不能折半查找（无随机访问），但能存树形结构——具体地，把 S 中的元素按字典序组织成 BST，查找时按 BST 规则下降。每个元素的比较次数 = 该元素在 BST 中的层数（根算 1 层）。

要让 ASL = 最小，就是经典的「最优二叉搜索树（OBST）」问题。4 个元素枚举所有合法 BST 形态（共 棵）的 ASL：

BST 根	形态描述	各结点深度（do, for, repeat, while）	ASL
do	退化向右链	1, 2, 3 或 4, 2 或 3 或 4	2.10 ~ 2.50
for	均衡：左 do，右 while-下挂 repeat	2, 1, 3, 2	2.00 ★
repeat	均衡：左 do-下挂 for，右 while	2, 3, 1, 2	2.00 ★
while	退化向左	多种	≥ 2.10

最优 ASL = 2.00（< 2.10 < 2.2 ✓）。

验证以 for 为根的 BST：

元素		深度
do	0.35	2	0.70
for	0.15	1	0.15
repeat	0.15	3	0.45
while	0.35	2	0.70

ASL = 0.70 + 0.15 + 0.45 + 0.70 = 2.00。

编者注（生僻术语）：「最优二叉搜索树（Optimal BST）」要在保持 BST 性质（左 < 根 < 右）的前提下，让加权深度和最小。一般用区间 DP 解，时间 ；本题 4 个元素枚举即可。本题"概率最大不一定在根"——do 和 while 概率都最大，但根是 for（中位附近的元素），这是 OBST 与"哈夫曼树"（无 BST 限制）的关键区别，别搞混。