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

Trong một cây, lá là gì?

1. ANút có giá trị lớn nhất
2. BNút không có con
3. CNút có đúng một con
4. DNút không có cha

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

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

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

Ma trận kề của một đồ thị có V đỉnh dùng bao nhiêu bộ nhớ?

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

Mục đích của nút lính canh (sentinel, nút giả) trong danh sách liên kết là gì?

1. ALưu số phần tử
2. BLàm cho danh sách được sắp xếp
3. CĐơn giản hóa mã bằng cách loại bỏ các trường hợp đặc biệt ở đầu hoặc cuối
4. DNgăn danh sách phát triển vượt quá một số nút tối đa cố định

Một ứng dụng cần tra cứu nhanh, đồng thời cần liệt kê khóa theo thứ tự đã sắp và trả lời các truy vấn khoảng. Cấu trúc nào phù hợp nhất?

1. ABảng băm
2. BCây tìm kiếm nhị phân cân bằng
3. CNgăn xếp
4. DDanh sách liên kết không sắp xếp

Thời gian chạy của tìm kiếm theo chiều rộng trên đồ thị có V đỉnh được lưu bằng ma trận kề là bao nhiêu?

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

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