PDF Đề cương – Tiểu luận mẫu – Bài tập lớn – Đề thi mẫu Cấu trúc dữ liệu và Giải thuật UED & UFM có đáp án năm 2025

TRÍCH DẪN ĐỀ MÔ TÀI LIỆU (Đề thi mẫu cuối kỳ UED & UFM)

ĐỀ THI MẪU CUỐI KỲ MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (UED & UFM)

Thời gian: 90 phút (UED), 75 phút (UFM)

Ngày thi: 15/01/2026

Phần I: Trắc nghiệm (4.0 điểm cho UED, 5.0 điểm cho UFM)

(Chọn đáp án đúng nhất cho mỗi câu hỏi. Mỗi câu 0.5 điểm)

Câu 1 (UED & UFM): Khi nào thì một hàng đợi (Queue) được xem là đầy khi cài đặt bằng mảng tròn (circular array)?

A. Khi `front == rear`
B. Khi `(rear + 1) % MAX_SIZE == front`
C. Khi `count == 0`
D. Khi `front == 0` và `rear == MAX_SIZE – 1`

Câu 2 (UED): Cho một cây nhị phân tìm kiếm cân bằng AVL (AVL Tree). Nếu một phép thêm/xóa làm mất cân bằng tại một node, cần thực hiện phép quay nào để cân bằng lại trong trường hợp “Left-Right” (LR)?

A. Một lần quay trái (Left Rotation)
B. Một lần quay phải (Right Rotation)
C. Một lần quay trái, sau đó một lần quay phải (Left-Right Rotation)
D. Một lần quay phải, sau đó một lần quay trái (Right-Left Rotation)

Câu 3 (UFM): Phát biểu nào sau đây là đúng về danh sách liên kết đơn (Singly Linked List)?

A. Truy cập phần tử theo chỉ số (random access) có độ phức tạp $O(1)$.
B. Thêm/xóa phần tử ở đầu danh sách có độ phức tạp $O(N)$.
C. Thêm/xóa phần tử ở giữa danh sách yêu cầu duyệt qua các phần tử trước đó.
D. Không thể thực hiện tìm kiếm phần tử trong danh sách liên kết.

Câu 4 (UED & UFM): Giải thuật nào sau đây được sử dụng để tìm đường đi ngắn nhất trong đồ thị có trọng số âm (không có chu trình âm)?

A. Dijkstra’s Algorithm
B. Prim’s Algorithm
C. Kruskal’s Algorithm
D. Bellman-Ford Algorithm

…

Phần II: Tự luận (6.0 điểm cho UED, 5.0 điểm cho UFM)

Bài 1 (3.0 điểm – UED): Đồ thị và Giải thuật (Floyd-Warshall)

Cho ma trận kề trọng số của đồ thị có hướng 4 đỉnh (A, B, C, D) như sau:

        A   B   C   D
      A [0,  3, ∞,  7]
      B [8,  0,  2, ∞]
      C [5, ∞,  0,  1]
      D [2, ∞, ∞,  0]

Yêu cầu:

a. (2.0 điểm) Áp dụng giải thuật **Floyd-Warshall** để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh. Ghi lại các ma trận $D^{(k)}$ sau mỗi bước lặp $k$ (từ $k=0$ đến $k=N-1$).

b. (1.0 điểm) Từ ma trận kết quả cuối cùng, hãy chỉ ra đường đi ngắn nhất từ đỉnh `A` đến đỉnh `D` và trọng số của đường đi đó.

Bài 2 (2.0 điểm – UED & UFM): Cây tìm kiếm nhị phân (BST) và thao tác

Cho một cây BST rỗng. Thực hiện lần lượt các thao tác thêm các khóa số nguyên sau vào cây theo đúng thứ tự: `70, 40, 90, 20, 50, 80, 100, 30`.

Yêu cầu:

a. (1.0 điểm) Vẽ trạng thái của cây BST sau khi tất cả các phần tử trên được thêm vào.

b. (1.0 điểm) Viết hàm C++ `int countLeafNodes(Node* root)` để đếm số lượng node lá (node không có con) trong cây BST.

Bài 3 (1.0 điểm – UFM): Cài đặt Hàng đợi (Queue) sử dụng mảng

Yêu cầu:

a. (1.0 điểm) Viết code Java để cài đặt một lớp `Queue` sử dụng mảng tĩnh với kích thước cố định `MAX_SIZE`. Lớp này cần có các phương thức cơ bản: `enqueue()`, `dequeue()`, `isFull()`, `isEmpty()`, và `peek()`. Sử dụng cơ chế mảng tròn để tối ưu không gian.

