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. AHai bản sao dữ liệu và một con trỏ
2. BDữ liệu, một con trỏ tới nút kế tiếp và một con trỏ tới nút trước
3. CDữ liệu và chỉ một con trỏ tới nút kế tiếp
4. DDữ 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 đó

Cấu trúc nào thường được dùng để cài đặt hàng đợi ưu tiên?

1. ADanh sách liên kết đơn không có thứ tự
2. BNgăn xếp
3. CMột chuỗi
4. DĐống (heap)

Một cây có n nút thì có bao nhiêu cạnh?

1. A2n
2. Bn − 1
3. Cn
4. Dn + 1

Điều nào đúng với ma trận kề của một đồ thị vô hướng?

1. ANó luôn là ma trận tam giác trên
2. BNó đối xứng qua đường chéo chính
3. CĐường chéo chính của nó luôn chứa các số một
4. DMỗi hàng có đúng một số 1

Một bảng băm kích thước 7 dùng h(k) = k mod 7 và dò tuyến tính. Sau khi chèn 10, 17 được lưu ở đâu?

1. AChỉ số 6
2. BChỉ số 3
3. CChỉ số 4
4. DChỉ số 0

Điều gì xảy ra khi bảng băm băm lại (rehash) sau khi hệ số tải vượt ngưỡng?

1. AMột bảng lớn hơn được cấp phát và mọi khóa được chèn lại
2. BCác khóa hiện có được sắp xếp tại chỗ
3. CChỉ các khóa va chạm được chuyển sang một danh sách tràn mới ở cuối bảng
4. DCác khóa cũ nhất bị xóa để lấy chỗ

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

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

Cây Fenwick (cây chỉ mục nhị phân) trên một mảng n số hỗ trợ những thao tác nào trong O(log n)?

1. ATìm trung vị trong O(1)
2. BChèn phần tử vào vị trí bất kỳ
3. CTruy vấn tổng tiền tố và cập nhật một phần tử
4. DSắp xếp mảng và tìm kiếm nhị phân