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

Mỗi nút trong danh sách liên kết đôi chứa gì?

1. ADữ liệu, một con trỏ tới nút kế tiếp và một con trỏ tới nút trước
2. BHai bản sao dữ liệu và một con trỏ
3. CDữ liệu và hai con trỏ, một tới nút kế tiếp và một tới nút đứng sau nút đó
4. DDữ liệu và chỉ một con trỏ tới nút kế tiếp

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

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

Đặc điểm xác định của tập hợp (set) như một kiểu dữ liệu trừu tượng là gì?

1. ANó chỉ cho phép truy cập ở một đầu
2. BNó lưu các phần tử theo thứ tự đã sắp
3. CNó lưu các cặp khóa-giá trị
4. DNó lưu các phần tử không trùng lặp

Độ phức tạp thời gian của việc tìm một khóa trong cây tìm kiếm nhị phân cân bằng là bao nhiêu?

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

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(log n)
2. BO(1)
3. CO(n)
4. DO(n²)

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. ALuôn luôn thứ tự giảm dần
2. BThứ tự theo mức
3. CThứ tự tăng dần đã sắp xếp
4. DThứ tự chèn

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

1. ALưu các cạnh của đồ thị
2. BSắ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
3. CCài đặt ngăn xếp
4. DTrả lời các truy vấn khoảng (như tổng khoảng) và cập nhật trong O(log n)

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. ACá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
2. BLàm trống ô có thể phá vỡ chuỗi dò của các khóa khác
3. CTombstone làm băm nhanh hơn
4. DNó làm bảng được sắp xếp