—

ĐÁP ÁN THAM KHẢO

Phần I: Trắc nghiệm

Câu 1: B. Khi `(rear + 1) % MAX_SIZE == front`
Giải thích: Trong cài đặt Queue bằng mảng tròn, queue được xem là đầy khi chỉ số của `rear` sau khi tăng 1 (modulo MAX_SIZE) bằng với chỉ số của `front`. Điều này đảm bảo rằng có đúng một ô trống được giữ lại để phân biệt trạng thái đầy và rỗng.

Câu 2 (UED): C. Một lần quay trái, sau đó một lần quay phải (Left-Right Rotation)
Giải thích: Trường hợp mất cân bằng LR (Left-Right) xảy ra khi node bị mất cân bằng có cây con trái nặng hơn (L), và cây con trái đó lại có cây con phải nặng hơn (R). Để cân bằng lại, cần thực hiện một phép quay trái tại cây con trái, sau đó một phép quay phải tại node ban đầu.

Câu 3 (UFM): C. Thêm/xóa phần tử ở giữa danh sách yêu cầu duyệt qua các phần tử trước đó.
Giải thích:

• A sai: Truy cập ngẫu nhiên theo chỉ số trong danh sách liên kết có độ phức tạp $O(N)$ vì phải duyệt từ đầu.
• B sai: Thêm/xóa phần tử ở đầu danh sách liên kết đơn có độ phức tạp $O(1)$.
• C đúng: Để thêm/xóa một phần tử ở giữa, cần tìm đến node ngay trước vị trí cần thao tác, điều này đòi hỏi duyệt qua các phần tử.
• D sai: Có thể tìm kiếm phần tử trong danh sách liên kết bằng cách duyệt tuần tự.

Câu 4: D. Bellman-Ford Algorithm
Giải thích: Giải thuật Dijkstra chỉ hoạt động với các cạnh có trọng số không âm. Bellman-Ford là giải thuật phù hợp để tìm đường đi ngắn nhất trong đồ thị có trọng số âm, miễn là không có chu trình âm.

…

Phần II: Tự luận

Bài 1 (UED): Đồ thị và Giải thuật (Floyd-Warshall)

a. **Các ma trận $D^{(k)}$ của Floyd-Warshall:**

(Minh họa chi tiết từng bước cập nhật ma trận $D$ và $P$ (predecessor matrix) nếu có)

Ma trận $D^{(0)}$ (ma trận kề trọng số ban đầu):

        A   B   C   D
      A [0,  3, ∞,  7]
      B [8,  0,  2, ∞]
      C [5, ∞,  0,  1]
      D [2, ∞, ∞,  0]

Ma trận $D^{(1)}$ (k=A):

        A   B   C   D
      A [0,  3, ∞,  7]
      B [8,  0,  2, 10] (min(∞, 8+7))
      C [5,  8,  0,  1] (min(∞, 5+3))
      D [2,  5, ∞,  0]  (min(∞, 2+3))

(Tiếp tục minh họa cho $D^{(2)}$ (k=B), $D^{(3)}$ (k=C), $D^{(4)}$ (k=D))

b. **Đường đi ngắn nhất từ A đến D:**

(Từ ma trận $D^{(N-1)}$ cuối cùng, truy vết đường đi từ $A$ đến $D$ qua ma trận $P$ (nếu có)).

Ví dụ: Nếu kết quả cuối cùng là $D(A,D) = 6$, đường đi có thể là $A \rightarrow B \rightarrow C \rightarrow D$ hoặc $A \rightarrow C \rightarrow D$. (Cần dựa vào kết quả tính toán chi tiết).

Kết quả cuối cùng cho đồ thị trên:

        A   B   C   D
      A [0,  3,  5,  6]
      B [7,  0,  2,  3]
      C [3,  6,  0,  1]
      D [2,  5,  7,  0]

Đường đi ngắn nhất từ A đến D là 6.

Đường đi cụ thể là: A → C → D (trọng số 5 + 1 = 6)

Hoặc A → B → C → D (trọng số 3 + 2 + 1 = 6)

Cả hai đường đều có trọng số 6. (Cần kiểm tra lại bằng ma trận tiền nhiệm).

Bài 2 (UED & UFM): Cây tìm kiếm nhị phân (BST) và thao tác

a. (Minh họa vẽ cây BST sau khi thêm từng phần tử)

