WorksheetsCTDLGT_T04(BST,AVLTree)
Total questions: 38
Worksheet time: 57mins
Cây tìm kiếm nhị phân (Binary Search Tree) là gì?
Cây mà mỗi nút có giá trị lớn hơn các nút con bên trái và nhỏ hơn các nút con bên phải
Cây mà mỗi nút có giá trị nhỏ hơn các nút con bên trái và lớn hơn các nút con bên phải
Cây mà mỗi nút có giá trị bằng nhau
Cây mà mỗi nút chỉ có một con
Chiều cao của cây (height of the tree) là gì?
Số nút trong cây
Số cạnh từ nút gốc đến nút lá xa nhất
Số nút từ gốc đến nút lá gần nhất
Số nút ở tầng cuối cùng
Cây nhị phân hoàn chỉnh (complete binary tree) là gì?
Cây mà tất cả các nút đều có đúng hai con
Cây mà tất cả các tầng đều đầy đủ trừ tầng cuối cùng
Cây mà tất cả các nút lá đều ở cùng một tầng
Cây mà tất cả các nút chỉ có một con
Khi chèn một giá trị vào cây tìm kiếm nhị phân, giá trị này sẽ được chèn vào đâu nếu nó nhỏ hơn giá trị của nút gốc?
Con bên trái của nút gốc
Con bên phải của nút gốc
Trên nút gốc
Không chèn được
Để xóa một nút có hai con trong cây tìm kiếm nhị phân, thao tác phổ biến nhất là gì?
Thay thế bằng nút lá trái cùng
Thay thế bằng nút lá phải cùng
Thay thế bằng nút có giá trị nhỏ nhất ở cây con bên phải
Thay thế bằng nút có giá trị lớn nhất ở cây con bên trái
Duyệt cây nhị phân theo thứ tự giữa (in-order) là gì?
Duyệt gốc, trái, phải
Duyệt trái, gốc, phải
Duyệt phải, trái, gốc
Duyệt trái, phải, gốc
Duyệt cây tìm kiếm nhị phân theo thứ tự nào sẽ trả về một danh sách có thứ tự tăng dần?
Pre-order
In-order
Post-order
Level-order
Có thể tìm kiếm phần tử nhỏ nhất trong cây nhị phân không? Nếu có, làm thế nào?
Có thể tìm kiếm phần tử nhỏ nhất trong cây nhị phân bằng cách đi theo hướng bên trái cho đến khi không còn nút con nào nữa.
Có thể tìm kiếm phần tử nhỏ nhất trong cây nhị phân bằng cách đi theo hướng bên phải
Có thể tìm kiếm phần tử nhỏ nhất trong cây nhị phân bằng cách sử dụng thuật toán tìm kiếm nhị phân
Không thể tìm kiếm phần tử nhỏ nhất trong cây nhị phân
Thứ tự nào sau đây cho phép duyệt đệ quy cây nhị phân theo thứ tự trước
Duyệt cây con trái theo thứ tự trước -> thăm gốc -> duyệt cây con phải theo thứ tự trước
Duyệt cây con trái theo thứ tự trước -> duyệt cây con phải theo thứ tự trước -> thăm gốc
Thăm gốc -> duyệt cây con trái theo thứ tự trước -> duyệt cây con phải theo thứ tự trước
Thăm gốc -> duyệt cây con phải theo thứ tự trước -> duyệt cây con trái theo thứ tự trước
Trong phép duyệt một cây nhị phân có 24 nút theo thứ tự sau, nút gốc có thứ tự duyệt thứ mấy ?
Thứ 1
Thứ 2
Thứ 23
Thứ 24
Nút có khóa nhỏ nhất trong cây nhị phân tìm kiếm khác rỗng là:
A. Nút gốc
A. Tất cả các nút
A. Nút con bên phải nhất
A. Nút con bên trái nhất
Thứ tự các nút được duyệt trong phép duyệt thứ tự TRƯỚC của cây này là gì?
A, B, C, D, E, F, G, H, I, J
E, B, A, C, D, G, F, I, H, J
A, D, C, B, F, H, J, I, G, E
B, A, C, D, G, F, I, H, J, E
Thứ tự các nút được duyệt trong phép duyệt sau của cây này là gì?
A, B, C, D, E, F, G, H, I, J
E, B, A, C, D, G, F, I, H, J
A, D, C, B, F, H, J, I, G, E
B, A, C, D, G, F, I, H, J, E
Khi duyệt cây này, biểu thức số học thu được là + ×ab ÷ cd. Đã thực hiện loại duyệt nào?
In-order
Pre-order
Post-order
Breadth-first
Đây có phải là Cây tìm kiếm nhị phân không?
Độ phức tạp là gì?
Yes, O(log(n))
No, O(n)
Yes, O(n)
No, O(log(n))
Trong các cây sau, cây nào là Cây tìm kiếm nhị phân?
Hình nào dưới đây biểu diễn cây tìm kiếm nhị phân của các giá trị sau: { 18, 6, 12, 22, 25, 30, 20, 2 }
Cho cây nhị phân có thứ tự duyệt là:
Duyệt theo thứ tự sau: 1 3 5 4 2
Duyệt theo thứ tự trong: 1 2 3 4 5
Kết quả duyệt theo thứ tự trước là?
Lưu ý: dãy số viết ngăn cách bởi khoảng trắng, ví dụ: 1 2 3 4 5
(a)
Kết quả duyệt theo thứ tự sau của cây?
9 8 4 2 3 5 1
4 9 8 5 2 3 1
8 9 4 2 3 5 1
8 9 4 3 2 5 1
Kết quả duyệt theo thứ tự trước của cây?
1 4 9 5 2 8 3
1 4 9 5 2 3 8
1 4 9 8 5 2 3
1 4 9 8 5 2 3
Duyệt theo thứ tự sau cho kết quả là:
1a+b*c+d*e+f*g
1abc*+de*f+g*+
++a*bc*+*defg
abc+*+defg*+*
Số lượng nút TỐI ĐA trong cây tìm kiếm nhị phân có chiều cao = 5 là bao nhiêu?
26-1
25-1
25
26
6
Số lượng nút TỐI THIỂU trong cây tìm kiếm nhị phân có chiều cao = 5 là bao nhiêu?
6
5
26-1
25-1
25
Khi nào cây AVL cần thực hiện xoay?
Khi cây bị mất cân bằng
Khi chèn phần tử vào
Khi xóa phần tử
Tất cả các đáp án trên
Thời gian trung bình để xóa một phần tử khỏi cây AVL là bao nhiêu?
O(n)
O(log n)
O(n^2)
O(1)
Phép xoay nào thực hiện trong cây AVL để cân bằng cây sau khi chèn một phần tử vào cây con phải của cây con trái?
a) Xoay phải
b) Xoay trái
c) Xoay trái kép
d) Xoay phải kép
Phép xoay nào thực hiện trong cây AVL để cân bằng cây sau khi chèn một phần tử vào cây con phải của cây con phải?
a) Xoay phải
b) Xoay trái
c) Xoay trái kép
d) Xoay phải kép
Trong cây AVL, khi chèn một phần tử có thể gây ra bao nhiêu lần xoay tối đa?
1
2
3
4
Phép xoay nào thực hiện trong cây AVL để cân bằng cây sau khi chèn một phần tử vào cây con trái của cây con phải?
a) Xoay phải
b) Xoay trái
c) Xoay trái kép
d) Xoay phải kép
Phép xoay nào thực hiện trong cây AVL để cân bằng cây sau khi chèn một phần tử vào cây con trái của cây con trái?
Xoay phải
Xoay trái
Xoay trái kép
Xoay phải kép
Trong cây AVL, chiều cao của một cây con bên trái là 3 và chiều cao của cây con bên phải là 1. Đây là tình huống gì?
a) Cân bằng
b) Mất cân bằng cần xoay phải
c) Mất cân bằng cần xoay trái
d) Không cần xoay
Cây AVL có thể được sử dụng trong ứng dụng nào sau đây?
a) Hệ thống cơ sở dữ liệu
b) Hệ thống tập tin
c) Trình biên dịch
d) Tất cả các ứng dụng trên
Thao tác xoay trái được sử dụng khi nào trong cây AVL?
Khi cây con phải cao hơn cây con trái
Khi cây con trái cao hơn cây con phải
Khi thêm một nút mới vào cây con phải của cây con phải
Khi thêm một nút mới vào cây con trái của cây con trái
Hệ số cân bằng của nút có giá trị 15 là bao nhiêu?
(a)
Hệ số cân bằng của nút có giá trị 345 là bao nhiêu?
(a)
Cây sau đây có phải là cây AVL không?
phải
không
Hệ số cân bằng của nút gốc là gì?
(a)
Cây này bị mất cân bằng. Chúng ta cần thực hiện bao nhiêu vòng quay để cây trở nên cân bằng?
(a)
