Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc nào sau đây?

LILO(last in last out)

LIFO(last in first out)

FIFO( first in first out)

FOLO(fisrt out last out)

Trả lời:

Đáp án đúng: B

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc LIFO (Last In First Out), nghĩa là phần tử cuối cùng được thêm vào (Last In) sẽ là phần tử đầu tiên được lấy ra (First Out). Các thao tác chính trên ngăn xếp bao gồm push (thêm phần tử vào đỉnh) và pop (lấy phần tử từ đỉnh).

220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án - Phần 5

Đề cương ôn thi với 220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án được chọn lọc và chia sẻ dưới đây, nhằm giúp bạn sinh viên hệ thống kiến thức chuẩn bị cho kì thi sắp diễn ra.

20 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 13:

Hãy cho biết tư tưởng nào sau đây nói về của giải thuật tìm kiếm trên cây nhị phân tìm kiếm?

Lời giải:

Đáp án đúng: B

Tư tưởng của giải thuật tìm kiếm trên cây nhị phân tìm kiếm là tìm kiếm dựa vào cấu trúc cây. Nếu giá trị cần tìm nhỏ hơn nút gốc (nút hiện tại đang xét), thì tiếp tục tìm kiếm ở cây con bên trái. Ngược lại, nếu giá trị cần tìm lớn hơn nút gốc, thì tìm kiếm ở cây con bên phải. Quá trình này lặp lại cho đến khi tìm thấy giá trị cần tìm hoặc đến khi cây con rỗng (không tìm thấy). Các phương án khác mô tả các thuật toán tìm kiếm khác, ví dụ như tìm kiếm tuần tự hoặc tìm kiếm nhị phân trên mảng đã sắp xếp.

Câu 14:

Cho cây nhị phân: A B C D E F. Cho biết thứ tự các phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự trước?

Lời giải:

Đáp án đúng: C

Duyệt cây theo thứ tự trước (pre-order traversal) có thứ tự là: Nút gốc -> Cây con trái -> Cây con phải. Với cây đã cho, thứ tự duyệt sẽ là: A (nút gốc), B (cây con trái của A), D (cây con trái của B), E (cây con phải của B), C (cây con phải của A), F (cây con phải của C). Vì vậy, đáp án đúng là A, B, D, E, C, F.

Câu 15:

Khi lưu trữ cây nhị phân dưới dạng mảng, phần tử ở vị trí số 9 đóng vai trò gì trong các phương án sau?

Lời giải:

Đáp án đúng: A

Trong cách lưu trữ cây nhị phân bằng mảng, nếu một nút ở vị trí `i`, thì nút con trái của nó ở vị trí `2*i` và nút con phải của nó ở vị trí `2*i + 1`.

Để tìm nút cha của nút ở vị trí 9, ta thực hiện phép chia nguyên: `9 // 2 = 4`. Tuy nhiên, vì mảng thường bắt đầu từ vị trí 1 (chứ không phải 0), công thức chính xác hơn là (vị trí nút - 1) // 2 + 1. Trong trường hợp này, (9 - 1) // 2 + 1 = 8 // 2 + 1 = 4 + 1 = 5.

Vậy, nút ở vị trí 9 là con của nút ở vị trí 5.

Vì 9 là số lẻ, nên nó là con phải của nút cha của nó.

Do đó, nút ở vị trí 9 là nút con phải của nút ở vị trí 5.

Câu 16:

Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là nút gì trong các phương án sau?

Lời giải:

Đáp án đúng: A

Trong cây, cấp của một nút là số cạnh trên đường đi từ nút gốc đến nút đó. Do đó, nút có cấp bằng 0 chính là nút gốc của cây. Các nút lá là các nút không có nút con.

Câu 17:

Hàng đợi còn được gọi là danh sách kiểu:

Lời giải:

Đáp án đúng: B

Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo nguyên tắc "First In, First Out" (FIFO), nghĩa là phần tử nào được thêm vào trước sẽ được lấy ra trước. Các lựa chọn khác không đúng vì:
- LOLO không phải là thuật ngữ liên quan đến hàng đợi.
- FILO là viết tắt của "First In, Last Out", nguyên tắc hoạt động của ngăn xếp (stack), không phải hàng đợi.
- LIFO là viết tắt của "Last In, First Out", cũng là nguyên tắc hoạt động của ngăn xếp (stack), không phải hàng đợi.

Câu 18:

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ ba là:

Lời giải: