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

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

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

Các phần tử của mảng được lưu trong bộ nhớ như thế nào?

1. ARải rác, liên kết bằng con trỏ
2. BỞ các vị trí ngẫu nhiên do hàm băm chọn
3. CTrong một cây các trang bộ nhớ
4. DTrong một khối liên tục, nối tiếp nhau

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

1. ACác khóa được sắp từ trái sang phải
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. CMọi lá đều chứa khóa lớn nhất
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

Vì sao đống nhị phân có thể lưu trong mảng mà không cần con trỏ?

1. AMảng tự động giữ các khóa theo thứ tự đã sắp, nên không cần con trỏ
2. BMọi khóa trong đống đều bằng nhau
3. CĐống không bao giờ chứa quá 100 phần tử
4. DNó là cây nhị phân đầy đủ, nên các vị trí tuân theo công thức chỉ số đơn giản

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. B2
3. CKhông có mức tối đa
4. D0,5

Cây AVL duy trì điều kiện cân bằng nào tại mọi nút?

1. ACả hai cây con của mọi nút chứa đúng cùng số nút
2. BMọi lá ở cùng một độ sâu chính xác
3. CChiều cao của cây con trái và phải chênh lệch tối đa 1
4. DMỗi nút được tô đỏ hoặc đen

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. ADi 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
2. BLưu mọi nút đã thăm trong một tập băm
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

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