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

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

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

Đồ thị có hướng là gì?

1. AĐồ thị trong đó mọi cặp đỉnh phân biệt đều được nối bằng một cạnh
2. BĐồ thị có mọi cạnh đều có trọng số
3. CĐồ thị không có chu trình
4. DĐồ thị có các cạnh mang hướng từ đỉnh này sang đỉnh khác

Thao tác peek (hoặc top) trên ngăn xếp làm gì?

1. ATrả về phần tử đỉnh mà không lấy nó ra
2. BLấy phần tử đỉnh ra và trả về nó
3. CXóa tất cả phần tử khỏi ngăn xếp
4. DTrả về phần tử đáy của ngăn xếp

Một hàng đợi được cài đặt bằng hai ngăn xếp: đẩy vào ngăn xếp "vào", và lấy ra từ ngăn xếp "ra", nạp lại từ "vào" khi nó rỗng. Chi phí khấu hao mỗi thao tác là bao nhiêu?

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

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. AMột mảng đỉnh đã sắp xếp đơn lẻ
2. BMa trận kề
3. CDanh sách kề
4. DMột đống nhị phân các cạnh

Cây nhị phân hoàn hảo có chiều cao h, với chiều cao tính bằng cạnh, có bao nhiêu nút?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

Trong bảng băm dùng địa chỉ mở, vì sao việc xóa thường được thực hiện bằng dấu "tombstone"?

1. ALàm trống ô có thể phá vỡ chuỗi dò của các khóa khác
2. BTombstone làm băm nhanh hơn
3. CCác khóa đã xóa phải được giữ mãi vì lý do bảo mật, nên các ô không bao giờ được tái sử dụng
4. DNó làm bảng được sắp xếp

Chi phí thời gian và không gian bổ sung của việc đảo ngược danh sách liên kết đơn tại chỗ là bao nhiêu?

1. AThời gian O(1) và không gian bổ sung O(1)
2. BThời gian O(n log n) và không gian bổ sung O(1)
3. CThời gian O(n) và không gian bổ sung O(n)
4. DThời gian O(n) và không gian bổ sung O(1)