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?

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:

Đáp án đúng: B

Phương pháp sắp xếp nổi bọt (Bubble Sort) hoạt động bằng cách lặp đi lặp lại duyệt qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Các phần tử lớn hơn "nổi" lên cuối danh sách (vị trí đúng của chúng) sau mỗi lần duyệt. Phương án 2 mô tả chính xác quá trình này: "Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên".

Câu 31:

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

Lời giải:

Đáp án đúng: B

Phương pháp sắp xếp chèn (Insertion Sort) hoạt động bằng cách duyệt qua danh sách, tại mỗi bước, nó 'chèn' phần tử hiện tại vào đúng vị trí của nó trong phần đã được sắp xếp của danh sách. Điều này được thực hiện bằng cách so sánh phần tử hiện tại với các phần tử trong phần đã sắp xếp và 'đẩy' các phần tử lớn hơn sang phải để tạo khoảng trống cho phần tử hiện tại. Do đó, đáp án chính xác là: "Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống". Các phương án còn lại mô tả các thuật toán sắp xếp khác (ví dụ: trộn, chọn, nổi bọt).

Câu 32:

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con phải là gì trong các phương án sau?

Lời giải:

Đáp án đúng: A

Khi lưu trữ cây nhị phân dưới dạng mảng, quy tắc chung là: nếu nút cha nằm ở vị trí `i` (bắt đầu từ 0), thì nút con trái sẽ ở vị trí `2*i + 1` và nút con phải ở vị trí `2*i + 2`. Vì vậy, phương án đúng phải là `2*i + 1` (nút con trái).

Câu 33:

Giải thuật đệ quy là:

Lời giải: