Bộ 5 đề ôn tập giữa kỳ Cấu trúc dữ liệu và Giải thuật (DSA)

PHẦN I. TRẮC NGHIỆM (3,0 điểm)

Thí sinh chọn một phương án đúng duy nhất cho mỗi câu hỏi sau:

Câu 1. Trong thuật toán Quick-Find, độ phức tạp thời gian trong trường hợp tồi nhất của thao tác `union(p, q)` trên tập $N$ phần tử là:

Câu 2. Cho một Stack rỗng. Thực hiện chuỗi thao tác: `push(3)`, `push(5)`, `pop()`, `push(7)`, `push(9)`, `pop()`. Giá trị còn lại ở đỉnh Stack là:

Câu 3. Thuật toán Sắp xếp Chèn (Insertion Sort) thực hiện số phép so sánh ít nhất $\sim N$ khi dãy đầu vào có đặc điểm gì?

Câu 4. Đâu là phát biểu ĐÚNG về thuật toán Mergesort?

Câu 5. Cho Max Heap nhị phân biểu diễn dưới dạng mảng (chỉ số bắt đầu từ $1$). Nút ở chỉ số $k$ ($k > 1$) có nút cha nằm ở chỉ số nào?

Câu 6. Để thu được danh sách các khóa theo thứ tự tăng dần từ một Cây tìm kiếm nhị phân (BST), ta thực hiện duyệt cây theo thứ tự nào?

Câu 7. Cấu trúc dữ liệu Weighted Quick-Union đảm bảo chiều cao tối đa của bất kỳ cây nào chứa $N$ phần tử không vượt quá:

Câu 8. Thuật toán Quickselect dùng để tìm phần tử nhỏ thứ $k$ trong mảng $N$ phần tử có độ phức tạp thời gian trung bình (khi đã shuffle) là:

Câu 9. Thuật toán sắp xếp nào dưới đây KHÔNG phải là thuật toán sắp xếp tại chỗ (In-place)?

Câu 10. Khi thêm một phần tử mới vào Max Heap nhị phân chứa $N$ phần tử, số phép so sánh nhiều nhất cần thực hiện (thao tác `swim`) là:

Câu 11. Biểu thức Tilde ($\sim$) xấp xỉ cho hàm $f(N) = 2N^3 - 15N^2 + 100N$ khi $N$ rất lớn là:

Câu 12. Cho Danh sách liên kết đơn có hai con trỏ `head` và `tail`. Thao tác nào sau đây có độ phức tạp thời gian tồi nhất là $O(N)$?

Câu 13. Thuật toán Sắp xếp Chọn (Selection Sort) có đặc điểm nào sau đây?

Câu 14. Trong thuật toán Dijkstra 2-stack để tính giá trị biểu thức số học, khi gặp toán tử (ví dụ `+`, `*`), ta xử lý như thế nào?

Câu 15. Chiều cao tồi nhất (worst-case height) của một cây BST chứa $N$ phần tử là:

PHẦN II. TỰ LUẬN (7,0 điểm)

Câu 1 (1,5 điểm - Phân tích độ phức tạp).
Cho đoạn mã nguồn C++ / Java sau:

int countPairs(int a[], int N) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (a[i] == a[j]) {
count++;
}
}
}
return count;
}

a) Hãy tính chính xác số lần thực hiện phép so sánh `a[i] == a[j]` theo $N$.
b) Cho biết độ phức tạp tính toán theo ký hiệu $O$ và ký hiệu Tilde ($\sim$) của thuật toán trên.

Câu 2 (1,5 điểm - Stack & Queue).
a) Cho một Queue $Q$ rỗng. Cho chuỗi thao tác:

$$\text{enqueue}(10) \to \text{enqueue}(20) \to \text{dequeue}() \to \text{enqueue}(30) \to \text{enqueue}(40) \to \text{dequeue}() \to \text{isEmpty}()$$

