Đề thi lý thuyết số 1

Câu 1 (0,5 điểm)

Xét độ phức tạp theo BigO, thuật toán tìm nhị phân tốt hơn thuật toán tìm tuyến tính, vì sao? (0,25đ)

Thuật toán tìm nhị phân với thứ tự tăng dần sẽ có kết quả tìm khóa 4 trong mảng gồm các khóa 1, 2, 3, 4, 5, 6, 7, 8, 9 sau bao nhiêu lần so sánh giá trị khóa? (0,25đ)

Bài làm tham khảo

Xét độ phức tạp theo BigO, thuật toán tìm kiếm nhị phân tốt hơn thuật toán tìm kiếm tuyến tính vì thuật toán tìm kiếm nhị phân có độ phức tạp là $O(\log n)$ , tốt hơn nhiều so với $O(n)$ của thuật toán tìm kiếm tuyến tính.

Thuật toán tìm kiếm nhị phân với thứ tự tăng dần sẽ có kết quả là khóa 4 trong mảng sau 4 lần.

Lần 1: left = 0; right = 8; mid = 4; $A[mid] = 5$ , vì $5 > 4$ nên giảm right = mid - 1;
Lần 2: left = 0; right = 3; mid = 1; $A[mid] = 2$ , vì $4 > 2$ nên tăng left = mid + 1;
Lần 3: left = 2; right = 3; mid = 2; $A[mid] = 3$ , vì $4 > 3$ nên tăng left = mid + 1;
Lần 4: left = 3; right = 3; mid = 3; $A[mid] = 4$ ; đã tìm thấy.

Câu 2 (0,5 điểm)

Nếu dùng thuật toán Insertion Sort (Chèn trực tiếp) để sắp xếp một dãy số tăng dần, thì khi hoàn thành việc sắp xếp mảng $A = \{3, 2, 4, 5, 1, 5\}$ , số lần dịch chuyển phần tử sang phải một vị trí là bao nhiêu?

Bài làm tham khảo

Số lần dịch chuyển phần tử sang phải một vị trí là 5 lần.

Lần 1: Vì $3 > 2$ hoán đổi 2 với 3, dịch phần tử sang phải 1 lần.
Lần 2: Vì $5 > 1$ hoán đổi 5 với 1, dịch phần tử sang phải thêm 1 lần.
Lần 3: Vì $4 > 1$ hoán đổi 4 với 1, dịch phần tử sang phải thêm 1 lần.
Lần 4: Vì $3 > 1$ hoán đổi 3 với 1, dịch phần tử sang phải thêm 1 lần.
Lần 5: Vì $2 > 1$ hoán đổi 2 với 1, dịch phần tử sang phải thêm 1 lần.

Câu 3 (0.5 điểm) Cho cây nhị phân T1 như Hình 1.

Cây nhị phân T1

Hình 1. Cây nhị phân T1

Hỏi khóa 7 xuất hiện ở vị trí thứ mấy (vị trí đầu tiên là 0) trong kết quả duyệt LNR?

Bài làm tham khảo

Kết quả duyệt: 3, 2, 4, 1, 5, 7, 8, 6

Khóa 7 xuất hiện ở vị trí số 5.

Câu 4 (0.5 điểm) Cho cây nhị phân T2 như Hình 2.

Cây nhị phân T2

Hình 2. Cây nhị phân T2

Hỏi mức nào trên cây T2 có tổng giá trị khóa cao nhất?

Bài làm tham khảo

Mức trên cây T2 có tổng giá trị khóa cao nhất là: Mức 2: 13 + 2 + 6 = 21.

Câu 5 (0.5 điểm) Cho B-Tree bậc 5, T3, như Hình 3.

B-Tree bậc 5 T3

Hình 3. B-Tree bậc 5 T3

Hãy vẽ cây T3 sau khi xóa khóa 6 (0.25đ)? Và cho biết tên thao tác đã điều chỉnh các nút trên T3 (0.25đ)?

Bài làm tham khảo

Lời giải thao tác trên B-Tree

Lí giải :

Số phần tử tối thiểu trong 1 node lá: $\lceil \frac{m}{2} \rceil - 1 = \lceil \frac{5}{2} \rceil - 1 = 3 - 1 = 2 \Rightarrow$ Số phần tử tối thiểu là 2.
Số phần tử tối đa trong 1 node lá: $m - 1 = 5 - 1 = 4$ .
Do đó khi xóa khóa 6 thì node phải chỉ còn 1 phần tử làm node phải trở thành node không hợp lệ. Ta có 2 phương án để giải quyết là mượn hoặc gộp. Thấy node trái có 4 phần tử, đạt tối đa số phần tử của 1 node hợp lệ, do đó phương án hợp lí nhất là mượn.
Để mượn phần tử thì theo nguyên tắc: khi mượn phải mượn phần tử lớn nhất bên trái hoặc nhỏ nhất bên phải. Đó là lí do ta chọn phần tử 4, là phần tử lớn nhất bên trái.
Sau khi mượn thành công thì ta đưa số 5 xuống node phải để hình thành node hợp lệ.
Thao tác trên được gọi là underflow.

