---
marp: true
theme: a4
paginate: true
footer: 数据结构 · 上机考试 · 学生信息管理
---

# 数据结构 – 上机考试

## 学生信息管理

<strong>考试时间：</strong>90 分钟 · <strong>语言：</strong>Java 或 Go（任选） · <strong>计算机：</strong>机房的计算机
<strong>允许使用：</strong>本课程的示例程序和幻灯片、自己的笔记 · <strong>不允许使用：</strong>互联网、人工智能（AI）工具、其他同学的帮助

### 任务

我们要管理一所大学的学生信息。每个学生有一个<strong>学号</strong>（`id`，整数）、<strong>姓名</strong>和<strong>分数</strong>（0–100）。请用<strong>你自己实现的数据结构</strong>完成初始代码中标有 <strong>TODO</strong> 的操作！

| | Java | Go |
|---|---|---|
| 初始代码 | `practical/java/StudentRegistry.java` | `practical/go/main.go` |
| 运行 | `java StudentRegistry.java` | `go run .`（在 `go` 文件夹中） |
| 解答中禁止使用 | `java.util` 中的集合类（`ArrayList`、`LinkedList`、`HashMap`、`TreeMap` …） | `container/list`、`map`、内置排序 |

程序最后会<strong>按级别</strong>输出哪些检查通过（<strong>OK</strong>），哪些失败（<strong>FAIL</strong>）。<strong>不要修改</strong>检查部分！程序的输出是英文的。

### 各个级别

必须<strong>按顺序</strong>完成各个级别：只有前面所有级别都完全正确时，一个级别才算数。

<strong>第 1 级 – 及格（2）：单链表</strong>

- `add(s)` – 新学生加到链表的<strong>末尾</strong>
- `size()` – 学生人数
- `find(id)` – 按学号查找（找不到：`null` / `nil`）
- `toString()` / `String()` – 例如 `[1003 Li Wei 87, 1001 Wang Fang 92]`，空链表：`[]`

<strong>第 2 级 – 中等（3）</strong>

- `remove(id)` – 删除学生；如果有这个学生则返回 true（注意删除<strong>第一个</strong>结点的情况！）
- `averageScore()` – 分数的平均值（空链表为 0）
- `best()` – 分数最高的学生；并列时取链表中靠前的

---

<strong>第 3 级 – 良好（4）</strong>

- `addSortedByScore(s)` – 插入后链表仍按分数<strong>降序</strong>排列；分数相同时，新学生排在已有学生的<strong>后面</strong>（稳定插入）
- `reverse()` – <strong>原地</strong>逆置链表，不创建新结点

<strong>第 4 级 – 优秀（5）：二叉搜索树</strong>（键：学号）

- `insert(s)` – 插入；重复的学号<strong>不</strong>再插入
- `find(id)` – 按学号查找
- `height()` – 树的高度（空树：−1，只有一个结点：0）
- `inorderIds()` – 按中序排列的学号，例如 `[1001, 1002, 1003]`

第 4 级的检查还会进行一次<strong>测量</strong>（在链表和二叉搜索树中各查找 20 000 次）。请观察结果 – 口试时会问到！

### 评分

1. <strong>自动检查：</strong>程序输出的级别是<strong>最高可能</strong>的成绩。
2. <strong>口试</strong>（约 5 分钟）：你必须能够讲解自己的代码，并回答 2–3 个问题（例如 <em>`find` 操作需要多少步？删除第一个结点时会发生什么？</em>）。
   如果讲解不能令人信服，成绩<strong>可能会降低</strong>。
3. 如果程序不能编译、使用了禁止的集合类，或者修改了检查部分，解答<strong>不予接受</strong>。

### 提示

- <strong>逐级</strong>进行，每写完一个方法就运行一次程序！
- 考虑<strong>特殊情况</strong>：空链表、只有一个结点的链表、第一个和最后一个结点。
- 第 9、10、14、15 周的示例程序很有帮助。
- 经常保存你的工作！

<br>

<strong>姓名：</strong>........................................................ &nbsp;&nbsp;<strong>学号：</strong>.............................. &nbsp;&nbsp;<strong>所选语言：</strong>Java / Go