Hãy cho biết trạng thái của Queue $Q$ sau mỗi thao tác và giá trị trả về của các thao tác `dequeue()`, `isEmpty()` (Quy ước bên phải là đầu ra / đầu lấy phần tử của Queue).
b) Viết hàm bằng mã giả hoặc Java `void reverseK(Queue<Integer> q, int k)` sử dụng đúng $01$ Stack phụ để đảo ngược thứ tự $k$ phần tử đầu tiên của Queue $q$, giữ nguyên thứ tự tương đối của các phần tử còn lại.

Câu 3 (1,5 điểm - Sắp xếp & Heap).
a) Cho dãy số $A = [18, 12, 25, 6, 30, 15]$. Minh họa từng bước quá trình sắp xếp dãy $A$ tăng dần bằng thuật toán Insertion Sort.
b) Cho mảng Max Heap nhị phân hiện tại: `[-, T, S, R, A, C, B]` (ô đầu tiên để trống ở chỉ số 0). Minh họa từng bước quá trình thêm khóa `U` vào heap.

Câu 4 (1,5 điểm - Cây tìm kiếm nhị phân BST).
a) Vẽ cây nhị phân tìm kiếm thu được sau khi thêm lần lượt chuỗi khóa `E, C, G, A, D, F, H` vào cây rỗng.
b) Viết hàm đệ quy tính chiều cao (`height`) của cây BST.

Câu 5 (1,0 điểm - Bài toán ứng dụng).
Hãy thiết kế cấu trúc dữ liệu `MinMaxStack` hỗ trợ các thao tác `push(x)`, `pop()`, `getMin()`, `getMax()` đều đạt độ phức tạp thời gian $O(1)$ trong trường hợp tồi nhất và bộ nhớ phụ $O(N)$. Mô tả ý tưởng và mã giả.

--------- HẾT ĐỀ SỐ 1 ---------

PHẦN I. TRẮC NGHIỆM (3,0 điểm)

Thí sinh chọn một phương án đúng duy nhất cho mỗi câu hỏi sau:

Câu 1. Thao tác `connected(p, q)` trong thuật toán Quick-Union cơ bản có độ phức tạp tồi nhất là:

Câu 2. Hàng đợi (Queue) là cấu trúc dữ liệu hoạt động theo nguyên tắc nào?

Câu 3. Thuật toán Sắp xếp Nổi bọt (Bubble Sort) cải tiến (dừng khi không có phép đổi chỗ) có độ phức tạp tốt nhất (Best case) là:

Câu 4. Trong thuật toán Mergesort Top-down, mảng phụ `aux` nên được cấp phát bộ nhớ ở đâu để tối ưu hiệu năng?

Câu 5. Cho mảng biểu diễn Max Heap: `[-, 90, 70, 80, 30, 40, 50, 60]`. Khóa con trái và con phải của nút có giá trị $70$ lần lượt là:

Câu 6. Khi xóa một nút $X$ có đầy đủ $2$ con trong cây BST, ta thay thế $X$ bằng nút nào để giữ nguyên tính chất BST?

Câu 7. Thuật toán 3-way Quicksort (phân chia 3 đoạn) đạt hiệu năng vượt trội $O(N)$ khi mảng đầu vào có đặc điểm gì?

Câu 8. Đối với Danh sách liên kết kép (Doubly Linked List) có con trỏ `head` và `tail`, thao tác xóa phần tử ở cuối danh sách (`removeLast`) có độ phức tạp thời gian là:

Câu 9. Thuật toán sắp xếp nào dưới đây KHÔNG có tính ổn định (Unstable)?

Câu 10. Phép toán `sink(k)` (hạ xuống) trong Max Heap được sử dụng trong thao tác nào?

Câu 11. Số phép so sánh nhiều nhất trong trường hợp tồi nhất của thuật toán Tìm kiếm nhị phân (Binary Search) trên mảng $N$ phần tử là:

Câu 12. Trong cài đặt Stack bằng mảng tự điều chỉnh kích thước (Resizing Array), mảng sẽ gấp đôi dung lượng khi nào?

Câu 13. Biểu thức Trung tố $(A + B) * C$ khi chuyển sang biểu thức Hậu tố (Postfix) là:

Câu 14. Nếu thêm lần lượt các khóa đã sắp xếp tăng dần $10, 20, 30, 40, 50$ vào một cây BST rỗng, cây thu được sẽ có dạng gì?

Câu 15. Kỹ thuật "Shuffle" (tráo ngẫu nhiên mảng) trước khi chạy Quicksort nhằm mục đích gì?

PHẦN II. TỰ LUẬN (7,0 điểm)

Câu 1 (1,5 điểm - Phân tích thuật toán).
Cho đoạn code Java sau tính tổng các phần tử mảng:

void processArray(int a[], int N) {
int sum = 0;
for (int i = 1; i < N; i *= 2) {
for (int j = 0; j < i; j++) {
sum += a[j];
}
}
}

a) Tính số lần thực hiện lệnh `sum += a[j]` theo $N$ khi $N = 2^k$.
b) Xác định cấp phát triển (Order of growth) theo $O$ của đoạn code trên.

Câu 2 (1,5 điểm - Stack & Queue).
a) Cho một Stack $S$ rỗng. Cho chuỗi thao tác:

$$\text{push}(7) \to \text{push}(6) \to \text{push}(5) \to \text{pop}() \to \text{isEmpty}() \to \text{push}(8) \to \text{pop}()$$

Cho biết tình trạng Stack sau mỗi thao tác và kết quả trả về của các hàm `pop()`, `isEmpty()`.
b) Viết hàm `boolean isBalanced(String expr)` sử dụng Stack để kiểm tra tính hợp lệ của các cặp dấu ngoặc `()`, `[]`, `{}` trong chuỗi `expr`.

Câu 3 (1,5 điểm - Sắp xếp & Heap).
a) Cho mảng chưa sắp xếp $A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]$. Hãy minh họa quá trình dựng Max Heap tại chỗ (`buildHeap` bằng phương pháp bottom-up / dùng `sink`).
b) Cho mảng Max Heap hiện tại: `[-, U, T, S, B, D, C]`. Minh họa từng bước xóa phần tử lớn nhất khỏi heap.

Câu 4 (1,5 điểm - Cây BST).
a) Cho chuỗi khóa `M, B, D, C, A, S, H, P, E`. Vẽ cây BST thu được sau khi thêm chuỗi khóa trên vào cây rỗng.
b) Viết hàm đệ quy `int countLeaves(Node root)` đếm số lượng nút lá (nút không có con) trong cây BST.

Câu 5 (1,0 điểm - Bài toán ứng dụng).
Cho một mảng $A$ chứa $N$ số nguyên, trong đó có một phần tử xuất hiện nhiều hơn $N/2$ lần (phần tử đa số - Majority Element). Hãy đề xuất thuật toán tìm phần tử này với thời gian $O(N)$ hoặc $O(N \log N)$ và bộ nhớ phụ $O(1)$ (gợi ý: dùng Quickselect hoặc Boyer-Moore Voting).

--------- HẾT ĐỀ SỐ 2 ---------

PHẦN I. TRẮC NGHIỆM (3,0 điểm)

Thí sinh chọn một phương án đúng duy nhất cho mỗi câu hỏi sau:

Câu 1. Trong thuật toán Weighted Quick-Union với Path Compression, độ phức tạp thời gian amortized cho mỗi thao tác find/union là:

Câu 2. Cấu trúc dữ liệu nào phù hợp nhất để quản lý chức năng "Undo" (Hoàn tác) trong trình soạn thảo văn bản?

Câu 3. Thuật toán Selection Sort thực hiện bao nhiêu phép đổi chỗ (swap/exchange) trong trường hợp tồi nhất đối với mảng $N$ phần tử?

Câu 4. Nhược điểm lớn nhất của Mergesort so với Quicksort là gì?

Câu 5. Chiều cao của một Cây nhị phân hoàn chỉnh (Complete Binary Tree) chứa $N$ nút là:

Câu 6. Trong cây BST, thao tác `select(k)` trả về thông tin gì?

Câu 7. Trong thuật toán Quicksort tiêu chuẩn (hoặc Lomuto/Hoare partition), sau bước phân chia (partitioning) đầu tiên với chốt $v$, vị trí của chốt $v$ có đặc điểm gì?