Câu 6 (0.5 điểm) Cho B-Tree bậc 5, T4, như Hình 4. Biết thao tác tìm khóa trên một nút sử dụng thuật toán tìm tuyến tính.

B-Tree bậc 5 T4

Hình 4. B-Tree bậc 5 T4

Hỏi số lần so sánh giá trị khóa khi có kết quả tìm khóa 14 trên T4?

Bài làm tham khảo

Số lần so sánh giá trị khóa khi có kết quả tìm khóa 14 trên T4 là: 7 lần

Lí giải:

Khóa 14 so sánh với khóa 15 vì $14 < 15$ nên sẽ nhảy xuống nhánh trái: 1 lần.
Khóa 14 so sánh lần lượt với 3, 6, 9, 12: 4 lần.
Vì 14 lớn hơn 12 nên con trỏ sẽ trỏ tới nhánh chứa giá trị lớn hơn 12.
Khóa 14 so sánh lần lượt với 13, 14: 2 lần.
Tổng số lần là: 7

Đề bài bên dưới được sử dụng cho câu 7, câu 8, câu 9

Cho bảng băm địa chỉ mở $HT_1$ , kích thước $M = 11$ , hàm băm $f$ và hàm băm lại $f'$ lần lượt là:

$f(key) = key \% M$

$f'(key, i) = [f(key) + i^2] \% M$

Trong đó, phép toán $\%$ là phép toán lấy phần dư của phép chia nguyên.

Bảng băm HT₁

Chỉ số	0	1	2	3	4	5	6	7	8	9	10
Khóa	11	1			15	5				9

Câu 7 (0.5 điểm) Hỏi số lần so sánh giá trị khóa khi có kết quả tìm khóa 4 trên $HT_1$ ?

Câu 8 (0.5 điểm) Hỏi hệ số tải của $HT_1$ (lấy 2 số lẻ sau phần thập phân)?

Câu 9 (0.5 điểm) Hỏi vị trí khi thêm khóa 22?

Bài làm tham khảo

Câu 7. Số lần so sánh giá trị khóa khi có kết quả tìm khóa 4 trên $HT_1$ là 3 lần.

$f(key) = 4 \% 11 = 4$ .

Lần 1: $f'(4, 0) = [4 + 0^2] \% 11 = 4$ . Chỉ số 4 hiện tại có giá trị là 15, không phải khóa 4.
Lần 2: $f'(4, 1) = [4 + 1^2] \% 11 = 5$ . Chỉ số 5 hiện tại có giá trị là 5, không phải khóa 4.
Lần 3: $f'(4, 2) = [4 + 2^2] \% 11 = 8$ . Chỉ số 8 hiện tại là 1 ô trống $\Rightarrow$ Dừng.

Câu 8. Hệ số tải của $HT_1$ là $\lambda = \frac{5}{11} \approx 0,45$ .

Câu 9. Vị trí thêm khóa 22 là 3.

Lí giải:

$f(22) = 22 \% 11 = 0$ ; chỉ số 0 đã có khóa 11.
Tiến hành băm lại:
- $f'(22, 0) = [0 + 0^2] \% 11 = 0$ ; đã có 11.
- $f'(22, 1) = [0 + 1^2] \% 11 = 1$ ; đã có 1.
- $f'(22, 2) = [0 + 2^2] \% 11 = 4$ ; đã có 15.
- $f'(22, 3) = [0 + 3^2] \% 11 = 9$ ; đã có 9.
- $f'(22, 4) = [0 + 4^2] \% 11 = 16 \% 11 = 5$ ; đã có 5.
- $f'(22, 5) = [0 + 5^2] \% 11 = 25 \% 11 = 3$ ; ô trống $\Rightarrow$ chèn 22 vào vị trí 3.
Câu 10 Cho đồ thị vô hướng G như hình 5

Đồ thị vô hướng G

Hình 5. Đồ thị vô hướng G

Đỉnh	B	C	D	E	F	G	H
Độ dài đường đi ngắn nhất từ A

Bài làm tham khảo

Đỉnh	B	C	D	E	F	G	H
Độ dài đường đi ngắn nhất từ A	1	1	6	12	13	17	15

Câu hỏi Tự Luận

Giả sử các đoạn chương trình trong phần này đều có các chỉ thị #include, đảm bảo các kiểu dữ liệu và các hàm được C++ hỗ trợ đều sẵn sàng để sử dụng.

Câu 11 (2 điểm)

Cho các bản đồ thể hiện không quá 10000 giao lộ (ngã ba, ngã tư, ..). Mỗi giao lộ được đánh số từ 0 đến 9999. Các bản đồ này có thể biểu diễn theo đồ thị đơn, vô hướng và được biểu diễn trên máy tính bằng ma trận, với kiểu dữ liệu Bando như sau:

