Tin học · Lớp 12
7 câu · 11 phút · Ngân hàng đề TopStudy. Đáp án và lời giải do TopStudy biên soạn, mở ngay dưới từng câu.
Cho cây nhị phân như Hình 1. Hãy dùng mảng một chiều để biểu diễn các giá trị trong cây nhị phân.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Mảng một chiều để biểu diễn các giá trị trong cây nhị phân như sau:
[2, 24, 11, None, 3, 8, 9]
Cho cây nhị phân như Hình 4.
Kết quả thực hiện phép toán duyệt cây nhị phân như sau:
3
4
1
2
8
Phép toán duyệt cây nhị phân cho kết quả như bảng ở trên là phép toán nào?
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Cách biểu diễn các giá trị của cây bằng mảng một chiều theo ba phép duyệt:
a) Duyệt trước (Pre-order): Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải. [20,24,14,None,None,None,None,None,None,None,None]
b) Duyệt giữa (In-order): Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải. None,None,None,None]
c) Duyệt sau (Post-order): Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc. [None]
Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:
a) Duyệt trước: Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải.
[20,24,14,None,None,None,None,None,None,None,None]
b) Duyệt giữa: Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải.
[None,None,None,None]
c) Duyệt sau: Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc.
[None]
Cho các thao tác: (1) Duyệt nút gốc; (2) Duyệt cây con trái; (3) Duyệt cây con phải. Sắp xếp thứ tự các thao tác tương ứng với các phép toán duyệt cây nhị phân:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Cho các thao tác: (1) Duyệt nút gốc; (2) Duyệt cây con trái; (3) Duyệt cây con phải. Sắp xếp thứ tự các thao tác tương ứng với các phép toán duyệt cây nhị phân:
a) Duyệt trước:
Thao tác: Duyệt nút gốc -> Duyệt cây con trái -> Duyệt cây con phải
Thứ tự: (1) -> (2) -> (3)
b) Duyệt giữa:
Thao tác: Duyệt cây con trái -> Duyệt nút gốc -> Duyệt cây con phải
Thứ tự: (2) -> (1) -> (3)
c) Duyệt sau:
Thao tác: Duyệt cây con trái -> Duyệt cây con phải -> Duyệt nút gốc
Thứ tự: (2) -> (3) -> (1)
Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).
a) Xây dựng cây nhị phân với mảng số nguyên dương trên.
b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên
cây nhị phân được xây dựng ở câu a).
Cho mảng các số nguyên dương A = [9, 6, 5, 17, 10, 3, 8, 12].
a) Xây dựng cây nhị phân với mảng số nguyên dương trên.
b) Viết chương trình có sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để:
- Kiểm tra giá trị 10 có trong cây hay không?
- Kiểm tra giá trị 7 có trong cây hay không?
Tất cả đề Chuyên đề 2. Tìm hiểu cây tìm kiếm nhị phân trong sắp xếp và tìm kiếm · Các bộ sách Tin học Lớp 12