b. **Hàm C++ `int countLeafNodes(Node* root)`:**

      // C++ Code
      #include <iostream>

      struct Node {
          int data;
          Node* left;
          Node* right;
          Node(int val) : data(val), left(nullptr), right(nullptr) {}
      };

      // Hàm đếm số lượng node lá
      int countLeafNodes(Node* root) {
          if (root == nullptr) {
              return 0; // Cây rỗng không có node lá
          }
          if (root->left == nullptr && root->right == nullptr) {
              return 1; // Đây là node lá
          }
          // Đệ quy đếm node lá ở cây con trái và cây con phải
          return countLeafNodes(root->left) + countLeafNodes(root->right);
      }

      // Hàm insert (để tạo cây test)
      Node* insert(Node* root, int value) {
          if (root == nullptr) {
              return new Node(value);
          }
          if (value < root->data) {
              root->left = insert(root->left, value);
          } else if (value > root->data) {
              root->right = insert(root->right, value);
          }
          return root;
      }

      int main() {
          Node* root = nullptr;
          root = insert(root, 70);
          root = insert(root, 40);
          root = insert(root, 90);
          root = insert(root, 20);
          root = insert(root, 50);
          root = insert(root, 80);
          root = insert(root, 100);
          root = insert(root, 30);

          // Cây sẽ có các node lá: 30, 80, 100
          std::cout << "Number of leaf nodes: " << countLeafNodes(root) << std::endl; // Expected: 3

          // Giải phóng bộ nhớ (không cần trong bài thi, nhưng nên có trong code thực tế)
          // (Cần hàm xóa cây để giải phóng bộ nhớ)
          return 0;
      }

Bài 3 (UFM): Cài đặt Hàng đợi (Queue) sử dụng mảng

      // Java Code
      import java.util.NoSuchElementException;

      public class MyCircularQueue {
          private int[] arr;
          private int front;
          private int rear;
          private int count;
          private int capacity;

          public MyCircularQueue(int size) {
              capacity = size;
              arr = new int[capacity];
              front = -1; // -1 indicates empty queue
              rear = -1;  // -1 indicates empty queue
              count = 0;
          }

          public boolean isEmpty() {
              return count == 0;
          }

          public boolean isFull() {
              return count == capacity;
          }

          public void enqueue(int value) {
              if (isFull()) {
                  System.out.println("Queue is full. Cannot enqueue " + value);
                  return;
              }
              if (isEmpty()) {
                  front = 0; // When queue is empty, first element makes front 0
              }
              rear = (rear + 1) % capacity; // Move rear circularly
              arr[rear] = value;
              count++;
              System.out.println("Enqueued: " + value);
          }

          public int dequeue() {
              if (isEmpty()) {
                  System.out.println("Queue is empty. Cannot dequeue.");
                  throw new NoSuchElementException("Queue is empty.");
              }
              int dequeuedValue = arr[front];
              if (front == rear) { // If only one element left
                  front = -1;
                  rear = -1;
              } else {
                  front = (front + 1) % capacity; // Move front circularly
              }
              count--;
              return dequeuedValue;
          }

          public int peek() {
              if (isEmpty()) {
                  System.out.println("Queue is empty. No element to peek.");
                  throw new NoSuchElementException("Queue is empty.");
              }
              return arr[front];
          }

          public void printQueue() {
              if (isEmpty()) {
                  System.out.println("Queue is empty.");
                  return;
              }
              System.out.print("Queue elements: ");
              int i = front;
              int elementsPrinted = 0;
              while (elementsPrinted < count) {
                  System.out.print(arr[i] + " ");
                  i = (i + 1) % capacity;
                  elementsPrinted++;
              }
              System.out.println();
          }

          public static void main(String[] args) {
              MyCircularQueue q = new MyCircularQueue(5); // Capacity 5
              q.enqueue(10);
              q.enqueue(20);
              q.enqueue(30);
              q.printQueue(); // Expected: 10 20 30

              System.out.println("Dequeued: " + q.dequeue()); // Expected: 10
              q.printQueue(); // Expected: 20 30

              q.enqueue(40);
              q.enqueue(50);
              q.enqueue(60); // Enqueue 60, will be at arr[rear] = arr[4]

              q.printQueue(); // Expected: 20 30 40 50 60
              q.enqueue(70); // Queue is full. Cannot enqueue 70
              q.printQueue(); // Expected: 20 30 40 50 60

              System.out.println("Peek: " + q.peek()); // Expected: 20
          }
      }

…