USYD COMP2123 Algorithms and Data Structures 是 USYD 计算机科学专业大二核心课程，与 UNSW 的 COMP2521 类似，但使用 Java 而非 C，部分概念和实现方式有所不同。
本文从 USYD 课程结构出发，系统整理 COMP2123 的核心考点和常见失分原因。
COMP2123 课程结构
| 组成部分 | 权重 | 说明 |
|---|---|---|
| Assignment 1（基础 ADT 实现） | 15% | Java 实现 Stack/Queue/LinkedList |
| Assignment 2（树 + 图算法） | 20% | Java BST + 图搜索 |
| Weekly Quizzes | 10% | 每周在线测验 |
| Mid-Semester Exam | 20% | 笔试 |
| Final Exam | 35% | 笔试，代码+分析 |
第一部分：基础数据结构（Java 实现）
1.1 链表（Linked List）
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
// 在头部插入 - O(1)
public void insertFront(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// 在尾部插入 - O(n)
public void insertBack(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node curr = head;
while (curr.next != null) curr = curr.next;
curr.next = newNode;
}
// 删除值为 key 的第一个节点 - O(n)
public void delete(int key) {
if (head == null) return;
if (head.data == key) { head = head.next; return; }
Node curr = head;
while (curr.next != null && curr.next.data != key)
curr = curr.next;
if (curr.next != null)
curr.next = curr.next.next;
}
// 反转链表 - O(n)
public Node reverse() {
Node prev = null, curr = head, next;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
1.2 栈与队列（Stack & Queue）
// 栈（LIFO）- 用 Deque 实现
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 压栈
stack.pop(); // 弹栈
stack.peek(); // 查看栈顶
// 队列（FIFO）- 用 LinkedList 实现
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
queue.poll(); // 出队
queue.peek(); // 查看队头
// 优先队列（最小堆）
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll(); // 返回 1（最小值）
// 最大堆
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
第二部分：树
2.1 二叉搜索树（BST）
public class BST {
int val;
BST left, right;
public BST(int val) { this.val = val; }
// 插入
public BST insert(int data) {
if (data < val) {
if (left == null) left = new BST(data);
else left.insert(data);
} else if (data > val) {
if (right == null) right = new BST(data);
else right.insert(data);
}
return this;
}
// 中序遍历（得到排序结果）
public void inorder() {
if (left != null) left.inorder();
System.out.print(val + " ");
if (right != null) right.inorder();
}
// 查找最小值（一直向左）
public int findMin() {
return (left == null) ? val : left.findMin();
}
}
2.2 堆（Heap）
最大堆的性质：父节点 ≥ 子节点
// 手写最大堆（数组实现）
class MaxHeap {
int[] heap;
int size;
// 父节点索引 = (i-1)/2
// 左子节点 = 2*i + 1
// 右子节点 = 2*i + 2
void insert(int val) {
heap[size] = val;
siftUp(size);
size++;
}
void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[parent] < heap[i]) {
swap(parent, i);
i = parent;
} else break;
}
}
int extractMax() {
int max = heap[0];
heap[0] = heap[--size];
siftDown(0);
return max;
}
void siftDown(int i) {
while (2 * i + 1 < size) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left] > heap[largest]) largest = left;
if (right < size && heap[right] > heap[largest]) largest = right;
if (largest == i) break;
swap(i, largest);
i = largest;
}
}
}
堆排序（Heap Sort）：O(n log n)
- 建堆（heapify）：O(n)
- 反复 extractMax：O(n log n)
第三部分：图算法（Java 实现）
3.1 图的表示
// 邻接链表（推荐，适合稀疏图）
Map<Integer, List<Integer>> graph = new HashMap<>();
// 添加边（无向图）
void addEdge(int u, int v) {
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
3.2 BFS（宽度优先搜索）
void bfs(int start, int n) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
BFS 应用：
- 无权图最短路径：从 start 到 end 的最少边数
- 二分图检测（层级染色）
- 连通分量
3.3 Dijkstra（加权有向图最短路径）
int[] dijkstra(int[][] graph, int src, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// (distance, node)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // 过期的条目，跳过
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
时间复杂度：O((V + E) log V)，使用优先队列
第四部分：排序算法对比
| 算法 | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ |
快速排序最差情况（O(n²)）的触发条件：每次 pivot 都选到最大/最小值（如已排序数组 + 选第一个元素为 pivot）。
归并排序 Java 实现（稳定排序，COMP2123 常考）：
void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void merge(int[] arr, int left, int mid, int right) {
int[] temp = Arrays.copyOfRange(arr, left, right + 1);
int i = 0, j = mid - left + 1, k = left;
while (i <= mid - left && j <= right - left) {
if (temp[i] <= temp[j]) arr[k++] = temp[i++];
else arr[k++] = temp[j++];
}
while (i <= mid - left) arr[k++] = temp[i++];
while (j <= right - left) arr[k++] = temp[j++];
}
COMP2123 期末考备考建议
笔试题型分布：
- 代码追踪（给出代码和输入，手动追踪输出）—— 30%
- 写代码/伪代码 —— 30%
- 复杂度分析 + 证明 —— 20%
- 概念问答（什么情况下用什么算法） —— 20%
备考策略：
- 优先练习"手工追踪"：拿一个链表/树/图，用手工步骤一步步走 BFS/Dijkstra 过程
- 记住 Java 标准库：
PriorityQueue、ArrayDeque、HashMap在考试里是可以用的 - 复杂度分析要写出"推导"，不只是写结论
需要辅导？
COMP2123 的 Assignment 里最常见的问题是：树和图的 Java 实现逻辑错误，以及期末考的算法追踪题型不熟悉。我们的 USYD CS 导师可以帮你针对性练习。
相关资源：
