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

Cấu trúc dữ liệu nào phù hợp nhất cho tính năng "hoàn tác" (undo) trong trình soạn thảo văn bản?

1. AHàng đợi (queue)
2. BĐồ thị
3. CTập băm
4. DNgăn xếp (stack)

Cấu trúc nào thường được dùng để cài đặt hàng đợi ưu tiên?

1. AĐống (heap)
2. BDanh sách liên kết đơn không có thứ tự
3. CNgăn xếp
4. DMột chuỗi

Trong bảng băm, va chạm (collision) là gì?

1. AHai khóa bằng nhau được lưu hai lần
2. BBảng hết bộ nhớ
3. CHai khóa khác nhau ánh xạ tới cùng một chỉ số
4. DMột khóa hoàn toàn không thể băm

Các khóa 50, 30, 70, 20, 40 được chèn theo thứ tự này vào một cây tìm kiếm nhị phân rỗng. Con trái của 30 là gì?

1. A50
2. B20
3. C70
4. D40

Cây AVL duy trì điều kiện cân bằng nào tại mọi nút?

1. AMọi lá ở cùng một độ sâu chính xác
2. BChiều cao của cây con trái và phải chênh lệch tối đa 1
3. CCả hai cây con của mọi nút chứa đúng cùng số nút
4. DMỗi nút được tô đỏ hoặc đen

Danh sách kề dùng bao nhiêu bộ nhớ cho đồ thị có V đỉnh và E cạnh?

1. AO(V²)
2. BO(E²)
3. CO(V × E)
4. DO(V + E)

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)
3. CO(n²)
4. DO(α(n)), hàm Ackermann ngược, thực tế gần như hằng số

Tìm một khóa tùy ý trong đống min nhị phân n phần tử mất bao lâu?

1. AO(log n)
2. BO(n)
3. CO(log log n)
4. DO(1)