Câu 8. Thuật toán Heapsort có độ phức tạp thời gian trong trường hợp tồi nhất là:

Câu 9. Cho mảng Max Heap: `[-, 95, 80, 75, 30, 40, 50, 60]`. Sau khi thực hiện 1 thao tác `delMax()`, giá trị ở gốc Heap mới là bao nhiêu?

Câu 10. Trong Danh sách liên kết đơn, để chèn một nút mới vào ngay sau nút $P$, ta cần thực hiện các lệnh nào (theo thứ tự)?

Câu 11. Vòng lặp `for (int i = N; i > 0; i /= 2)` thực hiện bao nhiêu lần lặp?

Câu 12. Cho biểu thức Hậu tố (Postfix): `5 3 2 * + 4 -`. Giá trị của biểu thức là:

Câu 13. Trong mảng vòng (Circular Array) dùng cài đặt Queue kích thước $M$, vị trí tiếp theo của chỉ số `rear` sau khi tăng được tính theo công thức nào?

Câu 14. Thao tác `floor(key)` trong cây BST trả về:

Câu 15. Thuật toán sắp xếp nào sau đây hoạt động theo mô hình Chia để trị (Divide and Conquer)?

PHẦN II. TỰ LUẬN (7,0 điểm)

Câu 1 (1,5 điểm - Phân tích thuật toán).
Cho đoạn code sau kiểm tra mảng:

void checkMatch(int a[], int N) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i < j && a[i] == a[j]) {
count++;
}
}
}
}

a) Tính chính xác số lần phép so sánh `a[i] == a[j]` được thực hiện.
b) Tính số lần phép so sánh `i < j` được thực hiện. Độ phức tạp $O$ của thuật toán là gì?

Câu 2 (1,5 điểm - Stack & Queue / Danh sách liên kết).
a) Cho Queue $Q$ rỗng. Thực hiện:

$$\text{enqueue}(3) \to \text{dequeue}() \to \text{isEmpty}() \to \text{enqueue}(2) \to \text{enqueue}(1) \to \text{dequeue}()$$

Trình bày trạng thái Queue sau mỗi bước và kết quả các hàm.
b) Viết hàm bằng Java/mã giả `Node removeAllX(Node head, int x)` xóa tất cả các nút có giá trị bằng $x$ khỏi Danh sách liên kết đơn.

Câu 3 (1,5 điểm - Sắp xếp & Heap).
a) Cho mảng $A = [45, 12, 89, 34, 67, 23, 10]$. Minh họa từng bước quá trình sắp xếp mảng $A$ tăng dần bằng Mergesort Top-down (vẽ cây đệ quy trộn).
b) Cho mảng Max Heap nhị phân: `[-, 90, 80, 70, 20, 40, 30]`. Minh họa từng bước quá trình thêm khóa $85$ vào Heap.

Câu 4 (1,5 điểm - Cây BST).
a) Thêm các khóa $50, 30, 70, 20, 40, 60, 80$ vào cây BST rỗng. Vẽ cây kết quả. Sau đó vẽ cây thu được sau khi xóa khóa $30$.
b) Viết hàm đệ quy `Key maxKey(Node root)` trả về giá trị khóa lớn nhất trong cây BST.

Câu 5 (1,0 điểm - Bài toán ứng dụng).
Thiết kế thuật toán độ phức tạp $O(\log N)$ tìm chỉ số $i$ của phần tử $1$ đầu tiên trong mảng đã sắp xếp chỉ chứa các số $0$ và $1$ (giả sử mảng có dạng $[0, 0, \dots, 0, 1, 1, \dots, 1]$). Viết mã giả dựa trên Tìm kiếm nhị phân.

--------- HẾT ĐỀ SỐ 3 ---------

PHẦN I. TRẮC NGHIỆM (3,0 điểm)

Thí sinh chọn một phương án đúng duy nhất cho mỗi câu hỏi sau:

Câu 1. Trong bài toán Dynamic Connectivity, tập hợp các phần tử liên thông tạo thành một:

