Phiếu bài tập Cấu trúc dữ liệu có đáp á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. BCác cặp khóa–giá trị được định vị bằng hàm băm
3. CMột chuỗi có độ dài cố định
4. DChỉ một danh sách đã sắp xếp

Duyệt thứ tự sau (postorder) của cây nhị phân thăm các nút theo thứ tự nào?

1. ACây con phải, rồi nút, rồi cây con trái
2. BCây con trái, rồi nút, rồi cây con phải
3. CCây con trái, rồi cây con phải, rồi nút
4. DNút, rồi cây con trái, rồi cây con phải

Thao tác nào chậm trong mảng nhưng nhanh ở đầu danh sách liên kết?

1. AChèn vào đầu
2. BĐọc phần tử cuối theo chỉ số
3. CTruy cập phần tử thứ 5
4. DTìm độ dài của mảng cố định

Mục đích của nút lính canh (sentinel, nút giả) trong danh sách liên kết là gì?

1. ANgăn danh sách phát triển vượt quá một số nút tối đa cố định
2. BLàm cho danh sách được sắp xếp
3. CĐơn giản hóa mã bằng cách loại bỏ các trường hợp đặc biệt ở đầu hoặc cuối
4. DLưu số phần tử

Một ứng dụng cần tra cứu nhanh, đồng thời cần liệt kê khóa theo thứ tự đã sắp và trả lời các truy vấn khoảng. Cấu trúc nào phù hợp nhất?

1. ACây tìm kiếm nhị phân cân bằng
2. BBảng băm
3. CNgăn xếp
4. DDanh sách liên kết không sắp xếp

Chi phí chèn một phần tử vào giữa mảng n phần tử là bao nhiêu?

1. AO(n), vì các phần tử phía sau phải dịch chuyển
2. BO(n²), vì mỗi phần tử di chuyển n lần
3. CO(1), vì đã biết chỉ số
4. DO(log n), nhờ tìm kiếm nhị phân

Với mỗi phần tử của mảng, bạn muốn tìm phần tử lớn hơn kế tiếp ở bên phải nó, trong tổng thời gian O(n). Cấu trúc nào giúp được?

1. AMột cây tìm kiếm nhị phân được xây lại cho mỗi phần tử
2. BMột bảng băm của mọi phần tử
3. CMột ngăn xếp giữ các phần tử đang chờ câu trả lời
4. DMột hàng đợi chứa mọi cặp phần tử

Ưu điểm chính của skip list so với danh sách liên kết đã sắp xếp là gì?

1. ATìm kiếm O(1) được đảm bảo vì mỗi nút lưu một con trỏ tới mọi nút khác
2. BTìm kiếm kỳ vọng O(log n) nhờ dùng nhiều tầng con trỏ tiến
3. CNó lưu khóa không có thứ tự
4. DNó không dùng thêm bộ nhớ