当然可以！以下是 **COMP9123 数据结构与算法 – 作业 3** 的题目翻译：

------

# 📘 COMP9123 数据结构与算法 – 作业 3（翻译版）

**截止时间：2025年6月1日 晚上11:59**

- 请通过 Canvas 提交第 Q1、Q2 和 Q3 题，通过 Ed 提交第 Q4 题。
- Q1、Q2 和 Q3 的提交必须为 PDF 格式，且**不能为手写**。
- 本次作业占期末总成绩的 **15%**。
- 请先翻到最后一页阅读 “关于如何完成作业的建议” 部分。

------

## ❓问题1：最小生成树

设图 G = (V, E) 是一个任意的**连通加权图**。

记 m = |E| 为图的边数，n = |V| 为图的顶点数。

**a)** 证明或反驳：图 G 的最小生成树一定包含每一个环中**权重最小的边**（如果存在多个权重最小的边，则包含其中至少一条）。

（2 分）

**b)** 如果图中所有边的权值都不相同，则最小生成树是唯一的。那反过来是否成立？证明或反驳：如果图中存在两条具有相同权重的边，则一定存在**多个**最小生成树。

（2 分）

**c)** 描述一个 **O(m log n)** 时间复杂度的算法，用于判断图是否具有**唯一的最小生成树**，或者是否存在多个最小生成树。

（6 分）

**d)** 证明你的算法是正确的。

（2 分）

**e)** 分析你算法的时间复杂度。

（2 分）

------

## 🎮问题2：赛车游戏（Vector Racer）

Vector Racer 是一个游戏，玩家轮流操作赛车在赛道上移动。每辆赛车初始速度为 (0, 0)，表示 x 和 y 方向的速度。

每回合，玩家可以对速度向量的任一分量加或减1，或同时改变两个方向，然后赛车根据当前速度向量移动到新的位置。

你会得到一个 n × n 的布尔矩阵，表示赛道布局，其中 `track[i][j] = True` 表示该格子是赛道的一部分，`False` 表示出界。

- 如果赛车出了赛道（落在 False 上），则会撞车。
- 起点是矩阵的第一列，终点是最后一列。
- 目标是**以最少回合数**到达终点线，且始终保持在赛道上。

**注意：**

- 多辆赛车可以在同一位置，不必考虑其他赛车。
- 赛车可以跳过出界区域，只要最终落点落在赛道上。
- 必须**落在终点线**上，不能越过，否则算作撞车。

你的任务是：

**a)** 设计一个高效算法，计算从起点到终点所需的最小回合数（不撞车）。

（7 分）

**b)** 说明你的算法正确性。

（2 分）

**c)** 分析你的算法时间复杂度。

（2 分）

------

## 🚗问题3：Helen 的公路旅行

Helen 从悉尼出发计划自驾到 Tamworth，她使用一个由城市和道路构成的图 G = (V, E) 作为地图。

图中每条边表示一条道路，边的长度表示道路距离。她将原始路径 P 设定为从悉尼到 Tamworth 的最短路径，|P| 为路径中的边数。

但她知道某一条道路可能会因为施工封闭，虽然她出发前会检查，但现在她想提前知道：如果路径 P 中的每一条边 e 被移除后的最短路径距离是多少（仅限原路径中的城市）。

换句话说，她不想绕路去访问那些原本不在路径中的城市。

**a)** 设计一个运行时间为 **O(|E|² log |V|)** 的算法，输出一个列表，包含当 P 中每一条边 e 被删除时，从悉尼到 Tamworth 的最短路径长度（若无路径，则为 ∞）。

（7 分）

**b)** 证明你的算法是正确的。

（2 分）

**c)** 分析你的算法时间复杂度。

（2 分）

------

## 💻问题4：编程实现（在 Ed 上完成）

### **a)** Greedy Job Scheduling（贪心作业调度）

实现一个贪心算法来选择兼容的作业。每个 `Job` 对象包含：

- `id`（整数）
- `startTime`（开始时间，浮点数）
- `finishTime`（结束时间，浮点数）

策略：按区间长度从短到长排序，选择不冲突的作业。

输入格式（如使用 `loadJobs`）：

```
1 3 6
2 6 10
3 1 4
4 5 7
5 0 3
```

请在 Edstem 上实现算法：

[Ed 链接](https://edstem.org/au/courses/20134/lessons/81247/slides/552253)

（8 分）

------

### **b)** 基因测试与治疗（genetics.py）

你需要帮助药企实现基因相关的三个函数：

#### `is_sorted(A: list) -> bool`

- 输入：整数列表 A
- 输出：布尔值，判断 A 是否升序排列
- 若 A 为 None，返回 None

#### `count_markers(A: list, c: int) -> int`

- 输入：A 为**已排序的整数列表**（基因标记），c 为阈值
- 输出：满足 `|A[i] − i| ≤ c` 的索引 i 的数量
- 要求用 **分治算法**，运行时间为 **O(log n)**

#### `treat_patient(A: list, c: int) -> int`

- 输入：同上
- 输出：随机返回一个满足 `|A[i] − i| ≤ c` 的索引 i
- 若无符合条件的索引，返回 None
- 要求用 **分治算法**，运行时间为 **O(log n)**

请在 Edstem 上实现算法：

[Ed 链接](https://edstem.org/au/courses/20134/lessons/81247/slides/552254)

（16 分）

------

## ✅作业建议

- 所有作业必须**独立完成**，严禁抄袭。
- 提交格式必须为 PDF，不能为手写。
- 切勿给出多个答案，否则按最差答案评分。
- 简洁明了，重点在思路和正确性。
- 算法题可写伪代码，**但必须解释思路和正确性**。
- 默认要求最坏情况分析。
- 参考资料需注明来源并解释内容。

------

是否需要我帮助你撰写某一题的解答或算法设计？