Câu 2. Chuyển biểu thức Trung tố $A * (B + C) / D$ sang biểu thức Hậu tố (Postfix):

Câu 3. Thuật toán sắp xếp nào có số phép truy nhập mảng (Array accesses) ít nhất trong trường hợp tồi nhất đối với mảng đã sắp xếp ngược?

Câu 4. Trong thuật toán 3-way Quicksort, sau khi phân chia mảng theo chốt $v$, mảng được chia thành 3 đoạn nào?

Câu 5. Trong một Min Heap nhị phân, phần tử nhỏ nhất luôn nằm ở vị trí nào?

Câu 6. Nút gốc (Root) của một cây nhị phân có đặc điểm gì?

Câu 7. Nếu chạy Quicksort tiêu chuẩn (chọn chốt là phần tử đầu tiên, không shuffle) trên mảng đã sắp xếp tăng dần, độ phức tạp thời gian sẽ là:

Câu 8. Kỹ thuật "Bồi hoàn" (Amortized Analysis) cho thao tác `push` trên Stack dùng mảng tự gấp đôi kích thước cho kết quả độ phức tạp trung bình là:

Câu 9. Thuật toán Sắp xếp Chèn (Insertion Sort) chạy mất thời gian $O(N)$ khi mảng đầu vào có số cặp nghịch đảo (inversions) là:

Câu 10. Trong Max Heap nhị phân (mảng từ index 1), thao tác `swim(k)` thực hiện so sánh khóa ở vị trí $k$ với nút nào?

Câu 11. Số lượng liên kết null trong một cây nhị phân có $N$ nút là bao nhiêu?

Câu 12. Mảng gồm $N$ phần tử có số lượng cặp nghịch đảo (inversions) nhiều nhất là bao nhiêu?

Câu 13. Trong cây BST, thao tác `ceiling(key)` trả về khóa nào?

Câu 14. Cấu trúc dữ liệu Túi (Bag) khác Stack và Queue ở điểm cơ bản nào?

Câu 15. Độ phức tạp không gian (Auxiliary Space) của thuật toán Quicksort tiêu chuẩn (do bộ nhớ stack đệ quy) trong trường hợp trung bình là:

PHẦN II. TỰ LUẬN (7,0 điểm)

Câu 1 (1,5 điểm - Phân tích thuật toán).
Cho thuật toán Tìm kiếm nhị phân (Binary Search).
a) Tính số lần gọi hàm `compare` trong trường hợp tốt nhất và tồi nhất theo $N$.
b) Giải thích ý nghĩa của công thức `mid = lo + (hi - lo) / 2` thay vì `(lo + hi) / 2`.

Câu 2 (1,5 điểm - Stack & Queue).
a) Cho Queue $Q$ rỗng. Cho chuỗi thao tác:

$$\text{enqueue}(7) \to \text{enqueue}(6) \to \text{enqueue}(5) \to \text{dequeue}() \to \text{isEmpty}()$$

Cho biết tình trạng Queue và giá trị trả về.
b) Viết hàm `String infixToPostfix(String exp)` chuyển biểu thức Trung tố có ngoặc sang Hậu tố bằng thuật toán Dijkstra 2-stack.

Câu 3 (1,5 điểm - Sắp xếp & Heap).
a) Cho Max Heap nhị phân hiện tại: `[-, 85, 75, 60, 40, 50, 30]`. Minh họa từng bước quá trình thêm khóa $68$ vào Heap.
b) Tiếp tục với Heap thu được ở câu a, minh họa từng bước xóa phần tử lớn nhất (`delMax`).

Câu 4 (1,5 điểm - Cây BST).
a) Cho chuỗi khóa $80, 20, 40, 30, 10, 100, 70, 90, 50$. Vẽ cây BST thu được sau khi thêm lần lượt chuỗi khóa trên vào cây rỗng.
b) Viết hàm đệ quy `int sumKeys(Node root)` tính tổng giá trị tất cả các khóa số nguyên trong cây BST.

