Java 期末复习 — 增强版

UML — Queue<T>

Queue<T>

Fields（属性）

— head : Node<T>

— tail : Node<T>

— size : int

Methods（方法）

+ enqueue(data: T) : void

+ dequeue() : T

+ peek() : T

+ isEmpty() : boolean

+ size() : int

«inner class» Node<T>

— data : T

— next : Node<T>

+ Node(data: T)

QueueApp.java ← 考试给你

public class QueueApp {
  public static void main(String[] args) {
    Queue<Integer> q = new Queue<>();
    q.enqueue(10); q.enqueue(20); q.enqueue(30);
    System.out.println(q.peek());     // 10
    System.out.println(q.dequeue());   // 10
    System.out.println(q.size());      // 2
    System.out.println(q.isEmpty());   // false
  }
}

考试题型练习

Queue

实现 `enqueue(T data)` 方法简单

将新元素添加到队列尾部。空队列时 head 和 tail 都指向新节点。

public void enqueue(T data) {
    Node<T> newNode = new Node<>(data);
    if (isEmpty()) { head = newNode; tail = newNode; }
    else { tail.next = newNode; tail = newNode; }
    size++;
}

实现 `dequeue()` 方法简单

移除并返回头部元素。空队列抛出异常；移除后如队列变空，tail 置 null。

public T dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue is empty");
    T data = head.data;
    head = head.next;
    if (head == null) tail = null;
    size--;
    return data;
}

实现 `peek()`、`isEmpty()`、`size()` 简单

peek 查看不删头部；isEmpty 检查 size==0；size 返回当前元素数。

public T peek() { if (isEmpty()) throw new NoSuchElementException(); return head.data; }
public boolean isEmpty() { return size == 0; }
public int size() { return size; }

⭐综合题：完整 Queue 类骨架

给你上方 UML + QueueApp.java，写出完整 Queue.java（含内部 Node 类）。

