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

Trong đồ thị, chu trình là gì?

1. AMột đường đi thăm mọi đỉnh
2. BMột đường đi bắt đầu và kết thúc tại cùng một đỉnh
3. CMột cạnh có trọng số bằng không
4. DMột đỉnh không có cạnh

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 trái, rồi nút, rồi cây con phải
2. BNút, rồi cây con trái, 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. DCây con phải, rồi nút, rồi cây con trái

Hàm băm làm gì trong bảng băm?

1. AMã hóa các giá trị trong bảng
2. BĐếm số khóa đang được lưu
3. CÁnh xạ một khóa tới một chỉ số trong bảng
4. DSắp xếp các khóa trong bảng

Làm thế nào để tìm khóa nhỏ nhất trong cây tìm kiếm nhị phân?

1. AĐi theo các con trái từ gốc cho đến khi không còn con trái
2. BThăm mọi lá và so sánh chúng
3. CChỉ nhìn vào gốc
4. DĐi theo các con phải từ gốc cho đến khi không còn con phải

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. ANgăn xếp lời gọi (call stack)
2. BCây tìm kiếm nhị phân các khung
3. CHàng đợi bộ nhớ heap
4. DBảng băm các hàm

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ố 4
2. BChỉ số 0
3. CChỉ số 3
4. DChỉ số 6

Độ phức tạp thời gian của decrease-key trong đống nhị phân (biết vị trí phần tử) là:

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

Ư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. ANó lưu khóa không có thứ tự
2. BTìm kiếm kỳ vọng O(log n) nhờ dùng nhiều tầng con trỏ tiến
3. CTì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
4. DNó không dùng thêm bộ nhớ