Câu 5 (1,0 điểm - Bài toán ứng dụng).
Thiết kế cấu trúc dữ liệu `UniStack` chứa các chuỗi String hỗ trợ `push(x)` và `pop()` như Stack thông thường nhưng đảm bảo không chứa phần tử trùng lặp. Yêu cầu: `push` và `pop` tốn thời gian $O(1)$ hoặc $O(\log N)$, bộ nhớ $O(N)$.

--------- HẾT ĐỀ SỐ 4 ---------

ĐÁP ÁN VÀ LỜI GIẢI CHI TIẾT ĐỀ SỐ 4

1. Đáp án trắc nghiệm Đề số 4

2. Lời giải tự luận Đề số 4

Câu 1 (1,5 điểm)
a) Số lần gọi `compare`:
- Trường hợp tốt nhất: $1$ lần (khi `a[mid] == key` ngay lần thử đầu tiên tại điểm giữa).
- Trường hợp tồi nhất: $\lfloor \log_2 N \rfloor + 1$ lần (khi không tìm thấy khóa hoặc khóa ở tận nhánh con chia đôi cuối cùng).

b) Ý nghĩa công thức `mid = lo + (hi - lo) / 2`:
- Về mặt đại số, $lo + (hi - lo) / 2 = (lo + hi) / 2$.
- Trong ngôn ngữ lập trình (Java/C++), nếu $lo$ và $hi$ lớn, tổng $lo + hi$ có thể vượt quá giá trị cực đại của số nguyên 32-bit có dấu ($2^{31} - 1 = 2\,147\,483\,647$), dẫn đến hiện tượng tràn số (integer overflow) làm kết quả bị âm.
- Biểu thức $lo + (hi - lo) / 2$ thực hiện phép trừ trước ($hi - lo \ge 0$) nên không bao giờ xảy ra tràn số.

Câu 2 (1,5 điểm)
a) Trạng thái Queue $Q$ qua từng thao tác (quy ước bên phải là đầu ra):
- $\text{enqueue}(7) \to Q: [7]$
- $\text{enqueue}(6) \to Q: [6, 7]$
- $\text{enqueue}(5) \to Q: [5, 6, 7]$
- $\text{dequeue}() \to$ Trả về giá trị $7$, trạng thái $Q: [5, 6]$
- $\text{isEmpty}() \to$ Trả về `false`, trạng thái $Q: [5, 6]$

b) Hàm `infixToPostfix` bằng Java:

public static String infixToPostfix(String exp) {
Stack<String> ops = new Stack<>();
StringBuilder postfix = new StringBuilder();
String[] tokens = exp.split("\\s+");

for (String token : tokens) {
if (token.equals("(")) {
// Bỏ qua dấu mở ngoặc
} else if (token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/")) {
ops.push(token);
} else if (token.equals(")")) {
postfix.append(ops.pop()).append(" ");
} else {
postfix.append(token).append(" ");
}
}
return postfix.toString().trim();
}

Câu 3 (1,5 điểm)
a) Thêm khóa $68$ vào Max Heap `[-, 85, 75, 60, 40, 50, 30]`:
- Bước 1: Thêm $68$ vào vị trí cuối mảng (chỉ số 7): `[-, 85, 75, 60, 40, 50, 30, 68]`.
- Bước 2: Gọi `swim(7)`: Nút cha tại chỉ số $\lfloor 7/2 \rfloor = 3$ có giá trị $60$. Do $68 > 60$, hoán đổi $68$ và $60$.
$\to$ Mảng: `[-, 85, 75, 68, 40, 50, 30, 60]`.
- Bước 3: Gọi `swim(3)`: Nút cha tại chỉ số $\lfloor 3/2 \rfloor = 1$ có giá trị $85$. Do $68 < 85$, điều kiện Max Heap thỏa mãn. Dừng.
$\to$ Kết quả: `[-, 85, 75, 68, 40, 50, 30, 60]`.

