浙江高考信息技术 · 浙江普通高等学校招生全国统一考试2017B 信息技术 第 12 题

12.【加试题】某对分査找算法的VB程序段如下:

i = 1: j = 7: s = ""
key = Int(Rnd * 100)
Do While i <= j
   m = (i + j) \ 2
   If key = a(m) Then
      s = s + "M": Exit Do    'Exit Do 表示退出循环
   ElseIf key < a(m) Then
      j = m - 1: s = s + "L"
   Else
      i = m + 1: s = s + "R"
   End If
Loop
Text1.Text = s

数组元素a(1)到a（7）的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是

这题考二分查找过程模拟。拿到题先别急着套公式，盯着循环里 i、j 的变化和 m 的位置，把每次比较 key 与 a(m) 的大小关系按顺序记下来，最后拼出的字符串就是答案。

最容易栽跟头的是把二分查找当成线性查找，或者在判断 key 与 a(m) 大小关系时看错方向。比如 key 比 a(m) 大却误判成 L，或者 key 比 a(m) 小却误判成 R，这样生成的字符串就完全不对。还有一种坑是忽略了数组下标从 1 开始，m = (i + j) \ 2 算出来的是中间位置，若下标搞错，a(m) 取值就错了，导致后续 i、j 调整方向全乱套。另外，有些同学看到选项里有多个字母就瞎猜，不一步步模拟，结果选了个看着像但实际走不通的。

这道题考查的是二分查找算法的流程模拟，核心在于理解循环中 i、j 的更新规则以及根据 key 与 a(m) 大小关系决定走向。命题人喜欢在这种题里挖坑：一是下标从 1 开始，m = (i + j) \ 2 算出的中间位置必须对应正确的数组元素；二是 key 与 a(m) 比较时方向不能搞反；三是循环终止条件 i <= j 要盯紧，一旦 i > j 就退出，不会再有后续操作。拿到题，第一步先明确数组 a(1) 到 a(7) 的值：24, 35, 38, 41, 45, 69, 78。第二步，key 是随机生成的整数（0~99），但题目问的是“可能”显示的内容，意味着我们只需要找到一个 key 值，使得程序输出的字符串与某个选项一致即可，不需要穷举所有 key。第三步，模拟循环过程。初始 i = 1, j = 7, s = ""。第一次循环：m = (1+7)\2 = 4，a(4) = 41。若 key < 41，则 j = 3, s += "L"；若 key > 41，则 i = 5, s += "R"；若 key = 41，则 s += "M" 并退出。我们逐个选项反推需要的 key 范围。选项 A 是 "RL"：第一次必须是 R，说明 key > 41，i 变成 5；第二次必须是 L，说明此时 m = (5+7)\2 = 6，a(6) = 69，key < 69，j 变成 5，s += "L"。此时 i = 5, j = 5，第三次 m = 5，a(5) = 45，若 key > 45 则 i = 6，s += "R"，但选项 A 只有 "RL"，没有第三个字符，说明在第二次之后循环已经结束？不对，i = 5, j = 5 时 m = 5，还会再执行一次，除非 key = 45 才可能中途退出。但选项 A 只有两个字符，所以 A 不可能。选项 B "LMR"：第一次 L，key < 41，j = 3；第二次 M，m = (1+3)\2 = 2，a(2) = 35，key = 35，s += "M"，退出。此时 s = "LM"，没有 R，所以 B 不可能。选项 C "RLR"：第一次 R，key > 41，i = 5；第二次 L，m = 6，a(6) = 69，key < 69，j = 5，s += "L"；此时 i = 5, j = 5，第三次 m = 5，a(5) = 45，若 key > 45，则 i = 6，s += "R"，循环结束（i = 6 > j = 5）。这样 s = "RLR"，完全匹配选项 C。因此只要 key 在 (41, 45) 之间，比如 key = 42，就能得到 "RLR"。选项 D "LRLM"：第一次 L，key < 41，j = 3；第二次 R，m = 2，a(2) = 35，key > 35，i = 3，s += "R"；此时 i = 3, j = 3，第三次 m = 3，a(3) = 38，若 key < 38，则 j = 2，s += "L"；此时 i = 3, j = 2，循环结束，s = "LRL"，没有 M，所以 D 不可能。综上，只有选项 C 是可能的输出。