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

Ánh xạ (map, từ điển) lưu gì?

1. ACác giá trị sắp theo kích thước
2. BCác cặp khóa bằng nhau
3. CCác cặp khóa-giá trị với khóa duy nhất
4. DChỉ các giá trị theo thứ tự chèn

Bảng băm lưu dữ liệu dưới dạng:

1. AChỉ một danh sách đã sắp xếp
2. BMột cây có khóa được sắp thứ tự
3. CCác cặp khóa–giá trị được định vị bằng hàm băm
4. DMột chuỗi có độ dài cố định

Một mạng lưới đường có 100,000 giao lộ, mỗi giao lộ nối với khoảng 4 giao lộ khác. Cách biểu diễn nào phù hợp nhất?

1. ADanh sách kề
2. BMa trận kề
3. CMột đống nhị phân các cạnh
4. DMột mảng đỉnh đã sắp xếp đơn lẻ

Thuật toán Dijkstra dùng kiểu dữ liệu trừu tượng nào để chọn đỉnh kế tiếp cần xử lý?

1. AMột tập không có thứ tự
2. BHàng đợi ưu tiên min
3. CHàng đợi FIFO
4. DNgăn xếp

Cây nhị phân hoàn hảo có chiều cao h, với chiều cao tính bằng cạnh, có bao nhiêu nút?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

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. AChèn phần tử vào vị trí bất kỳ
2. BTìm trung vị trong O(1)
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

Các quy tắc cây đỏ-đen đảm bảo điều gì về chiều cao của cây có n khóa?

1. AChiều cao tối đa là log₂ n + 1
2. BChiều cao tối đa là n / 2
3. CChiều cao tối đa là 2 log₂(n + 1)
4. DChiều cao chính xác là log₂ n