import java.util.NoSuchElementException;
public class Queue<T> {
    private class Node<T> { T data; Node<T> next; Node(T d) { data = d; } }
    private Node<T> head, tail; private int size;
    public Queue() { head = tail = null; size = 0; }
    public void enqueue(T d) { Node<T> n = new Node<>(d); if (isEmpty()) head = tail = n; else { tail.next = n; tail = n; } size++; }
    public T dequeue() { if (isEmpty()) throw new NoSuchElementException(); T d = head.data; head = head.next; if (head == null) tail = null; size--; return d; }
    public T peek() { if (isEmpty()) throw new NoSuchElementException(); return head.data; }
    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

实现 `contains(T data)` 方法中等

遍历链表检查是否含指定元素。O(n)。

public boolean contains(T data) {
    Node<T> curr = head;
    while (curr != null) { if (curr.data.equals(data)) return true; curr = curr.next; }
    return false;
}

实现 `toArray()` 方法中等

将队列所有元素按 FIFO 顺序输出到数组。

public Object[] toArray() {
    Object[] arr = new Object[size];
    Node<T> curr = head;
    for (int i = 0; curr != null; i++, curr = curr.next) arr[i] = curr.data;
    return arr;
}

⭐难题：实现 reverse()

实现 `reverse()` 方法困难

原地反转队列（head↔tail 互换）。逐个反转 next 指针，最后 swap(head, tail)。

public void reverse() {
    Node<T> prev = null, curr = head;
    tail = head;  // old head → new tail
    while (curr != null) {
        Node<T> next = curr.next;
        curr.next = prev; prev = curr; curr = next;
    }
    head = prev;  // old tail → new head
}

UML — BST

BST

Fields

— root : Node

Methods

+ insert(data: int) : void

+ search(data: int) : boolean

+ delete(data: int) : void

+ inorder() : void

+ preorder() : void

+ height() : int

«inner class» Node

— data : int

— left : Node

— right : Node

+ Node(data: int)

BSTApp.java ← 考试给你

public class BSTApp {
  public static void main(String[] args) {
    BST tree = new BST();
    tree.insert(50); tree.insert(30); tree.insert(70);
    tree.insert(20); tree.insert(40);
    System.out.println(tree.search(30));   // true
    System.out.println(tree.search(100));  // false
    tree.inorder();   // 20 30 40 50 70
    System.out.println(tree.height());  // 3
  }
}

考试题型练习

BST

实现 `insert(int data)` 方法简单

递归插入：比根小走左，比根大走右，到 null 时建新节点。

public void insert(int data) { root = insertRec(root, data); }
private Node insertRec(Node node, int data) {
    if (node == null) return new Node(data);
    if (data < node.data) node.left = insertRec(node.left, data);
    else if (data > node.data) node.right = insertRec(node.right, data);
    return node;
}

实现 `search(int data)` 方法简单

递归搜索：找到返回 true，到 null 返回 false。

public boolean search(int data) { return searchRec(root, data); }
private boolean searchRec(Node node, int data) {
    if (node == null) return false;
    if (data == node.data) return true;
    if (data < node.data) return searchRec(node.left, data);
    else return searchRec(node.right, data);
}

实现 `inorder()` + `preorder()` 简单

中序=左→根→右（有序输出）；前序=根→左→右。

// Inorder: Left → Root → Right (ascending)
public void inorder() { inorderRec(root); }
private void inorderRec(Node node) { if (node != null) { inorderRec(node.left); System.out.print(node.data + " "); inorderRec(node.right); } }
// Preorder: Root → Left → Right
public void preorder() { preorderRec(root); }
private void preorderRec(Node node) { if (node != null) { System.out.print(node.data + " "); preorderRec(node.left); preorderRec(node.right); } }

实现 `height()` 方法简单

空树高度 0；否则 = 1 + max(左高, 右高)。

public int height() { return heightRec(root); }
private int heightRec(Node node) { if (node == null) return 0; return 1 + Math.max(heightRec(node.left), heightRec(node.right)); }

⭐进阶题：delete

实现 `delete(int data)` 方法困难

三种情况：①叶节点→直接删 ②单子→用子替换 ③双子→右子树最小值替换。

public void delete(int data) { root = deleteRec(root, data); }
private Node deleteRec(Node node, int data) {
    if (node == null) return null;
    if (data < node.data) node.left = deleteRec(node.left, data);
    else if (data > node.data) node.right = deleteRec(node.right, data);
    else {
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        Node succ = findMin(node.right); node.data = succ.data;
        node.right = deleteRec(node.right, succ.data);
    }
    return node;
}
private Node findMin(Node node) { while (node.left != null) node = node.left; return node; }

实现 `countNodes()` + `countLeaves()` 简单

递归计算总节点数 / 叶节点数。

public int countNodes() { return countNodesRec(root); }
private int countNodesRec(Node n) { if (n == null) return 0; return 1 + countNodesRec(n.left) + countNodesRec(n.right); }
public int countLeaves() { return countLeavesRec(root); }
private int countLeavesRec(Node n) { if (n == null) return 0; if (n.left == null && n.right == null) return 1; return countLeavesRec(n.left) + countLeavesRec(n.right); }

实现 `findMin()` + `findMax()` 中等

BST 最小值在最左，最大值在最右。空树抛异常。

public int findMin() { if (root == null) throw new NoSuchElementException(); Node c = root; while (c.left != null) c = c.left; return c.data; }
public int findMax() { if (root == null) throw new NoSuchElementException(); Node c = root; while (c.right != null) c = c.right; return c.data; }

⭐难题：检查平衡性

实现 `isBalanced()` 困难

对每个节点，左右子树高度差≤1。用 -1 标记不平衡。

public boolean isBalanced() { return checkBal(root) != -1; }
private int checkBal(Node n) {
    if (n == null) return 0;
    int l = checkBal(n.left); if (l == -1) return -1;
    int r = checkBal(n.right); if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

UML — Graph

Graph

Fields

— adjList : Map<String, List<String>>

Methods

+ addVertex(v: String) : void

+ addEdge(v1,v2: String) : void

+ BFS(start: String) : void

+ DFS(start: String) : void

+ printGraph() : void

GraphApp.java ← 考试给你

public class GraphApp {
  public static void main(String[] args) {
    Graph g = new Graph();
    g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D");
    g.addEdge("A", "B"); g.addEdge("A", "C"); g.addEdge("B", "D");
    g.BFS("A"); // A B C D
    g.DFS("A"); // A B D C
  }
}

考试题型练习

Graph

实现 `addVertex()` + `addEdge()` 简单

addVertex 加空列表；addEdge 无向图两边互加。

import java.util.*;
public class Graph { private Map<String,List<String>> adjList; public Graph() { adjList = new HashMap<>(); }
    public void addVertex(String v) { adjList.putIfAbsent(v, new ArrayList<>()); }
    public void addEdge(String v1,String v2) { adjList.get(v1).add(v2); adjList.get(v2).add(v1); } }

实现 `BFS(String start)` 中等

用 Queue + visited Set。BFS 保证无权图最短路径。

public void BFS(String start) {
    Set<String> vis = new HashSet<>(); Queue<String> q = new LinkedList<>();
    vis.add(start); q.add(start);
    while (!q.isEmpty()) {
        String v = q.poll(); System.out.print(v + " ");
        for (String n : adjList.get(v)) if (!vis.contains(n)) { vis.add(n); q.add(n); }
    }
}

实现 `DFS(String start)` 中等

递归 + visited Set。一路到底再回溯。

public void DFS(String start) { dfsRec(start, new HashSet<>()); }
private void dfsRec(String v, Set<String> vis) { vis.add(v); System.out.print(v+" "); for (String n:adjList.get(v)) if(!vis.contains(n)) dfsRec(n,vis); }

⭐综合题：完整 Graph 类

给你上方 UML + GraphApp.java，写出完整 Graph.java。

import java.util.*;
public class Graph {
    private Map<String,List<String>> adjList;
    public Graph() { adjList = new HashMap<>(); }
    public void addVertex(String v) { adjList.putIfAbsent(v, new ArrayList<>()); }
    public void addEdge(String v1,String v2) { adjList.get(v1).add(v2); adjList.get(v2).add(v1); }
    public void BFS(String s) { Set<String> v = new HashSet<>(); Queue<String> q = new LinkedList<>(); v.add(s); q.add(s); while(!q.isEmpty()) { String x=q.poll(); System.out.print(x+" "); for(String n:adjList.get(x)) if(!v.contains(n)){v.add(n);q.add(n);} } }
    public void DFS(String s) { dfsRec(s, new HashSet<>()); }
    private void dfsRec(String x,Set<String> v) { v.add(x); System.out.print(x+" "); for(String n:adjList.get(x)) if(!v.contains(n)) dfsRec(n,v); }
    public void printGraph() { for(String x:adjList.keySet()) System.out.println(x+" → "+adjList.get(x)); }
}

实现 `countVertices()` + `countEdges()` 简单

顶点数 = adjList.size()；边数 = 总邻接条目/2。

public int countVertices() { return adjList.size(); }
public int countEdges() { int t=0; for(List<String> nb:adjList.values()) t+=nb.size(); return t/2; }

实现 `hasEdge(v1,v2)` + `degree(v)` 中等

hasEdge 检查邻接表含 v2；degree 返回邻居数。

public boolean hasEdge(String v1,String v2) { return adjList.containsKey(v1) && adjList.get(v1).contains(v2); }
public int degree(String v) { return adjList.containsKey(v) ? adjList.get(v).size() : 0; }

⭐难题：检查连通性

实现 `isConnected()` 困难

从任意顶点 DFS/BFS，检查 visited 数是否等于总顶点数。

public boolean isConnected() {
    if(adjList.isEmpty()) return true;
    Set<String> vis = new HashSet<>();
    dfsRec(adjList.keySet().iterator().next(), vis);
    return vis.size() == adjList.size();
}

真题模拟练习

Lab Exercise

Queue（队列）— 3 题

Q-1: Bank Customer Service Counter（银行排队）

Queue · FIFO 命令处理 · 难度: ⭐⭐

描述：银行用取号系统管理客户。客户到达时分配票号加入队列(FIFO)。系统支持 4 个命令：

issueTicket <ticketNumber>   — 加入队尾
nextCust                    — 叫号（移除队首，空则提示）
view                        — 显示当前队列
finish                      — 结束并显示剩余队列

BankQueue
— waitingQueue: Queue	存储票号
+ BankQueue()	创建空队列
+ isEmpty(): boolean
+ issueTicket(String): void	加票号到队尾
+ nextCust(): void	叫号，空时显示"No customers…"
+ view(): void	显示 [front] T-101 -> T-102 [rear]

Sample Input

issueTicket T-101
issueTicket T-102
view
nextCust
finish

Sample Output

[front] T-101 -> T-102 [rear]
[front] T-102 [rear]

public class BankQueue {
    private Queue<String> waitingQueue;
    public BankQueue() { waitingQueue = new Queue<>(); }
    public boolean isEmpty() { return waitingQueue.isEmpty(); }
    public void issueTicket(String t) { waitingQueue.enqueue(t); }
    public void nextCust() {
        if (isEmpty()) System.out.println("No customers are waiting for service.");
        else waitingQueue.dequeue();
    }
    public void view() {
        if (isEmpty()) { System.out.println("No customers are waiting for service."); return; }
        System.out.print("[front] ");
        Queue<String>.Node c = waitingQueue.head;
        while (c != null) {
            System.out.print(c.data);
            if (c.next != null) System.out.print(" -> ");
            c = c.next;
        }
        System.out.println(" [rear]");
    }
}

Q-2: Print Spooler Simulator（打印排队）

Queue · 文档标题队列 · 难度: ⭐⭐

描述：办公室共享一台打印机，所有打印请求按 FIFO 排队。每个文档有标题。支持命令：

submit <documentTitle>   — 提交打印任务
print                     — 打印队首文档（移除并显示）
queue                     — 显示打印队列
finish                    — 结束

PrintSpooler
— jobQueue: Queue<String>	存储文档标题
+ PrintSpooler()
+ submit(String title): void	入队
+ print(): void	出队并显示 "Printing: <title>"，空则"There is no print job."
+ queue(): void	显示 [→ Report.pdf → Photo.jpg → Resume.docx]

Sample Input

submit Report.pdf
submit Photo.jpg
submit Resume.docx
queue
print
queue
print
print
print
finish

Sample Output

[→ Report.pdf → Photo.jpg → Resume.docx]
Printing: Report.pdf
[→ Photo.jpg → Resume.docx]
Printing: Photo.jpg
Printing: Resume.docx
There is no print job.

public class PrintSpooler {
    private Queue<String> jobQueue;
    public PrintSpooler() { jobQueue = new Queue<>(); }
    public void submit(String title) { jobQueue.enqueue(title); }
    public void print() {
        if (jobQueue.isEmpty()) { System.out.println("There is no print job."); return; }
        String doc = jobQueue.dequeue();
        System.out.println("Printing: " + doc);
    }
    public void queue() {
        if (jobQueue.isEmpty()) { System.out.println("[]"); return; }
        System.out.print("[→ ");
        Queue<String>.Node c = jobQueue.head;
        while (c != null) {
            System.out.print(c.data);
            if (c.next != null) System.out.print(" → ");
            c = c.next;
        }
        System.out.println("]");
    }
}

Q-3: Event Registration System（活动报名）

Queue · 容量限制 · 难度: ⭐⭐⭐

描述：活动容量为 C。报名者放入注册队列。队列满后后续报名者放入等待列表。有人取消后从等待列表补位。

register <name>  — 报名（队列未满则入队，满则入等待列表，显示 Registered/Waitlisted）
cancel <name>    — 取消（从注册队列移除，从等待列表补一人入队）
preview           — 显示当前注册队列
waitlist          — 显示等待列表
finish            — 结束

EventRegistration (capacity C=3)
— regQueue: Queue<String>	注册队列（容量 C）
— waitQueue: Queue<String>	等待列表
— capacity: int	容量
+ EventRegistration(int cap)
+ register(String name): void	入 regQueue 或 waitQueue
+ cancel(String name): void	从 regQueue 移除，从 waitQueue 补人
+ preview(): void	显示注册队列
+ waitlist(): void	显示等待列表

Sample Input

register Alice
register Bob
register Charlie
register David
register Eve
preview
waitlist
cancel Bob
preview
waitlist
finish

Sample Output

Registered: Alice
Registered: Bob
Registered: Charlie
Waitlisted: David
Waitlisted: Eve
[Registered] Alice -> Bob -> Charlie
[Waitlist] David -> Eve
[Registered] Alice -> Charlie -> David
[Waitlist] Eve

public class EventRegistration {
    private Queue<String> regQueue, waitQueue;
    private int capacity;
    public EventRegistration(int cap) { regQueue=new Queue<>(); waitQueue=new Queue<>(); capacity=cap; }
    public void register(String name) {
        if (regQueue.size() < capacity) { regQueue.enqueue(name); System.out.println("Registered: "+name); }
        else { waitQueue.enqueue(name); System.out.println("Waitlisted: "+name); }
    }
    public void cancel(String name) {
        Queue<String> tmp = new Queue<>();
        while (!regQueue.isEmpty()) { String n = regQueue.dequeue(); if (!n.equals(name)) tmp.enqueue(n); }
        while (!tmp.isEmpty()) regQueue.enqueue(tmp.dequeue());
        if (!waitQueue.isEmpty()) regQueue.enqueue(waitQueue.dequeue());
    }
    public void preview() { printQ("[Registered] ", regQueue); }
    public void waitlist() { printQ("[Waitlist] ", waitQueue); }
    private void printQ(String label, Queue<String> q) {
        System.out.print(label); Queue<String>.Node c = q.head;
        while (c != null) { System.out.print(c.data); if (c.next != null) System.out.print(" -> "); c = c.next; }
        System.out.println();
    }
}

BST（二叉搜索树）— 3 题

Q-4: Smart Warehouse Inventory（智能仓库）

BST · 重复合并 · Inorder 输出 · 难度: ⭐⭐⭐

描述：仓库收到产品记录(productCode, quantity)。同一产品码多次出现需合并数量。用 BST 存储（按 code 排序），最后按升序输出所有产品及总数量。

InventoryNode（已提供）
— productCode: String, quantity: int, left/right: InventoryNode
+ InventoryNode(code, qty)

InventoryBST（实现）
+ insert(code, qty): void	存在则累加数量
— insertRec(node,code,qty): InventoryNode
+ displayAscending(): void	Inorder 输出
— inorder(node): void

Sample Input

Sample Output

Warehouse Inventory:
P120 (25)
P200 (12)
P300 (25)
P450 (18)

public class InventoryBST {
    private InventoryNode root;
    public void insert(String code, int qty) { root = insertRec(root, code, qty); }
    private InventoryNode insertRec(InventoryNode n, String code, int qty) {
        if (n == null) return new InventoryNode(code, qty);
        int cmp = code.compareTo(n.productCode);
        if (cmp < 0) n.left = insertRec(n.left, code, qty);
        else if (cmp > 0) n.right = insertRec(n.right, code, qty);
        else n.quantity += qty;
        return n;
    }
    public void displayAscending() { System.out.println("Warehouse Inventory:"); inorder(root); }
    private void inorder(InventoryNode n) { if (n == null) return; inorder(n.left); System.out.println(n.productCode+" ("+n.quantity+")"); inorder(n.right); }
}

Q-5: Student Grade Records（学生成绩管理）

BST · 多字段节点 · 遍历计算 · 难度: ⭐⭐⭐

描述：用 BST 管理学生记录，以 studentId 为键。支持插入（含姓名+分数）、按 ID 搜索、计算平均分（遍历全部节点）。

StudentNode（已提供）
— studentId: String, name: String, grade: int, left/right: StudentNode
+ StudentNode(id, name, grade)

StudentBST（实现）
+ insert(id,name,grade): void	按 id 插入，重复时更新成绩
+ search(id): String	返回 "name (grade)" 或 "Not found"
+ averageGrade(): double	遍历计算平均分
+ displayAscending(): void	Inorder 输出所有学生

Sample Input

S003 Alice 85
S001 Bob   92
S002 Carol 78
S001 Bob   95
XXX

Sample Output

Student Records:
S001 Bob (95)
S002 Carol (78)
S003 Alice (85)
Average Grade: 86.0

public class StudentBST {
    private StudentNode root;
    public void insert(String id, String name, int grade) { root = insRec(root, id, name, grade); }
    private StudentNode insRec(StudentNode n, String id, String na, int g) {
        if (n == null) return new StudentNode(id, na, g);
        int c = id.compareTo(n.studentId);
        if (c < 0) n.left = insRec(n.left, id, na, g);
        else if (c > 0) n.right = insRec(n.right, id, na, g);
        else { n.name = na; n.grade = g; }
        return n;
    }
    public String search(String id) { StudentNode r = srchRec(root, id); return r == null ? "Not found" : r.name + " (" + r.grade + ")"; }
    private StudentNode srchRec(StudentNode n, String id) { if (n==null) return null; int c=id.compareTo(n.studentId); if(c==0) return n; return c<0 ? srchRec(n.left,id) : srchRec(n.right,id); }
    public double averageGrade() { int[] sum = {0,0}; avgRec(root, sum); return sum[1]==0 ? 0 : (double)sum[0]/sum[1]; }
    private void avgRec(StudentNode n, int[] s) { if(n==null) return; avgRec(n.left,s); s[0]+=n.grade; s[1]++; avgRec(n.right,s); }
    public void displayAscending() { inOrd(root); }
    private void inOrd(StudentNode n) { if(n==null) return; inOrd(n.left); System.out.println(n.studentId+" "+n.name+" ("+n.grade+")"); inOrd(n.right); }
}

Q-6: Library Book Catalog（图书馆目录）

BST · 字符串键 · 计数 · 难度: ⭐⭐⭐

描述：图书馆用 BST 管理书籍。以 ISBN 为键，存储书名和副本数量。同一 ISBN 多次录入时累加副本数。支持查询总藏书量、按 ISBN 范围计数。

BookNode（已提供）
— isbn: String, title: String, copies: int, left/right: BookNode
+ BookNode(isbn, title, copies)

LibraryBST（实现）
+ addBook(isbn,title,copies): void	插入/更新
+ search(isbn): String	返回"title (copies)"或"Not found"
+ totalCopies(): int	遍历统计总副本数
+ displayCatalog(): void	Inorder 输出目录

Sample Input

978-001 Java Basics 3
978-002 Data Struct 5
978-001 Java Basics 2
978-003 Algorithms 4
XXX

Sample Output

Library Catalog:
978-001 Java Basics (5)
978-002 Data Struct (5)
978-003 Algorithms (4)
Total Copies: 14

public class LibraryBST {
    private BookNode root;
    public void addBook(String isbn, String title, int copies) { root = addRec(root, isbn, title, copies); }
    private BookNode addRec(BookNode n, String isbn, String t, int c) {
        if (n == null) return new BookNode(isbn, t, c);
        int cmp = isbn.compareTo(n.isbn);
        if (cmp < 0) n.left = addRec(n.left, isbn, t, c);
        else if (cmp > 0) n.right = addRec(n.right, isbn, t, c);
        else n.copies += c;
        return n;
    }
    public String search(String isbn) { BookNode r = srchRec(root, isbn); return r==null ? "Not found" : r.title+" ("+r.copies+")"; }
    private BookNode srchRec(BookNode n, String isbn) { if(n==null) return null; int c=isbn.compareTo(n.isbn); if(c==0) return n; return c<0 ? srchRec(n.left,isbn) : srchRec(n.right,isbn); }
    public int totalCopies() { return totalRec(root); }
    private int totalRec(BookNode n) { if(n==null) return 0; return n.copies + totalRec(n.left) + totalRec(n.right); }
    public void displayCatalog() { System.out.println("Library Catalog:"); inOrd(root); }
    private void inOrd(BookNode n) { if(n==null) return; inOrd(n.left); System.out.println(n.isbn+" "+n.title+" ("+n.copies+")"); inOrd(n.right); }
}

Graph（图）— 3 题

Q-7: Smart City Bicycle Lane Network（自行车道·邻接矩阵）

Graph · 邻接矩阵 · 无向图 · 难度: ⭐⭐⭐

描述：城市有 8 个公园（park1~park8），用无向图+邻接矩阵表示自行车道。读入 M 条边，输出公园索引列表 + 邻接矩阵。park 标签→索引：park1→0, park2→1…对称矩阵。

ParkMap
— adjMatrix: int[][]	8×8
+ ParkMap()	初始化
+ addLane(park1, park2): void	对称设置 1
+ displayParks(): void	索引: parkN
+ displayMatrix(): void	矩阵输出

Sample Input

3
park1 park2
park3 park4
park5 park6

Sample Output

Park List
0: park1  1: park2  2: park3  3: park4
4: park5  5: park6  6: park7  7: park8
Adjacency Matrix
    0 1 2 3 4 5 6 7
0   0 1 0 0 0 0 0 0
1   1 0 0 0 0 0 0 0
2   0 0 0 1 0 0 0 0
3   0 0 1 0 0 0 0 0
4   0 0 0 0 0 1 0 0
5   0 0 0 0 1 0 0 0
6   0 0 0 0 0 0 0 0
7   0 0 0 0 0 0 0 0

public class ParkMap {
    private int[][] adjMatrix;
    public ParkMap() { adjMatrix = new int[8][8]; }
    public void addLane(String park1, String park2) {
        int i = Integer.parseInt(park1.substring(4)) - 1;
        int j = Integer.parseInt(park2.substring(4)) - 1;
        adjMatrix[i][j] = 1; adjMatrix[j][i] = 1;
    }
    public void displayParks() { System.out.println("Park List"); for(int i=0;i<8;i++) System.out.println(i+": park"+(i+1)); }
    public void displayMatrix() {
        System.out.println("Adjacency Matrix");
        System.out.print("    "); for(int i=0;i<8;i++) System.out.print(i+" "); System.out.println();
        for(int i=0;i<8;i++) { System.out.print(i+"   "); for(int j=0;j<8;j++) System.out.print(adjMatrix[i][j]+" "); System.out.println(); }
    }
}

Q-8: Social Media Friend Network（社交好友·邻接表）

Graph · AdjList · 共同好友 · 难度: ⭐⭐⭐

描述：用无向图邻接表表示社交网络。顶点为人名，边为好友关系。支持添加好友、查询好友列表、找共同好友。

SocialNet
— adjList: Map<String,Set<String>> (Set 避免重复)
+ addPerson(name): void
+ addFriend(name1,name2): void	无向添加
+ getFriends(name): Set<String>	返回好友集合
+ getMutualFriends(n1,n2): Set<String>	交集
+ recommendFriends(name): Set<String>	好友的好友（排除自己+已有好友）

Sample Input (App)

add Alice
add Bob
add Charlie
add Diana
addFriend Alice Bob
addFriend Alice Charlie
addFriend Bob Diana
addFriend Charlie Diana
getFriends Alice
getMutual Alice Diana
recommend Alice

Sample Output

Friends of Alice: {Bob, Charlie}
Mutual friends of Alice & Diana: {Bob, Charlie}
Recommended for Alice: {Diana}

import java.util.*;
public class SocialNet {
    private Map<String,Set<String>> adjList;
    public SocialNet() { adjList = new HashMap<>(); }
    public void addPerson(String n) { adjList.putIfAbsent(n, new HashSet<>()); }
    public void addFriend(String n1,String n2) { addPerson(n1); addPerson(n2); adjList.get(n1).add(n2); adjList.get(n2).add(n1); }
    public Set<String> getFriends(String n) { return adjList.getOrDefault(n, new HashSet<>()); }
    public Set<String> getMutualFriends(String n1,String n2) {
        Set<String> f1 = new HashSet<>(getFriends(n1));
        f1.retainAll(getFriends(n2)); return f1;
    }
    public Set<String> recommendFriends(String n) {
        Set<String> recommended = new HashSet<>();
        for(String friend : getFriends(n))
            for(String fof : getFriends(friend))
                if (!fof.equals(n) && !getFriends(n).contains(fof))
                    recommended.add(fof);
        return recommended;
    }
}

Q-9: Course Prerequisite Checker（课程先修检查·有向图）

Graph · 有向图 · DFS 可达性 · 难度: ⭐⭐⭐⭐

描述：大学课程有先修关系（有向边）。如 CS102 先修 CS101，则边 CS101→CS102。检查某课程是否为另一课程的直接或间接先修（DFS 从 from 出发能否到达 to）。

CourseGraph
— adjList: Map<String,List<String>>	有向邻接表
+ addCourse(course): void
+ addPrerequisite(from,to): void	有向边 from→to
+ isPrerequisite(from,to): boolean	DFS 检查 from 能否到达 to
+ getDirectPrerequisites(course): List<String>	直接先修

Sample Input (App)

addCourse CS101
addCourse CS102
addCourse CS201
addCourse CS202
addPrerequisite CS101 CS102
addPrerequisite CS102 CS201
addPrerequisite CS101 CS202
isPrerequisite CS101 CS201  // true (indirect)
isPrerequisite CS102 CS101  // false
getDirectPrerequisites CS201  // [CS102]

Sample Output

Is CS101 prerequisite of CS201? true
Is CS102 prerequisite of CS101? false
Direct prerequisites of CS201: [CS102]

import java.util.*;
public class CourseGraph {
    private Map<String,List<String>> adjList;
    public CourseGraph() { adjList = new HashMap<>(); }
    public void addCourse(String c) { adjList.putIfAbsent(c, new ArrayList<>()); }
    public void addPrerequisite(String from, String to) { addCourse(from); addCourse(to); adjList.get(from).add(to); }
    public boolean isPrerequisite(String from, String to) { return dfs(from, to, new HashSet<>()); }
    private boolean dfs(String cur, String target, Set<String> visited) {
        if (cur.equals(target)) return true;
        visited.add(cur);
        for (String n : adjList.getOrDefault(cur, new ArrayList<>()))
            if (!visited.contains(n) && dfs(n, target, visited)) return true;
        return false;
    }
    public List<String> getDirectPrerequisites(String c) { return adjList.getOrDefault(c, new ArrayList<>()); }
}

考试题型练习

实现 enqueue(T data) 方法 简单

实现 dequeue() 方法 简单

实现 peek()、isEmpty()、size() 简单

实现 contains(T data) 方法 中等

实现 toArray() 方法 中等

实现 reverse() 方法 困难

考试题型练习

实现 insert(int data) 方法 简单

实现 search(int data) 方法 简单

实现 inorder() + preorder() 简单

实现 height() 方法 简单

实现 delete(int data) 方法 困难

实现 countNodes() + countLeaves() 简单

实现 findMin() + findMax() 中等

实现 isBalanced() 困难

考试题型练习

实现 addVertex() + addEdge() 简单

实现 BFS(String start) 中等

实现 DFS(String start) 中等

实现 countVertices() + countEdges() 简单

实现 hasEdge(v1,v2) + degree(v) 中等

实现 isConnected() 困难

真题模拟练习

Queue（队列）— 3 题

Q-1: Bank Customer Service Counter（银行排队）

Sample Input

Sample Output

Q-2: Print Spooler Simulator（打印排队）

Sample Input

Sample Output

Q-3: Event Registration System（活动报名）

Sample Input

Sample Output

BST（二叉搜索树）— 3 题

Q-4: Smart Warehouse Inventory（智能仓库）

Sample Input

Sample Output

Q-5: Student Grade Records（学生成绩管理）

Sample Input

Sample Output

Q-6: Library Book Catalog（图书馆目录）

Sample Input

Sample Output

Graph（图）— 3 题

Q-7: Smart City Bicycle Lane Network（自行车道·邻接矩阵）

Sample Input

Sample Output

Q-8: Social Media Friend Network（社交好友·邻接表）

Sample Input (App)

Sample Output

Q-9: Course Prerequisite Checker（课程先修检查·有向图）

Sample Input (App)

Sample Output

实现 `enqueue(T data)` 方法简单

实现 `dequeue()` 方法简单

实现 `peek()`、`isEmpty()`、`size()` 简单

实现 `contains(T data)` 方法中等

实现 `toArray()` 方法中等

实现 `reverse()` 方法困难

实现 `insert(int data)` 方法简单

实现 `search(int data)` 方法简单

实现 `inorder()` + `preorder()` 简单

实现 `height()` 方法简单

实现 `delete(int data)` 方法困难

实现 `countNodes()` + `countLeaves()` 简单

实现 `findMin()` + `findMax()` 中等

实现 `isBalanced()` 困难

实现 `addVertex()` + `addEdge()` 简单

实现 `BFS(String start)` 中等

实现 `DFS(String start)` 中等

实现 `countVertices()` + `countEdges()` 简单

实现 `hasEdge(v1,v2)` + `degree(v)` 中等

实现 `isConnected()` 困难