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. AMã hóa các giá trị trong bảng
2. BĐếm số khóa đang được lưu
3. CSắp xếp các khóa trong bảng
4. DÁnh xạ một khóa tới một chỉ số trong bảng

Đồ thị gồm:

1. AChỉ khóa và giá trị băm
2. BChỉ một gốc và các lá
3. CHàng và cột
4. DCác đỉnh (nút) được nối bởi các cạnh

Gốc của một cây là gì?

1. ANút trên cùng không có nút cha
2. BBất kỳ nút nào ở giữa
3. CNút có giá trị lớn nhất
4. DNút không có con

Các khóa 50, 30, 70, 20, 40 được chèn theo thứ tự này vào một cây tìm kiếm nhị phân rỗng. Con trái của 30 là gì?

1. A20
2. B40
3. C70
4. D50

Duyệt thứ tự giữa (in-order) của cây tìm kiếm nhị phân thăm các khóa theo:

1. AThứ tự theo mức
2. BThứ tự chèn
3. CLuôn luôn thứ tự giảm dần
4. DThứ tự tăng dần đã sắp xếp

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

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

Vì sao không thể đơn giản xóa phần tử khỏi bộ lọc Bloom chuẩn bằng cách xóa các bit của chúng?

1. ABộ lọc Bloom lưu đầy đủ các phần tử, và chúng không thể được tìm lại sau khi đã băm
2. BCác bit trong bộ lọc Bloom không thể thay đổi sau khi tạo
3. CViệc xóa sẽ làm tỷ lệ dương tính giả tăng lên 100%
4. DCác bit đó có thể cũng thuộc về các phần tử khác, gây ra âm tính giả

Nếu không có hợp theo hạng hay nén đường đi, chi phí trường hợp xấu nhất của một lần find trong cấu trúc union-find với n phần tử là bao nhiêu?

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