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

Đồ thị có trọng số là gì?

1. AĐồ thị có nhiều cạnh hơn đỉnh
2. BĐồ thị được lưu trên đĩa
3. CĐồ thị trong đó mỗi cạnh có một giá trị số như chi phí hoặc khoảng cách
4. DĐồ thị trong đó một số đỉnh nặng hơn các đỉnh khác vì có nhiều cạnh hơn

Duyệt thứ tự trước (preorder) của cây nhị phân thăm các nút theo thứ tự nào?

1. ANút, rồi cây con trái, rồi cây con phải
2. BCây con trái, rồi nút, rồi cây con phải
3. CTừng mức từ trên xuống
4. DCây con trái, rồi cây con phải, rồi nút

Hàm băm làm gì trong bảng băm?

1. AĐếm số khóa đang được lưu
2. BÁnh xạ một khóa tới một chỉ số trong bảng
3. CSắp xếp các khóa trong bảng
4. DMã hóa các giá trị trong bảng

Kiểm tra cạnh (u, v) có tồn tại hay không bằng ma trận kề mất bao lâu?

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

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

1. A1
2. B0,5
3. C2
4. DKhông có mức tối đa

Bạn có một tham chiếu đến một nút ở giữa danh sách. Trong danh sách nào bạn có thể xóa nó trong O(1)?

1. AMảng đã sắp xếp
2. BDanh sách liên kết đơn
3. CDanh sách liên kết đôi
4. DMảng động

Xóa một nút có hai con khỏi cây tìm kiếm nhị phân thường được thực hiện bằng cách:

1. AXây lại từ đầu cây con bên dưới nó và chèn lại mọi khóa mà nó chứa
2. BXóa cả cây con
3. CHoán đổi nó với gốc
4. DThay nó bằng nút kế tiếp theo thứ tự giữa (hoặc nút liền trước) rồi xóa nút đó

Độ phức tạp thời gian của decrease-key trong đống nhị phân (biết vị trí phần tử) là:

1. AO(n log n)
2. BO(log n)
3. CO(1)
4. DO(n)