Hãy cho biết tính chất nào sau đây là của cây nhị phân tìm kiếm?

Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con

Là cây nhị phân đầy đủ

Cây nhị phân thoả tính chất heap

Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha nhỏ hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phải của nó

Trả lời:

Đáp án đúng: D

Cây nhị phân tìm kiếm (Binary Search Tree - BST) là một cấu trúc dữ liệu cây nhị phân, trong đó mỗi nút có một khóa (giá trị) và thỏa mãn các tính chất sau: 1. Khóa của mọi nút trong cây con trái của một nút đều nhỏ hơn khóa của nút đó. 2. Khóa của mọi nút trong cây con phải của một nút đều lớn hơn khóa của nút đó. 3. Cây con trái và cây con phải cũng là cây nhị phân tìm kiếm. Như vậy, phương án 4 mô tả đúng tính chất của cây nhị phân tìm kiếm. Các phương án còn lại mô tả các tính chất của các cấu trúc dữ liệu khác (ví dụ: heap, cây đầy đủ) hoặc mô tả sai tính chất của cây nhị phân tìm kiếm.

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

Đề 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.

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 26:

Ưu điểm của việc cài đặt danh sách bằng mảng:

Lời giải:

Đáp án đúng: C

Câu hỏi này kiểm tra kiến thức về ưu điểm của việc cài đặt danh sách bằng mảng. Trong các phương án đưa ra, phương án 3 mô tả chính xác ưu điểm nổi bật của mảng: truy cập phần tử trực tiếp thông qua chỉ số, giúp tốc độ truy cập nhanh và đồng đều. Các phương án khác không đúng vì mảng có kích thước cố định (không thay đổi số lượng phần tử tùy ý) và việc bổ sung/xóa phần tử trong mảng thường tốn kém (phải dịch chuyển các phần tử khác).

Câu 27:

Định nghĩa danh sách tuyến tính Hàng đợi (Queue):

Lời giải:

Đáp án đúng: C

Hàng đợi (Queue) là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc FIFO (First In, First Out) - vào trước ra trước. Điều này có nghĩa là phần tử nào được thêm vào hàng đợi trước thì sẽ được lấy ra khỏi hàng đợi trước. Phép bổ sung phần tử được thực hiện ở cuối hàng đợi (lối sau/rear), và phép loại bỏ phần tử được thực hiện ở đầu hàng đợi (lối trước/front).

Phương án 1 sai vì nói phép loại bỏ không thực hiện được.
Phương án 2 sai vì nói phép bổ sung và loại bỏ thực hiện ở vị trí bất kì.
Phương án 4 sai vì mô tả hàng đợi giống như ngăn xếp (Stack).
Phương án 3 đúng vì mô tả chính xác cách hoạt động của hàng đợi.

Câu 28:

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ứ hai là:

Lời giải:

Đáp án đúng: B

Giải thuật sắp xếp chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của dãy và hoán đổi nó với phần tử đầu tiên của phần chưa được sắp xếp đó.

Ở lần lặp đầu tiên, phần tử nhỏ nhất là 0, được hoán đổi với 6, kết quả là {0 1 3 6 5 7 9 2 8 4}.

Ở lần lặp thứ hai, ta tìm phần tử nhỏ nhất trong phần còn lại của dãy (từ vị trí thứ 2 trở đi: {1 3 6 5 7 9 2 8 4}). Phần tử nhỏ nhất là 2, nằm ở vị trí thứ 8. Ta hoán đổi 2 với phần tử ở vị trí thứ 2 (là 1), được kết quả là {0 1 2 6 5 7 9 3 8 4}.

Vậy, đáp án đúng là {0 1 2 6 5 7 9 3 8 4}.

Câu 29:

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

Lời giải:

Đáp án đúng: B

Sau lần lặp đầu tiên, pivot là 3 và dãy được chia thành (0 1 2) 3 (5 4 8 6 9 7).

Lần lặp thứ hai, ta chọn pivot cho (0 1 2) và (5 4 8 6 9 7). Chọn 1 làm pivot cho (0 1 2) và 6 làm pivot cho (5 4 8 6 9 7). Kết quả: (0) 1 (2) 3 (5 4) 6 (8 9 7).

Lần lặp thứ ba, chọn pivot cho (5 4), (8 9 7). Chọn 4 làm pivot cho (5 4) và 8 làm pivot cho (8 9 7). Kết quả: (0) 1 (2) 3 (4) 6 (5) 8 (9 7).

Lần lặp thứ tư, chọn pivot cho (9 7). Chọn 7 làm pivot cho (9 7). Kết quả: (0) 1 (2) 3 (4) 6 (5) 8 (7) 9.

Dựa vào quá trình này, sau lần lặp thứ nhất ta có {(0 1 2) 3 (5 4 8 6 9 7)}. Sau lần lặp thứ hai chúng ta có: (0) 1 (2) 3 (5 4) 6 (8 9 7). Sau lần lặp thứ ba chúng ta có (0) 1 (2) 3 (4) 5 6 (8 9 7). Tuy nhiên, câu hỏi yêu cầu kết quả sau lần lặp thứ tư, và không có đáp án nào phù hợp với kết quả (0) 1 (2) 3 (4) 6 (5) 8 (9 7) hoặc (0) 1 (2) 3 (4) 5 6 (7) 8 (9). Do đó không có đáp án đúng trong các lựa chọn đã cho.

Câu 30:

Cho dãy số sau: 10 11 14 32 36 43 55 57 87 97 . Áp dụng phương pháp tìm kiếm nhị phân, sau bao nhiêu lần phân đoạn ta sẽ tìm thấy số 43?

Lời giải:

Đáp án đúng: B

Để tìm số 43 bằng phương pháp tìm kiếm nhị phân trong dãy số đã cho, ta thực hiện các bước sau:

1. Lần 1:
- Dãy số: 10 11 14 32 36 43 55 57 87 97
- Tìm phần tử ở giữa: (10 + 97) / 2 ≈ 53.5. Vị trí giữa là (0+9)/2 = 4 (làm tròn xuống). Phần tử ở vị trí 4 là 36.
- So sánh 43 với 36. Vì 43 > 36, ta loại bỏ nửa đầu của dãy (từ 10 đến 36).
- Dãy còn lại: 43 55 57 87 97

2. Lần 2:
- Dãy số: 43 55 57 87 97
- Tìm phần tử ở giữa: (43 + 97) / 2 = 70. Vị trí giữa là (0+4)/2 = 2. Phần tử ở vị trí 2 là 57.
- So sánh 43 với 57. Vì 43 < 57, ta loại bỏ nửa sau của dãy (từ 57 đến 97).
- Dãy còn lại: 43 55

3. Lần 3:
- Dãy số: 43 55
- Tìm phần tử ở giữa: (43 + 55) / 2 = 49. Vị trí giữa là (0+1)/2 = 0. Phần tử ở vị trí 0 là 43.
- So sánh 43 với 43. Vì 43 = 43, ta tìm thấy số cần tìm.

Vậy, sau 3 lần phân đoạn, ta tìm thấy số 43.

Câu 31:

Các thuộc tính của một kiểu dữ liệu?

Lời giải: