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. ANgăn xếp (stack)
2. BTập băm
3. CĐồ thị
4. DHàng đợi (queue)

Cấu trúc dữ liệu nào hoạt động theo nguyên tắc "vào trước, ra trước"?

1. ACây nhị phân
2. BHàng đợi (queue)
3. CNgăn xếp (stack)
4. DĐống (heap)

Sự khác biệt chính giữa mảng tĩnh và mảng động là gì?

1. AMảng động lưu các phần tử trong các nút liên kết để có thể tăng từng phần tử một
2. BMảng tĩnh cho phép truy cập chỉ số chậm hơn
3. CMảng động có thể tăng bằng cách chuyển sang một khối bộ nhớ lớn hơn
4. DMảng tĩnh chỉ có thể lưu số

Vì sao duyệt mảng thường nhanh hơn nhiều trong thực tế so với duyệt danh sách liên kết cùng độ dài?

1. ACác phần tử mảng liền kề, nên tận dụng tốt bộ nhớ đệm CPU
2. BDanh sách liên kết luôn lưu phần tử trên đĩa
3. CMảng dùng ít lệnh hơn để so sánh giá trị
4. DDuyệt mảng tổng cộng là O(1) còn duyệt danh sách liên kết là O(n)

Trong bảng băm dùng địa chỉ mở, hệ số tải tối đa có thể là bao nhiêu?

1. A0,5
2. BKhông có mức tối đa
3. C1
4. D2

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ự trước là gì?

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

Bộ lọc Bloom có thể trả lời "phần tử này có trong tập không?" với:

1. ACó thể có dương tính giả nhưng không có âm tính giả
2. BChỉ trả lời cho các số
3. CLuôn luôn chính xác
4. DCó thể có âm tính giả nhưng không có dương tính giả

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 đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối
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 mảng đã sắp xếp chứa tất cả n giá trị