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

Thao tác nào là O(1) với mảng nhưng O(n) với danh sách liên kết đơn?

1. ATruy cập phần tử ở chỉ số i
2. BChèn vào đầu
3. CXóa phần tử đầu
4. DĐọc phần tử đầu tiên

Cấu trúc dữ liệu nào phù hợp nhất cho tính năng "hoàn tác" (undo) trong trình soạn thảo văn bản?

1. ATập băm
2. BHàng đợi (queue)
3. CNgăn xếp (stack)
4. DĐồ thị

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

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

Kiểm tra cạnh (u, v) có tồn tại hay không bằng ma trận kề mất bao lâu?

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

Trong đống nhị phân min lưu trong mảng (chỉ số bắt đầu từ 0), các con của nút ở chỉ số i nằm ở:

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

Làm thế nào phát hiện danh sách liên kết đơn có chu trình hay không bằng O(1) bộ nhớ thêm?

1. ALưu mọi nút đã thăm trong một tập băm
2. BĐếm số nút cho đến khi số đếm vượt trường độ dài của danh sách
3. CSắp xếp danh sách và tìm phần tử trùng
4. DDi chuyển một con trỏ một bước và con trỏ kia hai bước rồi kiểm tra chúng có gặp nhau không

Với băm đồng nhất đơn giản, thời gian kỳ vọng của một lần tìm kiếm trong bảng băm xâu chuỗi, với n khóa và m ngăn, là bao nhiêu?

1. AO(1 + α), với α = n / m
2. BO(n)
3. CO(m)
4. DO(log n)