b) Xóa phần tử lớn nhất (`delMax`) từ Heap trên:
- Bước 1: Đổi chỗ gốc ($85$ tại index 1) với phần tử cuối ($60$ tại index 7), giảm kích thước mảng còn $6$. Xóa $85$.
$\to$ Mảng tạm: `[-, 60, 75, 68, 40, 50, 30]`.
- Bước 2: Gọi `sink(1)`: Gốc $60$ có con trái là $75$ (index 2) và con phải là $68$ (index 3). Con lớn nhất là $75$. Do $60 < 75$, hoán đổi $60$ và $75$.
$\to$ Mảng: `[-, 75, 60, 68, 40, 50, 30]`.
- Bước 3: Xét nút $60$ tại index 2: có con trái là $40$ (index 4) và con phải là $50$ (index 5). Con lớn nhất là $50$. Do $60 > 50$, điều kiện Max Heap thỏa mãn. Dừng.
$\to$ Kết quả: `[-, 75, 60, 68, 40, 50, 30]`.

Câu 4 (1,5 điểm)
a) Cây BST sau khi thêm chuỗi khóa `80, 20, 40, 30, 10, 100, 70, 90, 50`:

80
/ \
20 100
/ \ /
10 40 90
/ \
30 70
/
50

- $80$ là gốc.
- $20 < 80 \implies$ rẽ trái.
- $40 > 20 \implies$ rẽ phải của $20$.
- $30 < 40 \implies$ rẽ trái của $40$.
- $10 < 20 \implies$ rẽ trái của $20$.
- $100 > 80 \implies$ rẽ phải của $80$.
- $70 > 40 \implies$ rẽ phải của $40$.
- $90 < 100 \implies$ rẽ trái của $100$.
- $50 < 70 \implies$ rẽ trái của $70$.

b) Hàm đệ quy tính tổng các khóa:

int sumKeys(Node root) {
if (root == null) return 0;
return root.key + sumKeys(root.left) + sumKeys(root.right);
}

Câu 5 (1,0 điểm)
Thiết kế cấu trúc `UniStack`:
- Cấu trúc kết hợp:
- Danh sách liên kết kép (Doubly Linked List - DLL): Nút chứa giá trị chuỗi và 2 con trỏ `prev`, `next`. Con trỏ `head` trỏ tới đỉnh Stack.
- Bảng băm (`HashMap<String, Node>`): Lưu ánh xạ từ chuỗi giá trị tới nút chứa nó trong DLL.
- Thao tác `push(x)`:
- Kiểm tra `map.containsKey(x)`. Nếu đã tồn tại, lấy nút ra và ngắt liên kết khỏi DLL trong $O(1)$.
- Tạo nút mới chứa `x`, chèn lên đầu DLL (`head`) trong $O(1)$.
- Cập nhật địa chỉ nút vào `map.put(x, newNode)`.
- Thao tác `pop()`:
- Lấy giá trị chuỗi tại `head.val`.
- Xóa nút `head` khỏi DLL và xóa khóa tương ứng trong `map`.
- Trả về giá trị đã lấy.
- Độ phức tạp: Thời gian $O(1)$ cho mỗi thao tác, bộ nhớ phụ $O(N)$ đáp ứng hoàn toàn yêu cầu đề bài.

PHẦN I. TRẮC NGHIỆM (3,0 điểm)

Thí sinh chọn một phương án đúng duy nhất cho mỗi câu hỏi sau:

Câu 1. Giả sử thực hiện $M$ thao tác union/find trên cấu trúc dữ liệu Quick-Union có trọng số (Weighted Quick-Union) với $N$ đối tượng. Thời gian chạy tồi nhất tỉ lệ với:

Câu 2. Cấu trúc dữ liệu Hàng đợi (Queue) thường được ứng dụng trong thuật toán nào sau đây?

Câu 3. Thuật toán sắp xếp nào sau đây có thời gian chạy trường hợp tốt nhất (Best case) là $O(N)$?

Câu 4. Giáo viên cần sắp xếp danh sách sinh viên: đầu tiên theo Nhóm thực hành, sau đó trong từng nhóm sắp xếp theo Tên ABC. Hỏi thuật toán sắp xếp được chọn bắt buộc phải có đặc tính gì nếu ta sắp xếp theo Tên trước rồi mới sắp xếp theo Nhóm thực hành?

