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

Cấu trúc nào thường được dùng để cài đặt hàng đợi ưu tiên?

1. ADanh sách liên kết đơn không có thứ tự
2. BĐống (heap)
3. CMột chuỗi
4. DNgăn xếp

Trong một cây, lá là gì?

1. ANút không có cha
2. BNút có giá trị lớn nhất
3. CNút không có con
4. DNút có đúng một con

Đồ thị có hướng là gì?

1. AĐồ thị có các cạnh mang hướng từ đỉnh này sang đỉnh khác
2. BĐồ thị trong đó mọi cặp đỉnh phân biệt đều được nối bằng một cạnh
3. CĐồ thị có mọi cạnh đều có trọng số
4. DĐồ thị không có chu trình

Một cây nhị phân có gốc 1 với con trái 2 và con phải 3; nút 2 có các con 4 (trái) và 5 (phải). Duyệt thứ tự sau là gì?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

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

Cấu trúc dữ liệu nào được tìm kiếm theo chiều sâu (phiên bản lặp) sử dụng?

1. AĐống
2. BHàng đợi
3. CChỉ bảng băm
4. DNgăn xếp

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

Trong bộ đệm vòng, front == rear có thể nghĩa là rỗng hoặc đầy. Cách phổ biến để phân biệt là gì?

1. ALưu front và rear trong cùng một biến
2. BLàm kích thước bộ đệm là lũy thừa của hai
3. CLuôn xóa bộ đệm bất cứ khi nào front bằng rear, nên trạng thái là rỗng
4. DGiữ một bộ đếm phần tử riêng, hoặc luôn để trống một ô