Hãy cho biết phương pháp nào sau đây để loại bỏ nút X trên cây nhị phân tìm kiếm, với X là một phần tử bất kỳ?

Với dữ liệu đầu vào (n) đủ nhỏ, ta nên sử dụng phương pháp sắp xếp nào sau đây?

Lời giải:

Đáp án đúng: C

Với dữ liệu đầu vào nhỏ, các thuật toán sắp xếp đơn giản như sắp xếp lựa chọn (selection sort), sắp xếp chèn (insertion sort), hoặc sắp xếp nổi bọt (bubble sort) thường hiệu quả hơn so với các thuật toán phức tạp như sắp xếp nhanh (quick sort), sắp xếp vun đống (heap sort) hay sắp xếp trộn (merge sort). Điều này là do các thuật toán đơn giản có ít overhead hơn (ví dụ: ít gọi hàm đệ quy hơn, ít thao tác quản lý bộ nhớ hơn), và với kích thước nhỏ, sự khác biệt về độ phức tạp thuật toán (ví dụ: O(n^2) so với O(n log n)) không đáng kể. Trong các lựa chọn được đưa ra, sắp xếp lựa chọn là một thuật toán đơn giản, phù hợp với dữ liệu nhỏ.

Câu 26:

Hãy cho biết phát biểu nào đúng nhất về Giải thuật đệ quy?

Lời giải:

Đáp án đúng: C

Giải thuật đệ quy là giải thuật trong đó có lời gọi đến chính nó. Tuy nhiên, điều quan trọng là lời gọi này phải thực hiện trên một phạm vi nhỏ hơn của vấn đề gốc. Việc giảm phạm vi giúp giải thuật tiến dần đến trường hợp cơ sở (base case), là trường hợp có thể giải trực tiếp mà không cần đệ quy. Nếu không giảm phạm vi, giải thuật sẽ lặp vô hạn và gây ra lỗi tràn bộ nhớ (stack overflow). Vì vậy, phương án 'Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn' là đáp án chính xác nhất. Các đáp án khác không đầy đủ hoặc không chính xác.

Câu 27:

Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)). Theo qui tắc tổng xác định độ phức tạp tính toán của giải thuật thì thời gian thực hiện đoạn P1 rồi đến P2 là phương án nào sau đây?

Lời giải:

Đáp án đúng: B

Câu hỏi này kiểm tra kiến thức về quy tắc tổng trong phân tích độ phức tạp thuật toán. Quy tắc tổng nói rằng nếu một thuật toán thực hiện hai tác vụ liên tiếp, với độ phức tạp thời gian tương ứng là O(f(n)) và O(g(n)), thì độ phức tạp thời gian của toàn bộ thuật toán sẽ là O(max(f(n), g(n))). Điều này có nghĩa là độ phức tạp của toàn bộ thuật toán sẽ bị chi phối bởi độ phức tạp lớn hơn trong hai độ phức tạp thành phần.

Phương án 1: Sai. Min(f(n), g(n)) không phản ánh độ phức tạp lớn nhất, mà là độ phức tạp nhỏ nhất, không đúng với quy tắc tổng.

Phương án 2: Đúng. Max(f(n), g(n)) thể hiện độ phức tạp lớn nhất trong hai độ phức tạp, phù hợp với quy tắc tổng khi các giai đoạn thực hiện tuần tự.

Phương án 3: Sai. (f(n) or g(n)) không phải là ký hiệu chuẩn để biểu diễn độ phức tạp thuật toán.

Phương án 4: Sai. O(f(n) + g(n)) thường được viết là O(max(f(n), g(n))) để đơn giản hóa ký hiệu và nhấn mạnh vào tốc độ tăng trưởng chiếm ưu thế. Mặc dù không sai hoàn toàn nhưng không phải là cách biểu diễn tối ưu và thường dùng.

Câu 28:

Cho Stack gồm 5 phần tử {12, 5, 20, 23, 72}, trong đó 72 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 4 trong Stack ta phải thực hiện theo phương án nào?

Lời giải:

Đáp án đúng: B

Stack là cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In, First Out - Vào sau ra trước). Trong trường hợp này, stack ban đầu là {12, 5, 20, 23, 72} với 72 là đỉnh. Để lấy ra phần tử thứ 4 (tức là 5), ta cần loại bỏ các phần tử nằm trên nó.

1. POP(72): Loại bỏ phần tử 72 (đỉnh stack). Stack trở thành {12, 5, 20, 23}.
2. POP(23): Loại bỏ phần tử 23. Stack trở thành {12, 5, 20}.
3. POP(20): Loại bỏ phần tử 20. Stack trở thành {12, 5}.

Vậy, để lấy ra phần tử thứ tư (là 5) cần thực hiện POP(72), POP(23), POP(20). Tuy nhiên, không có đáp án nào chính xác là POP(72), POP(23), POP(20). Đáp án gần đúng nhất là POP(72), POP(23), PUSH(72) với ý nghĩa là sau khi lấy 2 phần tử trên đầu stack thì đẩy lại phần tử trên cùng vừa lấy ra vào. Dù vậy, đáp án này không chính xác hoàn toàn. Vì theo yêu cầu đề bài là lấy ra phần tử thứ 4.

Câu 29:

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chọn tăng dần (select sort)?

Lời giải:

Đáp án đúng: C

Phương pháp sắp xếp chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong dãy chưa được sắp xếp và đổi chỗ nó với phần tử đầu tiên của dãy chưa sắp xếp đó. Quá trình này lặp lại cho đến khi toàn bộ dãy được sắp xếp. Do đó, phương án "Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng" mô tả chính xác ý tưởng của thuật toán sắp xếp chọn tăng dần.

Câu 30:

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (bubble sort)?

Lời giải: