数据结构：UNSW新南学COMP9024真题讲解
作者：Ethan（连接教育高级讲师）
首发于：UNSW学习知识库（UNSW Study Wiki）
创作时间：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：其邻居为 0 和 2，优先选编号小的 0。此时路径为
1-0。 -
处理顶点 0：其邻居中未访问的最小编号是 3。路径更新为
1-0-3。 -
处理顶点 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);