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. ANút có giá trị lớn nhất
2. BNút không có con
3. CBất kỳ nút nào ở giữa
4. DNút trên cùng không có nút cha

Cấu trúc dữ liệu nào được dùng để duyệt cây theo mức (level-order)?

1. AHàng đợi ưu tiên
2. BBảng băm
3. CHàng đợi
4. DNgăn xếp

Thao tác nào chậm trong mảng nhưng nhanh ở đầu danh sách liên kết?

1. ATìm độ dài của mảng cố định
2. BĐọc phần tử cuối theo chỉ số
3. CChèn vào đầu
4. DTruy cập phần tử thứ 5

Trong hàng đợi vòng lưu trong mảng có sức chứa n, vị trí kế tiếp sau chỉ số i được tính thế nào?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Trie (cây tiền tố) đặc biệt hiệu quả cho:

1. ATìm đường đi ngắn nhất
2. BTìm kiếm theo tiền tố như tự động hoàn thành
3. CLưu trữ ma trận
4. DSắp xếp các số

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

Bạn phải giữ k giá trị nhỏ nhất từ một luồng n số bằng bộ nhớ O(k). Cách nào chạy trong thời gian O(n log k)?

1. AMột mảng đã sắp xếp chứa tất cả n giá trị
2. BMột hàng đợi FIFO gồm k giá trị cuối
3. CMột đống max kích thước k, thay gốc của nó khi có giá trị nhỏ hơn đến
4. DMột đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối

Trong bảng băm dùng địa chỉ mở, vì sao việc xóa thường được thực hiện bằng dấu "tombstone"?

1. ALàm trống ô có thể phá vỡ chuỗi dò của các khóa khác
2. BCác khóa đã xóa phải được giữ mãi vì lý do bảo mật, nên các ô không bao giờ được tái sử dụng
3. CNó làm bảng được sắp xếp
4. DTombstone làm băm nhanh hơn