数据结构：UNSW新南学COMP9024真题讲解

作者：Ethan（连接教育高级讲师）

首发于：

创作时间：2025年3月14日

COMP9024虽存在较大争议，但完成后可显著提升专业能力。课程评估包含周测（C 语言语法选择题）、编程作业（高难度代码项目）、线上开卷期中考试及线下闭卷期末考试（需自备电脑）。

BFS 的题目

If we used a standard breadth-first search, starting from vertex 1, and giving priorityto lower-numbered neighbours, which path would be discovered to reach vertex 4?

题目要求使用标准广度优先搜索（BFS），从顶点 1 出发，优先选择编号更小的邻居，寻找到达顶点 4 的路径。需根据 BFS 的队列操作逻辑和邻居优先级规则分析。

解析

1. 初始化：从顶点 1 开始，将 1 加入队列。
2. 处理顶点 1：其邻居为 0 和 2，优先选编号小的 0。此时路径为 1-0 。
3. 处理顶点 0：其邻居中未访问的最小编号是 3。路径更新为 1-0-3 。
4. 处理顶点 3：其邻居中未访问的是 4。最终路径为 1-0-3-4 。

其他选项分析：

• 1-2-3-4 ：BFS 优先处理 0（比 2 编号小），不会先经过 2。
• 1-2-6-7-8-5-4 ：路径过长，不符合 BFS 短路径优先特性。
• 1-0-3-5-4 ：顶点 3 的邻居中 4 比 5 编号小，应先访问 4。

答案

选择 1-0-3-4 ，对应第一个选项

哈密顿路径

Consider the following graph. Give a Hamiltonian path starting from 1 if one exists. Hint: there may be more than one correct solution. (Enter your solution path in this format: 1-2-3 dash separated no spaces, from starting node to finishing node. If no Hamiltonian path exists, enter: none).

如果存在从顶点 1 开始的哈密顿路径，请给出一个。提示：可能有多个正确解。（按照此格式输入路径：1-2-3，用短横线分隔，无空格，从起始节点到结束节点。如果不存在哈密顿路径，输入：none）。

答案

none

MCQ Memory Allocation

Consider the structured data type typedef struct { NodeT *head, *tail; int size; } ListRep; Tick all correct ways to allocate dynamic memory for 1,000 elements of type ListRep on a CSE lab computer.

• ListRep *L = malloc(1000 * sizeof(ListRep));
• ListRep *L = calloc(1000, sizeof(ListRep));
• ListRep *L = malloc(1000 * sizeof(ListRep *));
• ListRep L = calloc(20000);
• ListRep L = malloc(1000 * sizeof(ListRep *));

解析

• 选项 1： ListRep *L = malloc(1000 * sizeof(ListRep)); malloc 需传入总字节数， 1000 * sizeof(ListRep) 正确计算了 1000 个 ListRep 的内存大小，用法正确。
• 选项 2： ListRep *L = calloc(1000, sizeof(ListRep)); calloc 第一个参数是元素个数，第二个是单个元素大小， 1000 和 sizeof(ListRep) 匹配需求，用法正确。
• 选项 3： malloc 中使用 sizeof(ListRep *) 错误，因为目标是分配 ListRep 类型元素，而非 ListRep * 指针数组。
• 选项 4、5： L 未定义为指针，直接用 malloc/calloc 分配内存且参数逻辑错误，语法和语义均不成立。

答案

• ListRep *L = malloc(1000 * sizeof(ListRep));
• ListRep *L = calloc(1000, sizeof(ListRep);

UNSW学习资料：