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

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

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

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

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

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ố phần tử đang lưu chia cho số ngăn
3. CThời gian cần để tải bảng từ đĩa
4. DSố va chạm cho đến hiện tại

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)

Ma trận kề của một đồ thị có V đỉnh dùng bao nhiêu bộ nhớ?

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

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

1. AĐống không bao giờ chứa quá 100 phần tử
2. BMảng tự động giữ các khóa theo thứ tự đã sắp, nên không cần con trỏ
3. CNó 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
4. DMọi khóa trong đống đều bằng nhau

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. ACác bit trong bộ lọc Bloom không thể thay đổi sau khi tạo
2. BCác bit đó có thể cũng thuộc về các phần tử khác, gây ra âm tính giả
3. CBộ 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
4. DViệc xóa sẽ làm tỷ lệ dương tính giả tăng lên 100%

Cây đoạn (segment tree) thường được dùng để:

1. ALưu các cạnh của đồ thị
2. BTrả lời các truy vấn khoảng (như tổng khoảng) và cập nhật trong O(log n)
3. CCài đặt ngăn xếp
4. DSắp xếp chuỗi theo bảng chữ cái bằng cách lưu mỗi tiền tố trong một nút cây riêng