Chuyển tới nội dung chính

Đề thi lý thuyết số 2

PHẦN 1: CÂU TRẢ LỜI NGẮN

Câu 1 (1.25 điểm) Hãy liên kết các đặc trưng ở cột bên trái với các thuật toán tương ứng ở cột bên phải. Các thuật toán có thể có những đặc trưng giống nhau.

Danh sách đặc trưng​

STTĐặc trưng
1Độ phức tạp của thuật toán trong trường hợp xấu nhất là O(nlog⁡n)O(n \log n)
2Độ phức tạp của thuật toán trong trường hợp trung bình là O(n2)O(n^2)
3Thuật toán được phân loại là online sorting
4Thuật toán sắp xếp không dựa trên kết quả so sánh giá trị (khóa) giữa các phần tử trong danh sách
5Thuật toán có số lượng phép so sánh trong mọi trường hợp (xấu nhất, trung bình, tốt nhất) đều như nhau.
6Thuật toán có số lần hoán vị ít (xấu nhất là n−1n - 1 lần)
7Thuật toán được thiết kế theo chiến lược chia để trị

Danh sách thuật toán​

STTThuật toán
ASelection Sort
BInsertion Sort
CQuick Sort
DMerge sort
EHeap sort
FCounting sort
GRadix sort

Bài làm tham khảo

1D,E-2.A,B-3.B-4.F,G-5.A-6.A-7.C,D

Câu 2 (0.5 điểm) Cho một mảng gồm 7 số nguyên như sau: 4, 9, 5, 6, 10, 2, 3. Hãy cho biết mảng sẽ thay đổi qua từng bước như thế nào khi áp dụng thuật toán QuickSort theo mã giả bên dưới, để sắp xếp mảng theo thứ tự giảm dần.

Mã giả:

void QuickSort(int a[], int left, int right) {
    int i, j, x;
    x = a[(left + right) / 2];
    i = left; j = right;
    while (i <= j) {
        while (a[i] > x) i++;
        while (a[j] < x) j--;
        if (i <= j) {
            Doicho(a[i], a[j]);
            i++; j--;
        }
    }
    if (left < j) QuickSort(a, left, j);
    if (i < right) QuickSort(a, i, right);
}

Bài làm tham khảo

4-9-5-6-10-2-3

10-9-5-6-4-2-3

10-9-5-6-4-2-3

10-9-6-5-4-2-3

10-9-6-5-4-2-3

10-9-6-5-4-2-3

10-9-6-5-4-3-2

10-9-6-5-4-3-2

10-9-6-5-4-3-2

Câu 3 (1 điểm) Xét giải thuật tạo cây nhị phân tìm kiếm, thứ tự các giá trị nhập vào cây T1 như sau: 8, 3, 5, 2, 20, 11, 30, 9, 18, 4.

Yêu cầu: (a) Cho biết kết quả duyệt cây T1 theo thứ tự Right – Left – Node (RLN); (b) Hãy vẽ lại hình ảnh cây T1 khi xóa 2 lần nút gốc sao cho cây vẫn là cây nhị phân tìm kiếm.

Bài làm tham khảo

a) RLN: 30, 18, 9, 11, 20, 4, 5, 2, 3, 8

b)

Hình ảnh cây T1 sau khi xóa 2 lần nút gốc

Câu 4 (1 điểm) Tạo một cây B-Tree T2 bậc 5 với thứ tự thêm các giá trị vào cây như sau: 1, 12, 8, 2, 25, 6, 14, 28, 17.

Yêu cầu: (a) Vẽ cây T2; (b) Sau đó, lần lượt xóa 2 giá trị là 12 và 25 ra khỏi cây T2, hãy vẽ trạng thái cây sau mỗi lượt xóa.

Quy ước: Trong quá trình xóa, ưu tiên thực hiện thủ tục nhường khóa (underflow) trước thủ tục gộp (catenation).

Bài làm tham khảo

(a)

Cây B-Tree T2 bậc 5 sau khi thêm đầy đủ các giá trị

(b)

Trạng thái cây T2 sau khi xóa giá trị 12

Trạng thái cây T2 sau khi xóa giá trị 25

Câu 5 (1 điểm) Thêm các khoá 37, 28, 24, 7, 71 vào một bảng băm địa chỉ mở HT, có kích thước M=13M = 13, sử dụng hàm băm h1(key)=key%Mh_1(key) = key \% M. Biết rằng, phương pháp giải quyết xung đột là băm kép (double hashing), với hàm băm phụ h2(key)=11−(key%11)h_2(key) = 11 - (key \% 11), và hàm băm lại h(key,i)=(h1(key)+i×h2(key))%Mh(key, i) = ( h_1(key) + i \times h_2(key) ) \% M.

Yêu cầu: (a) Hãy trình bày từng bước việc thêm các khóa vào HT bằng cách điền kết quả tính toán vào Bảng 1; (b) Cho biết vị trí thêm các khóa ở Bảng 2.

Bảng 1: Minh họa các bước tính toán trong quá trình thêm 5 khóa trên

Keyh1(key)h_1(key)h2(key)h_2(key)Kết quả băm lại lần 1Kết quả băm lại lần 2Lần 3
37
28
24
7
71

Bảng 2: Bảng băm HT sau khi thêm 5 khóa trên

Chỉ số0123456789101112
Khóa(key)

Bài làm tham khảo

Bảng 1: Minh họa các bước tính toán trong quá trình thêm 5 khóa trên

Keyh1(key)h_1(key)h2(key)h_2(key)Kết quả băm lại lần 1Kết quả băm lại lần 2Lần 3
3711
282
241197
7741126
716612

Bảng 2: Bảng băm HT sau khi thêm 5 khóa trên

Chỉ số0123456789101112
Khóa(key)287243771

Câu 6 (1.25 điểm)

Bạn đang chơi trò chơi MazeCraft, có giao diện như Hình 1. Nhận thấy rằng, bạn có thể chuyển đổi mê cung thành một đồ thị, trong đó các đỉnh đại diện cho các ô và các cạnh đại diện cho các lối đi, bạn muốn sử dụng các thuật toán tìm kiếm trên đồ thị vừa học để tìm đường đi qua mê cung.

Hình 1: Ví dụ về một mê cung trong game MazeCraft

Hãy xem xét đồ thị G1 (Hình 2) đã được chuyển đổi dưới đây.

Hình 2: Đồ thị vô hướng G1

Giả sử rằng, đồ thị được biểu diễn bằng danh sách kề (adjacency list) và tất cả các danh sách kề được sắp xếp, nghĩa là ứng với mỗi đỉnh ii, ta cần lưu trữ một danh sách có thứ tự gồm các đỉnh kề với đỉnh ii. Các đỉnh kề này được sắp xếp theo thứ tự bảng chữ cái. Thứ tự bảng chữ cái là A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z.

Hãy thực hiện các yêu cầu sau:

(a) Giả sử bạn muốn tìm một đường đi từ đỉnh A đến đỉnh H. Nếu bạn sử dụng thuật toán tìm kiếm theo chiều rộng (Breadth-First Search, BFS), hãy viết lại đường đi kết quả dưới dạng một chuỗi các đỉnh.

Bài làm tham khảo

(a) Đường đi từ đỉnh A tới đỉnh H là: A-B-D-F-H.

Lí giải:

BướcĐỉnh đang xét (Rút khỏi Queue)Các đỉnh kề chưa duyệt (Theo Alphabet)Đưa vào Queue
0Khởi tạoA
1AB, CB, C
2BD (A, C đã thấy)D
3CKhông có (A, B, D đều đã thấy)
4DE, F (B, C đã thấy)E, F
5EG (D đã thấy)G
6FH (D, G đã thấy)H

(b) Nếu bạn sử dụng thuật toán tìm kiếm theo chiều sâu (Depth-First Search, DFS) để tìm một đường đi từ đỉnh A đến đỉnh H, hãy viết lại đường đi kết quả dưới dạng một chuỗi các đỉnh, kèm theo chú thích là bạn chọn cài đặt theo cách thức nào.

Ví dụ, có 2 cách cài đặt DFS phổ biến là sử dụng Ngăn xếp để lưu các đỉnh chờ duyệt (Stack-based implementation) hoặc dùng kỹ thuật Đệ quy quay lui (Recursion-based implementation, Backtracking).

Chú thích: Ngăn xếp

Bài làm tham khảo

Đường đi từ A tới đỉnh H: A-C-D-F-H

Lí giải:

BướcĐỉnh đang xét (Rút khỏi Stack)Các đỉnh kề chưa duyệt (Theo Alphabet)Đẩy vào Stack (Trái →\rightarrow Phải)Trạng thái Stack (Đỉnh Stack ở bên Phải)
0Khởi tạoA[A]
1AB, CB, C[B, C]
2CB, D (A đã thấy)B, D[B, B, D]
3DB, E, F (C đã thấy)B, E, F[B, B, B, E, F]
4FG, H (D đã thấy)G, H[B, B, B, E, G, H]
5HĐã tới đíchThuật toán dừng

(c) Bây giờ giả sử rằng, các lối đi trong mê cung có hướng. Chạy lại thuật toán tìm kiếm theo chiều sâu (DFS) trên đồ thị có hướng G2 (Hình 3) bên dưới.

Hình 3: Đồ thị có hướng G2

Bài làm tham khảo

Đường đi từ đỉnh A tới đỉnh H: A-B-D-F-H

Lí giải:

BướcĐỉnh đang xét (Rút khỏi Stack)Đỉnh kề có hướng chưa duyệt (Theo Alphabet)Đẩy vào Stack (Trái →\rightarrow Phải)Trạng thái Stack (Đỉnh Stack ở bên Phải)
0Khởi tạoA[A]
1ABB[B]
2BC, DC, D[C, D]
3DE, FE, F[C, E, F]
4FG, HG, H[C, E, G, H]
5HĐã tới đíchThuật toán dừng

(d) Giả sử mỗi lối đi trong mê cung gây ra một lượng sát thương khác nhau cho bạn trong trò chơi. Đồ thị được bổ sung thêm các trọng số để biểu diễn sát thương gây ra bởi mỗi cạnh. Sử dụng thuật toán Dijkstra để tìm đường đi từ đỉnh A đến đỉnh H trong đồ thị G3 (Hình 4) với sát thương thấp nhất có thể. Hãy ghi lại thứ tự các đỉnh được loại bỏ khỏi hàng đợi ưu tiên (priority queue) khi chạy thuật toán Dijkstra.

Hình 4: Đồ thị có hướng G3 có trọng số

Bài làm tham khảo

Thứ tự các đỉnh: A-B-D-C-F-E-G-H

Lí giải:

Bước. Đỉnh đang xét (Rút khỏi PQ)Các đỉnh kề và Sát thương tích lũyXử lý Relaxation (Cập nhật/Bỏ qua)Trạng thái PQ (Sắp xếp Min →\rightarrow Max)
0. Khởi tạod[A]=0d[A] = 0[(0, A)]
1. AB (0 + 1 = 1)Cập nhật B[(1, B)]
2. BD (1 + 2 = 3)
C (1 + 3 = 4)		Cập nhật D
Cập nhật C		[(3, D), (4, C)]
3. DF (3 + 2 = 5)
E (3 + 3 = 6)		Cập nhật F
Cập nhật E		[(4, C), (5, F), (6, E)]
4. CA (4 + 1 = 5)
D (4 + 1 = 5)		Bỏ qua A (đã xét)
Bỏ qua D (5 > 3)		[(5, F), (6, E)]
5. FH (5 + 3 = 8)
G (5 + 4 = 9)		Cập nhật H
Cập nhật G		[(6, E), (8, H), (9, G)]
6. EG (6 + 1 = 7)Cập nhật G (7 < 9)[(7, G), (8, H)]
7. GH (7 + 1 = 8)Bỏ qua H (8 không nhỏ hơn 8)[(8, H)]
8. HĐã tới đíchThuật toán dừng

PHẦN 2: TỰ LUẬN (4 điểm)

Câu 7 (1.5 điểm) Hãy khai báo kiểu dữ liệu danh sách liên kết đơn mà mỗi phần tử chứa thông tin về một quốc gia gồm tên quốc gia, dân số, diện tích. Với các kiểu dữ liệu vừa khai báo, hãy xây dựng các hàm sau:

(a) Hàm nhập danh sách các quốc gia bằng cách thêm từng quốc gia vào đầu danh sách.

(b) Hàm sắp xếp danh sách các quốc gia theo tên quốc gia dùng thuật toán Selection Sort.

Bài làm tham khảo

(a)

struct QuocGia {
    string ten_quoc_gia;
    int dan_so;
    double dien_tich;
};

struct Node {
    QuocGia du_lieu;
    Node* tiep_theo;
};


struct List {
    Node* pHead;
    Node* pTail;
};

void EmptyList(List& L) 
{
    L.pHead = nullptr;
    L.pTail = nullptr;
}
void Nhap(QuocGia& qg)
{
    getline(cin,qg.ten_quoc_gia);
    cin >> qg.dan_so;
    cin >> qg.dien_tich;
    cin.ignore();
}
Node* CreateNode(QuocGia qg) 
{
    Node* node = new Node();
    node->du_lieu = qg;
    node->tiep_theo = nullptr;
    return node;
}
void AddHead(List& L, QuocGia qg)
{
    Node* newNode = CreateNode(qg);
    if (L.pHead == nullptr) 
    {
        L.pHead = newNode;
        L.pTail = newNode; 
    } 
    else 
    {
        newNode->tiep_theo = L.pHead; 
        L.pHead = newNode;            
    }
}

(b)

void SelectionSort(List& L) 
{
    if (L.pHead == nullptr) return; 

    for (Node* p = L.pHead; p != nullptr; p = p->tiep_theo) 
    {
        for (Node* q = p->tiep_theo; q != nullptr; q = q->tiep_theo) 
        {
            if (q->du_lieu.ten_quoc_gia < p->du_lieu.ten_quoc_gia) 
            {
                QuocGia temp = p->du_lieu;
                p->du_lieu = q->du_lieu;
                q->du_lieu = temp;
            }
        }
    }
}

Câu 8 (2.5 điểm)

Cho bài toán "Tô màu bản đồ" được đặt ra như sau: Có một bản đồ các quốc gia trên thế giới, ta muốn tô màu các quốc gia này sao cho hai nước có cùng ranh giới được tô khác màu nhau. Yêu cầu tìm cách tô sao cho số màu sử dụng là ít nhất (Hình 5).

Hình 5: Ví dụ về một bản đồ

Hãy thực hiện các yêu cầu sau:

(a) Xác định thông tin đầu vào (input), thông tin đầu ra (output) của bài toán.

(b) Hãy mô hình hóa bài toán trên thành một bài toán trên đồ thị, tức cho biết đỉnh và cạnh của đồ thị biểu diễn thông tin gì, đồ thị có trọng số hay không, yêu cầu xử lý gì với đồ thị đó.

(c) Xây dựng các cấu trúc dữ liệu phù hợp nhất có thể để biểu diễn đồ thị trên máy tính theo input đã cho ở Câu a. Cấu trúc được xem là tốt nếu đạt được các tiêu chuẩn sau: Tiết kiệm tài nguyên; Hỗ trợ một số thao tác cơ bản như "Kiểm tra hai đỉnh có kề nhau không", "Tìm danh sách các đỉnh kề với một đỉnh cho trước" với ràng buộc là không phải duyệt qua danh sách tất cả các cạnh của đồ thị.

(d) Giả sử chương trình đã có sẵn các hàm hỗ trợ nhập thông tin đầu vào và xuất thông tin đầu ra theo cấu trúc dữ liệu ở Câu c, cùng với các chỉ thị #include cần thiết.

Hãy cài đặt một (hoặc một số) hàm cho biết tên của quốc gia có đường biên giới chung với nhiều quốc gia khác nhất trong bản đồ.

Sinh viên được phép sử dụng Standard Template Library-STL với những cấu trúc dữ liệu (vector, stack, queue, list, map, set, pair, ...) cũng như giải thuật được xây dựng sẵn.

Bài làm tham khảo

(a) Thông tin đầu vào: Số quốc gia, các quốc gia giáp ranh nhau, tên các quốc gia. Thông tin đầu ra: Đưa ra phương án tô màu.

(b) Mô hình hóa:

  • Quốc gia tương ứng các đỉnh.
  • Ranh giới giáp với nhau tương ứng: cạnh nối 2 đỉnh.
  • Đồ thị không có trọng số.
  • Các màu là các số.
  • Yêu cầu: không cho 2 đỉnh kề nhau có số giống nhau.

(c)

struct NodeKe 
{
    string quoc_gia;
    NodeKe* tiep_theo;
};

struct NodeDinh 
{
    string quoc_gia;
    NodeKe* dau_danh_sach_ke;
    NodeDinh* tiep_theo;
};

struct DoThi 
{
    NodeDinh* pDau;
};

(d)

int DemSoNutKe(NodeKe* pDauKe)
{
    int count = 0;
    while (pDauKe != NULL)
    {
        count++;
        pDauKe = pDauKe->tiep_theo;
    }
    return count;
}

string QuocGiaNhieuBienGioiNhat(DoThi G)
{
    if (G.pDau == NULL) return "";

    string ten_quoc_gia = "";
    int maxBienGioi = -1;

    NodeDinh* p = G.pDau;
    while (p != NULL)
    {
        int soBienGioi = DemSoNutKe(p->dau_danh_sach_ke);
        if (soBienGioi > maxBienGioi)
        {
            maxBienGioi = soBienGioi;
            ten_quoc_gia = p->quoc_gia;
        }
        p = p->tiep_theo;
    }
    return ten_quoc_gia;
}