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

Deque (hàng đợi hai đầu) là gì?

1. AMột cấu trúc cho phép chèn và xóa ở cả hai đầu
2. BMột hàng đợi chỉ cho phép xóa ở cuối
3. CHai hàng đợi riêng biệt dùng chung một mảng
4. DMột hàng đợi được sắp theo ưu tiên

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

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

Trong một cây, các nút anh em (sibling) là gì?

1. ACác nút không có con
2. BCác nút có chung một nút cha
3. CMột nút và cha của nó
4. DCác nút cùng độ sâu ở những cây con khác nhau

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. AXâu chuỗi riêng (separate chaining)
2. BDò tuyến tính
3. CBăm kép
4. DDò bậc hai

Các khóa 50, 30, 70, 20, 40 được chèn theo thứ tự này vào một cây tìm kiếm nhị phân rỗng. Con trái của 30 là gì?

1. A40
2. B70
3. C50
4. D20

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

Độ 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(n log n)
2. BO(log n)
3. CO(1)
4. DO(n)

Chèn một khóa vào cây AVL làm cây con trái của một nút quá cao, và khóa mới đi vào cây con trái của con trái của nó (trường hợp trái-trái). Cách sửa nào được áp dụng?

1. ATô lại màu nút và con của nó
2. BMột phép xoay phải đơn tại nút mất cân bằng
3. CMột phép xoay trái đơn tại nút mất cân bằng
4. DXoay trái tại nút con, rồi xoay phải tại nút