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

Deque (hàng đợi hai đầu) là gì?

1. AHai hàng đợi riêng biệt dùng chung một mảng
2. BMột hàng đợi được sắp theo ưu tiên
3. CMột hàng đợi chỉ cho phép xóa ở cuối
4. DMột cấu trúc cho phép chèn và xóa ở cả hai đầu

Thao tác hàng đợi lấy phần tử ở đầu ra có tên là gì?

1. AInsert
2. BDequeue
3. CPush
4. DEnqueue

Trong biểu diễn danh sách kề của đồ thị, mỗi đỉnh lưu gì?

1. ATổng số cạnh trong đồ thị
2. BDanh sách các đỉnh lân cận của nó
3. CĐường đi ngắn nhất đến mọi đỉnh khác
4. DMột hàng gồm V giá trị Boolean

Một bảng băm kích thước 7 dùng h(k) = k mod 7 và dò tuyến tính. Sau khi chèn 10, 17 được lưu ở đâu?

1. AChỉ số 3
2. BChỉ số 0
3. CChỉ số 4
4. DChỉ số 6

Một phần tử mới được chèn vào đống nhị phân như thế nào?

1. AXây lại toàn bộ đống từ đầu
2. BChèn nó vào vị trí đã sắp bằng cách dịch tất cả các phần tử lớn hơn sang phải một vị trí
3. CĐặt nó ở gốc và đẩy xuống
4. DĐặt nó ở cuối mảng và đẩy lên trong khi nó vi phạm tính chất đống

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. ANgăn xếp
2. BCây tìm kiếm nhị phân cân bằng
3. CDanh sách liên kết không sắp xếp
4. DBảng băm

Cây cơ số (radix tree, trie nén) cải thiện trie thông thường như thế nào?

1. ANó lưu mỗi từ trong một bảng băm ở gốc thay vì trong các nút riêng
2. BNó chỉ giữ chữ cái đầu của mỗi từ
3. CNó gộp các chuỗi nút một con thành một cạnh được gắn nhãn bằng một xâu
4. DNó sắp các con của mỗi nút theo tần suất

Với băm đồng nhất đơn giản, thời gian kỳ vọng của một lần tìm kiếm trong bảng băm xâu chuỗi, với n khóa và m ngăn, là bao nhiêu?

1. AO(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), với α = n / m