struct Bando
{
    int N;
    bool Duong[10000][10000];
}; 

1) Cài đặt hàm DemNgaNam để đếm số ngã năm trên bản đồ m (1đ):

2) Cài đặt hàm CoDuongdi trả về 1 nếu bản đồ m có đường đi từ giao lộ s đến giao lộ e, trả về 0 trong các trường hợp còn lại. Yêu cầu phải dùng queue thay cho hàm đệ quy (1đ):

Bài làm tham khảo

int DemNgaNam(Bando m)
{
    int nga_nam = 0;
    for(int i = 0; i < m.N; ++i)
    {
        int dem_giao_lo = 0;
        for(int j = 0; j < m.N; ++j)
        {
            if(m.Duong[i][j] == true)
            {
                dem_giao_lo++;
            }
        }
        
        if(dem_giao_lo == 5)
        {
            nga_nam++;
        }
    }
    return nga_nam;
}

int CoDuongdi(Bando m, int s, int e)
{
    vector<bool> di_qua(m.N, false);
    if(s == e) return 1;
    
    queue<int> q;
    q.push(s);
    di_qua[s] = true;
    
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        
        if(u == e) return 1;
        
        for(int j = 0; j < m.N; ++j)
        {
            if(m.Duong[u][j] == true && di_qua[j] == false)
            {
                q.push(j);
                di_qua[j] = true;
            }
        }
    }
    return 0;
}

Câu 12 (1 điểm)

Cho kiểu dữ liệu DblStack, là một stack chứa các giá trị double, và một hàm CreateDblItem được khai báo như bên dưới.

struct DblStack {
    double data;
    DblStack *next;
};

DblStack * CreateDblItem(double x) {
    DblStack* r = new DblStack;
    if (r == NULL) exit(1);
    r->data = x;
    r->next = NULL;
    return r;
};

Hãy cài đặt hàm push (0.5đ) và hàm pop (0.5đ) ở bên dưới, lần lượt để đưa một số double vào stack và xóa bỏ phần tử ở đỉnh stack.

Bài làm tham khảo

Hàm push:

void push(DblStack* &a, double x)
{
    DblStack* p = CreateDblItem(x);
    p->next = a;
    a = p;
}

Hàm pop:

void pop(DblStack* &a)
{
    if (a == NULL) return;
    DblStack* p = a;
    a = a->next;
    delete p;
}

Câu 13 (1 điểm)

Cho kiểu dữ liệu TREE, để biểu diễn cây nhị phân tìm kiếm, được khai báo như bên dưới. Hãy cài đặt hàm ChonKhoa để trả về một danh sách các khóa k trên cây nhị phân tìm kiếm sao cho $a < k < b$ , với a, b là các số cho trước. Yêu cầu dùng queue thay cho hàm đệ quy.

struct TNode {
    int key;
    TNode *left, *right;
};

typedef TNode *TREE;

Bài làm tham khảo

vector<int> ChonKhoa(TREE root, int a, int b)
{
    vector<int> ket_qua;
    if (root == NULL) return ket_qua;

    queue<TREE> q;
    q.push(root);

    while (!q.empty())
    {
        TREE u = q.front();
        q.pop();

        if (u->key > a && u->key < b)
        {
            ket_qua.push_back(u->key);
        }

        if (u->left != NULL && u->key > a)
        {
            q.push(u->left);
        }

        if (u->right != NULL && u->key < b)
        {
            q.push(u->right);
        }
    }
    return ket_qua;
}

Câu 14 (1 điểm)

Quỳnh được giao công việc cài đặt một hàm nhận một danh sách số nguyên và trả về một tập hợp số nguyên (các phần tử không trùng nhau). Các phần tử trong tập hợp được sắp thứ tự tăng dần.

Ví dụ: Input là 1, 5, 2, 7, 4, 1, 3, 2, 3, 5 thì output là 1, 2, 3, 4, 5, 7.

Quỳnh sử dụng hàm sort, có độ phức tạp $O(n \log n)$ , và cài đặt hàm ListToSet như sau:

vector<int> List2Set(vector<int> A) {
    
    vector<int> r;
    sort(A.begin(), A.end());
    r.push_back(A[0]);
    int i = 1;
    for(;i < A.size();++i)
    {
        if(r.back() != A[i])
        {
            r.push_back(A[i]);
        }
    }
    return r;
}

Bài làm tham khảo

vector<int> List2Set(vector<int> A) {
    
    vector<int> r;
    sort(A.begin(), A.end());
    r.push_back(A[0]);
    int i = 1;
    for(;i < A.size();++i)
    {
        if(r.back() != A[i])
        {
            r.push_back(A[i]);
        }
    }
    return r;
}

Bảng băm HT1​

Câu hỏi Tự Luận

Bảng băm HT₁