数据结构: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);