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. AXóa phần tử đầu
2. BĐọc phần tử đầu tiên
3. CTruy cập phần tử ở chỉ số i
4. DChèn vào đầu

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ùng độ sâu ở những cây con khác nhau
3. CCác nút có chung một nút cha
4. DMột nút và cha của nó

Trong đồ thị vô hướng, bậc của một đỉnh là gì?

1. AVị trí của nó trong danh sách kề
2. BSố đỉnh trong đồ thị
3. CĐộ dài đường đi dài nhất từ nó
4. DSố cạnh nối với nó

Bộ đệm vòng (circular buffer, ring buffer) thường được dùng để cài đặt:

1. AHàng đợi kích thước cố định
2. BCây tìm kiếm nhị phân
3. CPhép duyệt đồ thị
4. DHàm băm

Mục đích của nút lính canh (sentinel, nút giả) trong danh sách liên kết là gì?

1. ALàm cho danh sách được sắp xếp
2. BĐơn giản hóa mã bằng cách loại bỏ các trường hợp đặc biệt ở đầu hoặc cuối
3. CLưu số phần tử
4. DNgăn danh sách phát triển vượt quá một số nút tối đa cố định

Danh sách kề dùng bao nhiêu bộ nhớ cho đồ thị có V đỉnh và E cạnh?

1. AO(V × E)
2. BO(V²)
3. CO(V + E)
4. DO(E²)

Trong BST có gốc 50, cây con trái 30 (các con 20, 40) và cây con phải 70 (các con 60, 80), gốc bị xóa bằng nút kế tiếp theo thứ tự giữa. Khóa nào trở thành gốc mới?

1. A40
2. B60
3. C70
4. D80

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. ADi 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
2. BSắp xếp danh sách và tìm phần tử trùng
3. CĐếm số nút cho đến khi số đếm vượt trường độ dài của danh sách
4. DLưu mọi nút đã thăm trong một tập băm