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à nút con phải của nút có vị trí là 4

Là nút con trái của nút có vị trí là 5

Là nút con trái của nút có vị trí là 4

Là nút con phải của nút có vị trí là 5

Trả lờ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.

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 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:

Đáp án đúng: A

Giải thuật sắp xếp lựa 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ử ở vị trí đầu tiên của dãy chưa sắp xếp đó. Sau mỗi lần lặp, một phần tử sẽ được đưa về đúng vị trí của nó.

Sau lần lặp đầu tiên, dãy số là: {0 1 3 6 5 7 9 2 8 4}

- Lần lặp thứ hai: Tìm phần tử nhỏ nhất trong dãy {1 3 6 5 7 9 2 8 4}. Phần tử nhỏ nhất là 1, nó đã ở đúng vị trí nên không cần đổi chỗ. Dãy số vẫn là {0 1 3 6 5 7 9 2 8 4}

- Lần lặp thứ ba: Tìm phần tử nhỏ nhất trong dãy {3 6 5 7 9 2 8 4}. Phần tử nhỏ nhất là 2, đổi chỗ 2 với 3. Dãy số trở thành {0 1 2 6 5 7 9 3 8 4}

Câu 19:

Bước tổng quát của Phương pháp sắp xếp kiểu lựa chọn (selection sort):

Lời giải:

Đáp án đúng: a

Phương pháp sắp xếp kiểu lựa chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp của mảng và hoán đổi nó với phần tử đầu tiên của đoạn đó. Bước tổng quát của thuật toán này là chọn phần tử có khóa nhỏ nhất trong `n-i+1` phần tử từ `a[i]` đến `a[n]` và hoán vị nó với `a[i]`. Các phương án khác mô tả các thuật toán sắp xếp khác (ví dụ, phương án 1 liên quan đến sắp xếp chèn, phương án 2 liên quan đến sắp xếp nổi bọt).

Câu 20:

Dùng phương pháp lưu trữ liên tiếp để lưu trữ một ma trận ( mảng hai chiều) có nhược điểm lớn nhất là:

Lời giải:

Đáp án đúng: B

Phương pháp lưu trữ liên tiếp cho ma trận, đặc biệt là ma trận thưa (sparse matrix), có nhược điểm lớn nhất là lãng phí bộ nhớ. Ma trận thưa là ma trận mà phần lớn các phần tử có giá trị bằng 0. Khi lưu trữ liên tiếp, chúng ta vẫn phải cấp phát bộ nhớ cho tất cả các phần tử, kể cả các phần tử có giá trị 0, dẫn đến lãng phí không gian lưu trữ đáng kể.

Câu 1:

Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử:

Lời giải: