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

Tính chất đống max là gì?

1. AMọi lá đều chứa khóa lớn nhất
2. BKhóa của mỗi con trái lớn hơn hoặc bằng khóa của anh em bên phải của nó
3. CCác khóa được sắp từ trái sang phải
4. DKhóa của mỗi nút cha lớn hơn hoặc bằng khóa của các con

Ánh xạ (map, từ điển) lưu gì?

1. ACác giá trị sắp theo kích thước
2. BChỉ các giá trị theo thứ tự chèn
3. CCác cặp khóa-giá trị với khóa duy nhất
4. DCác cặp khóa bằng nhau

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
2. BHàng đợi ưu tiên
3. CNgăn xếp
4. DBảng băm

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

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

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ự sau là gì?

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

Một mạng lưới đường có 100,000 giao lộ, mỗi giao lộ nối với khoảng 4 giao lộ khác. Cách biểu diễn nào phù hợp nhất?

1. ADanh sách kề
2. BMa trận kề
3. CMột mảng đỉnh đã sắp xếp đơn lẻ
4. DMột đống nhị phân các cạnh

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 + E)
2. BO(V)
3. CO(E log V)
4. DO(V²)

Làm thế nào phát hiện danh sách liên kết đơn có chu trình hay không bằng O(1) bộ nhớ thêm?

1. ALưu mọi nút đã thăm trong một tập băm
2. BDi chuyển một con trỏ một bước và con trỏ kia hai bước rồi kiểm tra chúng có gặp nhau không
3. CSắp xếp danh sách và tìm phần tử trùng
4. DĐếm số nút cho đến khi số đếm vượt trường độ dài của danh sách