---
marp: true
theme: a4
paginate: true
footer: 数据结构 · 期末笔试 · A 卷
---

# 数据结构 – 期末笔试

<div class="fejlec">
<div>姓名：</div>
<div>学号：</div>
<div>日期：</div>
</div>

<strong>考试时间：</strong>60 分钟 · <strong>满分：</strong>100 分 · <strong>辅助工具：</strong>不得使用。
伪代码中数组下标<strong>从 1 开始</strong>。链表结点的字段为 `Elem[P].Value`、`Elem[P].Next`；树结点的字段为 `Elem[P].Key`、`Elem[P].Left`、`Elem[P].Right`。空指针记作 <strong>Nil</strong>。

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

在正确的答案下打 X!

<div class="ih">

| # | 题目 | 对 | 错 |
|---|---|---|---|
| 1. | 数组的元素在内存中连续地依次存放。 | | |
| 2. | 单链表的第 <em>i</em> 个元素可以在 O(1) 步内访问。 | | |
| 3. | 二分查找在无序数组上也总能给出正确的结果。 | | |
| 4. | 使用动态数据结构可以实现资源共享。 | | |
| 5. | 空的带哨兵链表不需要存储空间，因为其中没有存放任何元素。 | | |
| 6. | 栈是一种后进先出（LIFO）的数据结构。 | | |
| 7. | 在循环队列中，出队需要 O(n) 步，因为要把元素向前移动。 | | |
| 8. | 插入排序在已经有序的数组上只需 O(n) 步。 | | |
| 9. | 快速排序在最坏情况下需要 O(n²) 步。 | | |
| 10. | 归并排序是稳定的排序算法。 | | |
| 11. | 二叉搜索树总是平衡的二叉树。 | | |
| 12. | 在二叉搜索树中查找可能和在链表中查找一样慢。 | | |
| 13. | 动态数据结构使用不当会导致内存泄漏。 | | |
| 14. | 在 Java 中比较两个 `String` 的内容必须使用 `==` 运算符。 | | |

</div>

---

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

圈出唯一正确的答案！

<strong>1.</strong> 单链表<strong>不可能</strong>具有下面哪个性质？
<div class="mcq n4"><p>a) 链式存储</p><p>b) 直接访问</p><p>c) 同构</p><p>d) 动态</p></div>

<strong>2.</strong> 二叉树作为一种数据结构是：
<div class="mcq n4"><p>a) 异构的</p><p>b) 可直接访问的</p><p>c) 层次的</p><p>d) 以上都不对</p></div>

<strong>3.</strong> 带哨兵链表的元素可以：
<div class="mcq n4"><p>a) 按中序访问</p><p>b) 直接访问</p><p>c) 顺序访问</p><p>d) 以上都不对</p></div>

<strong>4.</strong> 哪种数据结构可以<strong>直接</strong>访问？
<div class="mcq n4"><p>a) 双向链表</p><p>b) 一维数组</p><p>c) 链栈</p><p>d) 循环链表</p></div>

<strong>5.</strong> 按递增顺序给出二叉搜索树中所有键的是：
<div class="mcq n4"><p>a) 先序遍历</p><p>b) 中序遍历</p><p>c) 后序遍历</p><p>d) 层序遍历</p></div>

<strong>6.</strong> 在 <em>n</em> 个元素的有序数组中，二分查找需要多少步？
<div class="mcq n4"><p>a) O(1)</p><p>b) O(log n)</p><p>c) O(n)</p><p>d) O(n log n)</p></div>

<strong>7.</strong> 矩阵 `int A[6][10]` 从地址 1000 开始按行优先存储，元素 4 字节，下标<strong>从 0 开始</strong>。`A[2][3]` 的地址是多少？
<div class="mcq n4"><p>a) 1092</p><p>b) 1132</p><p>c) 1128</p><p>d) 1052</p></div>

<strong>8.</strong> 哪种排序至多进行 <em>n</em> − 1 次交换？
<div class="mcq n4"><p>a) 冒泡排序</p><p>b) 选择排序</p><p>c) 插入排序</p><p>d) 快速排序</p></div>

<strong>9.</strong> 后缀表达式 `5 1 2 + 4 * + 3 −` 的值是多少？
<div class="mcq n4"><p>a) 14</p><p>b) 12</p><p>c) 18</p><p>d) 20</p></div>

<strong>10.</strong> 在有 8 个元素（下标 0–7）的循环队列中，`front = 6`,`count = 3`。下一个入队的元素放在哪个下标处？
<div class="mcq n4"><p>a) 0</p><p>b) 1</p><p>c) 9</p><p>d) 7</p></div>

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

用大O记号写出各操作的步数（<em>n</em> 为元素个数）！

| | 操作 | 步数 |
|---|---|---|
| a) | 访问数组的第 <em>i</em> 个元素 | |
| b) | 在 <em>n</em> 个元素的数组中顺序查找（最坏情况） | |
| c) | 向 <em>n</em> 个元素的有序数组中插入一个新元素，使其仍然有序 | |
| d) | 在单链表的表头插入 | |
| e) | 删除单链表的表尾 | |
| f) | 用数组实现的栈的 push 和 pop | |
| g) | 从 <em>n</em> 个元素的堆中取出最大值 | |
| h) | 在平衡二叉搜索树中查找 | |
| i) | 归并排序 | |
| j) | <em>n</em> 个盘子的汉诺塔（移动次数） | |

