Phiếu bài tập Cấu trúc dữ liệu có đáp án

Gốc của một cây là gì?

1. ABất kỳ nút nào ở giữa
2. BNút trên cùng không có nút cha
3. CNút có giá trị lớn nhất
4. DNút không có con

Hệ số tải (load factor) của bảng băm là gì?

1. ASố phần tử đang lưu chia cho số ngăn
2. BSố ngăn chia cho độ dài trung bình của các khóa được lưu
3. CSố va chạm cho đến hiện tại
4. DThời gian cần để tải bảng từ đĩa

Đặc điểm xác định của tập hợp (set) như một kiểu dữ liệu trừu tượng là gì?

1. ANó lưu các phần tử theo thứ tự đã sắp
2. BNó chỉ cho phép truy cập ở một đầu
3. CNó lưu các phần tử không trùng lặp
4. DNó lưu các cặp khóa-giá trị

Một nút trong cây tìm kiếm nhị phân có cây con phải. Nút kế tiếp theo thứ tự giữa của nó nằm ở đâu?

1. ANút ngoài cùng bên phải của cây con trái
2. BNút ngoài cùng bên trái của cây con phải
3. CLuôn là cha của nó
4. DLuôn là con phải của nó

Một cây nhị phân có gốc 1 với con trái 2 và con phải 3; nút 2 có các con 4 (trái) và 5 (phải). Duyệt thứ tự sau là gì?

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D4 5 2 3 1

Cây nhị phân hoàn hảo có chiều cao h, với chiều cao tính bằng cạnh, có bao nhiêu nút?

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

Các khóa 5, 3, 8, 1 được chèn theo thứ tự này vào đống min nhị phân dùng mảng rỗng. Mảng cuối cùng là gì?

1. A[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 3, 5, 8]
4. D[1, 5, 8, 3]

Cấu trúc union-find (tập rời nhau) với hợp theo hạng và nén đường đi có chi phí khấu hao mỗi thao tác là:

1. AChính xác O(log n)
2. BO(α(n)), hàm Ackermann ngược, thực tế gần như hằng số
3. CO(n)
4. DO(n²)