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

Cấu trúc dữ liệu nào hoạt động theo nguyên tắc "vào trước, ra trước"?

1. AĐống (heap)
2. BHàng đợi (queue)
3. CCây nhị phân
4. DNgăn xếp (stack)

Đặc điểm xác định của tập hợp (set) như một kiểu dữ liệu trừu tượng là gì?

1. ANó lưu các cặp khóa-giá trị
2. BNó lưu các phần tử không trùng lặp
3. CNó lưu các phần tử theo thứ tự đã sắp
4. DNó chỉ cho phép truy cập ở một đầu

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

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

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. A4 5 2 3 1
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D1 2 4 5 3

Giá trị của biểu thức hậu tố 3 4 + 2 * là bao nhiêu?

1. A11
2. B10
3. C24
4. D14

Tìm một từ có độ dài L trong trie với bảng chữ cái cố định mất bao lâu?

1. AO(log n), với n là số từ
2. BO(L × n)
3. CO(L), không phụ thuộc số từ được lưu
4. DO(n), với n là số từ

Mảng động nhân đôi khi đầy. Vì sao nhiều cách cài đặt chỉ thu nhỏ nó khi đầy một phần tư, không phải một nửa?

1. AVì chia đôi ở một nửa sẽ làm mất phần tử
2. BVì bộ cấp phát bộ nhớ chỉ có thể giải phóng bộ nhớ theo phần tư của một khối
3. CĐể giữ mảng được sắp xếp
4. DĐể tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới

Cấu trúc union-find (tập rời nhau) với hợp theo hạng và nén đường đi có chi phí khấu hao mỗi thao tác là:

1. AO(n)
2. BO(n²)
3. CO(α(n)), hàm Ackermann ngược, thực tế gần như hằng số
4. DChính xác O(log n)