---
marp: true
theme: a4
paginate: true
footer: 数据结构 · 期末笔试 A 卷 · 参考答案 – 仅供教师使用
---

# 期末笔试 A 卷 – 参考答案与评分标准

<span class="kicsi">可以给部分分。伪代码填空中，任何明确、正确的答案都可以接受（例如用 `<>` 或 `!=` 代替 `≠`，用 `null` 代替 `Nil`）。细小的语法问题不扣分。</span>

## 一、判断题 <span class="pont">14 分</span>

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| <strong>对</strong> | <strong>错</strong> | <strong>错</strong> | <strong>对</strong> | <strong>错</strong> | <strong>对</strong> | <strong>错</strong> | <strong>对</strong> | <strong>对</strong> | <strong>对</strong> | <strong>错</strong> | <strong>对</strong> | <strong>对</strong> | <strong>错</strong> |

<span class="kicsi">有争议之处的说明：2 – 顺序访问，O(n) · 5 – 哨兵结点要占用空间 · 7 – 只改变下标，O(1) · 12 – 退化的树（例如按有序顺序插入） · 14 – 必须用 `equals`。</span>

## 二、选择题 <span class="pont">10 分</span>

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| <strong>b</strong> | <strong>c</strong> | <strong>c</strong> | <strong>b</strong> | <strong>b</strong> | <strong>b</strong> | <strong>a</strong> | <strong>b</strong> | <strong>a</strong> | <strong>b</strong> |

<span class="kicsi">7:1000 + (2 · 10 + 3) · 4 = 1092 · 9:5 + (1 + 2) · 4 − 3 = 14 · 10:(6 + 3) mod 8 = 1。</span>

## 三、步数 <span class="pont">10 分</span>

| a) | b) | c) | d) | e) | f) | g) | h) | i) | j) |
|---|---|---|---|---|---|---|---|---|---|
| O(1) | O(n) | O(n) | O(1) | O(n) | O(1) | O(log n) | O(log n) | O(n log n) | O(2ⁿ) |

## 四、栈 <span class="pont">7 分</span>

输出：<strong>`ATAD ERUTCURTS`</strong> <span class="pontozas">（5 分；如果单词顺序或空格有错：3 分）</span>
一般地：把文本中的<strong>每个单词分别逆序</strong>，单词的顺序和空格保持不变。<span class="pontozas">（2 分）</span>

## 五、队列 <span class="pont">7 分</span>

输出：<strong>`2 4 6 3 1 5`</strong> <span class="pontozas">（5 分；至多一个数字错误时：3 分）</span>
一般地：k = 2 时的<strong>约瑟夫问题</strong>：<em>n</em> 个人围成一圈，每隔一个人淘汰一个；输出是淘汰的顺序，最后一个数是幸存者。<span class="pontozas">（2 分；答“每隔一个元素取出/输出一个”也给满分）</span>

## 六、在纸上执行算法 <span class="pont">8 分</span>

<strong>a)</strong> 插入排序 <span class="pontozas">（每步 1 分，共 4 分）</span>

| 步骤 | 1（插入 2） | 2（插入 9） | 3（插入 1） | 4（插入 5） |
|---|---|---|---|---|
| 数组 | [2, 6, 9, 1, 5] | [2, 6, 9, 1, 5] | [1, 2, 6, 9, 5] | [1, 2, 5, 6, 9] |

<strong>b)</strong> 二分查找，x = 45 <span class="pontozas">（每步 1 分，共 4 分）</span>

| 步骤 | left | right | k | A[k] | 判断 |
|---|---|---|---|---|---|
| 1 | 1 | 10 | 5 | 30 | 30 < 45 → left ← 6 |
| 2 | 6 | 10 | 8 | 52 | 52 > 45 → right ← 7 |
| 3 | 6 | 7 | 6 | 38 | 38 < 45 → left ← 7 |
| 4 | 7 | 7 | 7 | 45 | 找到：下标 7 |

---

## 七、二叉搜索树 <span class="pont">12 分</span>

<div class="ket-hasab">
<div>

<strong>a)</strong> 这棵树 <span class="pontozas">（3 分）</span>

```text
            45
          /    \
        20      70
       /  \    /  \
     10   30  60   80
         /  \
       25    35
```

<strong>c)</strong> 删除 20 之后 <span class="pontozas">（3 分）</span>

```text
            45
          /    \
        25      70
       /  \    /  \
     10   30  60   80
            \
             35
```

</div>
<div>

<strong>b)</strong> 遍历序列 <span class="pontozas">（各 1 分）</span>

- 先序：<strong>45 20 10 30 25 35 70 60 80</strong>
- 中序：<strong>10 20 25 30 35 45 60 70 80</strong>
- 后序：<strong>10 25 35 30 20 60 80 70 45</strong>

<strong>c)</strong> 20 有<strong>两个孩子</strong>（情况 3）：由右子树中最小的元素，即<strong>中序后继（25）</strong>顶替，然后删除 25（叶子）。<span class="pontozas">（说明情况 1 分，树正确 2 分；用中序前驱（10）也正确）</span>

<strong>d)</strong> 高度：<strong>3</strong>（45 – 20 – 30 – 25）。找到 35 需要 <strong>4</strong> 次比较（45、20、30、35）。<span class="pontozas">（高度 1 分，比较次数 2 分）</span>

</div>
</div>

## 八至十、伪代码填空 <span class="pont">每个空缺处 2 分</span>

<div class="ket-hasab">
<div>

<strong>八、在二叉搜索树中查找</strong> <span class="pontozas">（10 分）</span>

| | 答案 |
|---|---|
| (1) | `Root` |
| (2) | `≠` |
| (3) | `≠` |
| (4) | `<`（`≤` 也可以） |
| (5) | `Elem[P].Right` |

<strong>九、哨兵查找</strong> <span class="pontozas">（10 分）</span>

| | 答案 |
|---|---|
| (1) | `x` |
| (2) | `Head` |
| (3) | `≠` |
| (4) | `Elem[P].Next` |
| (5) | `=` |

</div>
<div>

<strong>十、在表尾插入</strong> <span class="pontozas">（12 分）</span>

| | 答案 |
|---|---|
| (1) | `Nil` |
| (2) | `=` |
| (3) | `P` |
| (4) | `≠` |
| (5) | `Elem[Q].Next` |
| (6) | `Elem[Q].Next` |

<span class="kicsi">八/（4）：如果 x = Elem[P].Key，循环就不会再执行，所以 `≤` 也能得到正确的结果。九：由于有哨兵，循环条件中不需要 `P ≠ End` 的判断。十/（1）：如果新结点的 `Next` 字段不是 Nil，链表的末尾就“悬空”了 – 这是常见的错误。</span>

</div>
</div>

## 成绩

| 分数 | 0–49 | 50–61 | 62–74 | 75–86 | 87–100 |
|---|---|---|---|---|---|
| 成绩 | 不及格（1） | 及格（2） | 中等（3） | 良好（4） | 优秀（5） |