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

Hàm băm làm gì trong bảng băm?

1. AMã hóa các giá trị trong bảng
2. BSắp xếp các khóa trong bảng
3. CĐếm số khóa đang được lưu
4. DÁnh xạ một khóa tới một chỉ số trong bảng

Đồ thị có trọng số là gì?

1. AĐồ thị được lưu trên đĩa
2. BĐồ thị trong đó mỗi cạnh có một giá trị số như chi phí hoặc khoảng cách
3. CĐồ thị có nhiều cạnh hơn đỉnh
4. DĐồ thị trong đó một số đỉnh nặng hơn các đỉnh khác vì có nhiều cạnh hơ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. BNgăn xếp (stack)
3. CĐồ thị
4. DTập băm

Cây AVL và cây đỏ-đen đảm bảo:

1. ATìm kiếm thời gian hằng số trong mọi trường hợp
2. BKhông nút nào có hai con
3. CCác khóa được lưu theo thứ tự chèn
4. DChiều cao O(log n) nhờ cân bằng lại

Độ phức tạp thời gian của việc tìm một khóa trong cây tìm kiếm nhị phân cân bằng là bao nhiêu?

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

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 trái của cây con phải
2. BLuôn là con phải của nó
3. CLuôn là cha của nó
4. DNút ngoài cùng bên phải của cây con trái

Các quy tắc cây đỏ-đen đảm bảo điều gì về chiều cao của cây có n khóa?

1. AChiều cao tối đa là 2 log₂(n + 1)
2. BChiều cao chính xác là log₂ n
3. CChiều cao tối đa là n / 2
4. DChiều cao tối đa là log₂ n + 1

Cấu trúc dữ liệu nào hỗ trợ bộ nhớ đệm LRU (ít được dùng gần đây nhất) với get và put O(1)?

1. AMột mảng đã sắp xếp đơn lẻ
2. BChỉ một ngăn xếp
3. CMột bảng băm kết hợp với danh sách liên kết đôi
4. DChỉ một cây tìm kiếm nhị phân