Câu 5. Mức (Level) hay Độ sâu (Depth) của nút gốc trong cây nhị phân theo quy ước thông thường bằng bao nhiêu?

Câu 6. Kết quả duyệt cây BST theo thứ tự Postorder (Hậu tự) luôn thăm nút gốc ở vị trí nào?

Câu 7. Phương pháp sắp xếp Trộn Bottom-up Mergesort thực hiện sắp xếp mảng mà KHÔNG sử dụng:

Câu 8. Cho mảng biểu diễn Min Heap: `[-, 5, 12, 10, 15, 20, 25]`. Giá trị của nút con phải của nút gốc là:

Câu 9. Trong thuật toán Quicksort, bước Phân chia mảng (Partitioning) tiêu chuẩn mất thời gian:

Câu 10. Trong cài đặt Stack bằng Danh sách liên kết đơn, thao tác `push(x)` và `pop()` thực hiện ở đầu danh sách có độ phức tạp thời gian là:

Câu 11. Cho hai hàm $f(N) = N \log_2 N$ và $g(N) = N^{1.5}$. Phát biểu nào sau đây đúng về cấp tăng?

Câu 12. Cấu trúc Priority Queue cài đặt bằng Mảng đã sắp xếp tăng dần có độ phức tạp của thao tác `insert` và `delMax` lần lượt là:

Câu 13. Trong cây BST, thao tác `rank(key)` trả về giá trị gì?

Câu 14. Trong thuật toán Dijkstra 2-stack để tính giá trị biểu thức số học, khi gặp dấu đóng ngoặc `)`, ta thực hiện thao tác gì?

Câu 15. Sự khác biệt cơ bản về nguyên lý giữa Selection Sort và Insertion Sort là gì?

PHẦN II. TỰ LUẬN (7,0 điểm)

Câu 1 (1,5 điểm - Phân tích thuật toán).
Cho hàm `mergeTwo` dưới đây:

void mergeTwo(int a[], int aux[], int N) {
int lo = 0, mid = N / 2, hi = N - 1;
for (int k = lo; k <= hi; k++) aux[k] = a[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}

a) Tính chính xác số lần truy nhập mảng (đọc/ghi trên `a` và `aux`) theo $N$.
b) Cho biết độ phức tạp thời gian theo $O$ và Tilde ($\sim$) trong trường hợp tốt nhất và tồi nhất.

Câu 2 (1,5 điểm - Stack & Queue).
a) Cho Queue $Q = [1, 2, 3, 4, 5]$ (đầu lấy phần tử là $1$) và Stack $S$ rỗng. Viết đoạn code đảo ngược thứ tự các phần tử trong $Q$.
b) Viết hàm `boolean areEqualStacks(Stack<Integer> s1, Stack<Integer> s2)` kiểm tra xem 2 Stack có giống hệt nhau về nội dung và thứ tự không mà không làm thay đổi trạng thái ban đầu của $s1, s2$.

Câu 3 (1,5 điểm - Sắp xếp & Heap).
a) Cho mảng $A = [32, 15, 7, 28, 4, 19, 30, 22]$. Minh họa bước Partition đầu tiên của Quicksort tiêu chuẩn (chốt là phần tử đầu tiên $A[0]$).
b) Minh họa các bước sắp xếp mảng $A = [25, 67, 34, 15, 42, 7, 9]$ bằng Insertion Sort.

Câu 4 (1,5 điểm - Cây BST).
a) Thêm các khóa $25, 15, 35, 10, 20, 30, 40$ vào cây BST rỗng. Vẽ cây kết quả.
b) Viết hàm đệ quy `int countSingleChildNodes(Node root)` đếm số lượng nút trong cây BST chỉ có đúng 1 nút con.

Câu 5 (1,0 điểm - Bài toán ứng dụng).
Thiết kế cấu trúc dữ liệu `Tournament` lưu trữ thông tin đấu thủ: `insert(name, score)`, `getScore(name)`, `getLead()`. Yêu cầu cả 3 hàm chạy thời gian $O(\log N)$, bộ nhớ $O(N)$.

--------- HẾT ĐỀ SỐ 5 ---------