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

Á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. AMột cây có khóa được sắp thứ tự
2. BChỉ một danh sách đã sắp xếp
3. CMột chuỗi có độ dài cố định
4. DCác cặp khóa–giá trị được định vị bằng hàm băm

Trong danh sách liên kết đơn, mỗi nút chứa:

1. ADữ liệu và một chỉ số
2. BDữ liệu và tham chiếu đến mọi nút khác
3. CDữ liệu và một tham chiếu đến nút kế tiếp
4. DChỉ dữ liệu

Chương trình đang chạy dùng cấu trúc dữ liệu nào để theo dõi các lời gọi hàm đang hoạt động và biến cục bộ của chúng?

1. ABảng băm các hàm
2. BHàng đợi bộ nhớ heap
3. CCây tìm kiếm nhị phân các khung
4. DNgăn xếp lời gọi (call stack)

Phương pháp xử lý va chạm nào lưu các khóa va chạm trong một danh sách ở cùng một ngăn?

1. ADò tuyến tính
2. BBăm kép
3. CDò bậc hai
4. DXâu chuỗi riêng (separate chaining)

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

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

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

Cây splay làm gì sau mỗi lần truy cập?

1. AXoay nút vừa truy cập lên gốc
2. BChuyển nút vừa truy cập xuống một lá
3. CXây lại toàn bộ cây ở dạng cân bằng
4. DTô lại màu các nút trên đường tìm kiếm