---

## 四、代码阅读：栈 <span class="pont">7 分</span>

下面的程序片段输出什么？一般地说，它对任意文本做了什么？（`Stack` 是存放字符的栈。）

```java
String t = "DATA STRUCTURE";
Stack s = new Stack();
for (char c : t.toCharArray()) {
    if (c != ' ') s.push(c);
    else {
        while (!s.isEmpty()) System.out.print(s.pop());
        System.out.print(' ');
    }
}
while (!s.isEmpty()) System.out.print(s.pop());
```

<div class="kitoltes szeles"><table><tr><td>输出</td><td></td></tr><tr><td>一般地</td><td></td></tr></table></div>

## 五、代码阅读：队列 <span class="pont">7 分</span>

下面的程序片段输出什么？如果把 1, 2, …, <em>n</em> 放入队列，一般地说它解决了哪个著名的问题？

```java
Queue q = new Queue();
for (int i = 1; i <= 6; i++) q.enqueue(i);
while (q.size() > 1) {
    q.enqueue(q.dequeue());
    System.out.print(q.dequeue() + " ");
}
System.out.print(q.dequeue());
```

<div class="kitoltes szeles"><table><tr><td>输出</td><td></td></tr><tr><td>一般地</td><td></td></tr></table></div>

---

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

<strong>a)</strong> 用<strong>插入排序</strong>对数组 `[6, 2, 9, 1, 5]` 排序！写出外层循环每一步之后数组的状态！

<div class="valasz h2" style="height: 22mm"></div>

<strong>b)</strong> 在下面的数组（下标从 1 开始）中用<strong>二分查找</strong>查找 `45`!写出每一步的 `left`、`right` 和 `k` 的值！ `A = [4, 9, 13, 21, 30, 38, 45, 52, 60, 71]`

<div class="valasz h2" style="height: 22mm"></div>

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

<strong>a)</strong> 向空的二叉搜索树中依次插入下列键，并画出这棵树！
`45, 20, 70, 10, 30, 60, 80, 25, 35`

<div class="valasz h3" style="height: 38mm"></div>

<strong>b)</strong> 写出这棵树的先序、中序和后序遍历序列！

<div class="kitoltes">

| | 遍历序列 |
|---|---|
| 先序 | |
| 中序 | |
| 后序 | |

</div>

<strong>c)</strong> 从 a) 得到的树中删除键 `20`!画出结果，并说明这是删除的哪一种情况！

<div class="valasz h3" style="height: 38mm"></div>

<strong>d)</strong> a) 得到的树的高度是多少？找到 `35` 需要多少次键比较？

<div class="valasz h1"></div>

---

第八至十题中请补全伪代码！每个空缺处是一个表达式、一个指针或一个<strong>关系运算符</strong>（=、≠、<、>、≤、≥）。把答案写在代码旁边的表格中！

## 八、在二叉搜索树中查找 <span class="pont">5 × 2 = 10 分</span>

函数返回键为 `x` 的结点的指针；如果没有这个键，返回 Nil。<strong>Root</strong> 指针指向树的根。

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

```text
Function Search(Root, x)
  P ← __(1)__
  While P __(2)__ Nil and
        Elem[P].Key __(3)__ x
    If x __(4)__ Elem[P].Key then
      P ← Elem[P].Left
    else
      P ← __(5)__
    End if
  End while
  Return P
End function
```

</div>
<div class="kitoltes">

| | 空缺处 |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |

</div>
</div>

## 九、哨兵查找 <span class="pont">5 × 2 = 10 分</span>

带哨兵的链表由 <strong>Head</strong> 和 <strong>End</strong> 指针给出；End 指向链表末尾的哨兵结点。函数返回第一个包含 `x` 的结点的指针；如果 `x` 不在链表中，返回 Nil。

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

```text
Function SentinelSearch(Head, End, x)
  Elem[End].Value ← __(1)__
  P ← __(2)__
  While Elem[P].Value __(3)__ x
    P ← __(4)__
  End while
  If P __(5)__ End then
    Return Nil
  else
    Return P
  End if
End function
```

</div>
<div class="kitoltes">

| | 空缺处 |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |

</div>
</div>

---

## 十、在单链表的表尾插入 <span class="pont">6 × 2 = 12 分</span>

链表由 <strong>Head</strong> 指针给出。函数 `Reserve(P)` 分配一个新结点：成功时 P 指向分配的结点，函数返回 true。

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

```text
Function InsertLast(Head, Data)
  If not Reserve(P) then Return false
  Elem[P].Value ← Data
  Elem[P].Next ← __(1)__
  If Head __(2)__ Nil then
    Head ← __(3)__
  else
    Q ← Head
    While Elem[Q].Next __(4)__ Nil
      Q ← __(5)__
    End while
    __(6)__ ← P
  End if
  Return true
End function
```

</div>
<div class="kitoltes">

| | 空缺处 |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |
| (6) | |

</div>
</div>

## 评分

| 题号 | 一 | 二 | 三 | 四 | 五 | 六 | 七 | 八 | 九 | 十 | 总分 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 满分 | 14 | 10 | 10 | 7 | 7 | 8 | 12 | 10 | 10 | 12 | <strong>100</strong> |
| 得分 | | | | | | | | | | | |

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

<strong>阅卷人：</strong>................................................ &nbsp;&nbsp;&nbsp;&nbsp;<strong>成绩：</strong>................