Đề thi, bài tập trắc nghiệm online Cấu trúc dữ liệu và giải thuật – Đề 8

1. Trong bảng băm, phương pháp 'chaining' (dây chuyền) được sử dụng để xử lý xung đột như thế nào?

A. Ghi đè giá trị cũ bằng giá trị mới

B. Tìm vị trí trống tiếp theo trong bảng

C. Sử dụng danh sách liên kết tại mỗi vị trí trong bảng để lưu trữ các khóa băm vào cùng vị trí

D. Tăng kích thước bảng băm

2. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick Sort) là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(log n)

D. O(n)

3. Trong thuật toán DFS (Depth-First Search), cấu trúc dữ liệu nào được sử dụng một cách ngầm định (implicitly) để theo dõi các đỉnh cần duyệt?

A. Hàng đợi

B. Ngăn xếp (call stack)

C. Cây nhị phân

D. Mảng

4. Trong cấu trúc dữ liệu, thuật ngữ 'ADT' thường được dùng để chỉ điều gì?

A. Kiểu dữ liệu trừu tượng (Abstract Data Type)

B. Kiểu dữ liệu thích ứng (Adaptive Data Type)

C. Kiểu dữ liệu nâng cao (Advanced Data Type)

D. Kiểu dữ liệu ứng dụng (Applied Data Type)

5. Thuật toán sắp xếp nào sau đây hoạt động dựa trên nguyên tắc 'chia để trị' (Divide and Conquer)?

A. Sắp xếp nổi bọt (Bubble Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp chọn (Selection Sort)

D. Sắp xếp trộn (Merge Sort)

6. Hash table (Bảng băm) thường được sử dụng cho mục đích gì?

A. Sắp xếp dữ liệu

B. Tìm kiếm và truy xuất dữ liệu nhanh chóng dựa trên khóa

C. Lưu trữ dữ liệu theo thứ tự tuyến tính

D. Biểu diễn quan hệ thứ bậc giữa các phần tử

7. Ưu điểm chính của việc sử dụng danh sách liên kết (Linked List) so với mảng (Array) là gì?

A. Truy cập phần tử nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước thay đổi

C. Dễ dàng sắp xếp hơn

D. Tiết kiệm bộ nhớ hơn cho dữ liệu tĩnh

8. Cấu trúc dữ liệu nào phù hợp nhất để kiểm tra xem một biểu thức ngoặc có hợp lệ (đóng mở đúng cặp) hay không?

A. Hàng đợi

B. Ngăn xếp

C. Cây nhị phân

D. Mảng

9. Khi nào thì thuật toán tìm kiếm tuyến tính (Linear Search) là lựa chọn tốt hơn so với tìm kiếm nhị phân (Binary Search)?

A. Khi dữ liệu đã được sắp xếp

B. Khi kích thước dữ liệu rất lớn

C. Khi cần tìm kiếm trên danh sách liên kết

D. Khi dữ liệu có kích thước nhỏ và không cần sắp xếp

10. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Danh sách liên kết (Linked List)

D. Cây nhị phân (Binary Tree)

11. Ưu điểm của việc sử dụng danh sách liên kết đôi (Doubly Linked List) so với danh sách liên kết đơn (Singly Linked List) là gì?

A. Tiết kiệm bộ nhớ hơn

B. Duyệt danh sách theo cả hai chiều (tiến và lùi) dễ dàng hơn

C. Chèn và xóa phần tử ở đầu danh sách nhanh hơn

D. Tìm kiếm phần tử nhanh hơn

12. Trong cây nhị phân tìm kiếm (BST - Binary Search Tree), tính chất nào sau đây luôn đúng?

A. Mọi nút con trái đều lớn hơn nút cha

B. Mọi nút con phải đều nhỏ hơn nút cha

C. Giá trị của nút cha luôn nằm giữa giá trị lớn nhất của cây con trái và giá trị nhỏ nhất của cây con phải

D. Mọi nút con trái đều nhỏ hơn hoặc bằng nút cha và mọi nút con phải đều lớn hơn nút cha

13. Trong cây đỏ-đen (Red-Black Tree), một tính chất quan trọng là gì?

A. Tất cả các nút đều có màu đỏ

B. Đường đi từ gốc đến mọi nút lá đều có cùng số lượng nút đen

C. Chiều cao của cây luôn là logarit cơ số 2 của số lượng nút

D. Nút gốc luôn có màu đỏ

14. Độ phức tạp thời gian của thao tác 'chèn' (insertion) vào một cây nhị phân tìm kiếm cân bằng (ví dụ: AVL, Red-Black) là bao nhiêu?

A. O(1)

B. O(n)

C. O(log n)

D. O(n log n)

15. Giải thuật tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất trên loại dữ liệu nào?

A. Danh sách liên kết chưa sắp xếp

B. Mảng đã sắp xếp

C. Cây nhị phân tìm kiếm chưa cân bằng

D. Đồ thị không có hướng

16. Độ phức tạp không gian của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

17. Giải thuật sắp xếp nào sau đây thường được coi là nhanh nhất trong thực tế cho mảng lớn, mặc dù độ phức tạp trường hợp xấu nhất có thể là O(n^2)?

A. Sắp xếp nổi bọt (Bubble Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp trộn (Merge Sort)

D. Sắp xếp nhanh (Quick Sort)

18. Cây AVL là loại cây gì?

A. Cây nhị phân tìm kiếm không cân bằng

B. Cây nhị phân tìm kiếm tự cân bằng

C. Cây n-phân

D. Cây biểu thức

19. Thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search) sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần duyệt?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây nhị phân tìm kiếm

D. Heap (Đống)

20. Trong thuật toán sắp xếp trộn (Merge Sort), quá trình 'trộn' (merge) có vai trò gì?

A. Chia nhỏ mảng thành các mảng con

B. So sánh các phần tử và đổi chỗ nếu cần

C. Kết hợp hai mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp

D. Chọn phần tử chốt để phân vùng mảng

21. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp xấu nhất?

A. Sắp xếp nhanh (Quick Sort)

B. Sắp xếp nổi bọt (Bubble Sort)

C. Sắp xếp trộn (Merge Sort)

D. Sắp xếp chèn (Insertion Sort)

22. Ứng dụng phổ biến của hàng đợi (Queue) trong hệ thống máy tính là gì?

A. Quản lý bộ nhớ

B. Lập lịch tác vụ (task scheduling) trong hệ điều hành

C. Tính toán biểu thức số học

D. Tìm kiếm đường đi trong đồ thị

23. Thuật toán Kruskal được sử dụng để giải quyết bài toán nào?

A. Tìm đường đi ngắn nhất giữa hai đỉnh

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) của đồ thị

C. Duyệt đồ thị theo chiều sâu

D. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô

24. Thuật toán Prim được sử dụng để giải quyết bài toán nào?

A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) của đồ thị

C. Tìm luồng cực đại trong mạng

D. Phát hiện chu trình trong đồ thị có hướng

25. Trong thuật toán Dijkstra, mục đích chính là gì?

A. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm

B. Tìm chu trình Euler trong đồ thị

C. Tìm cây khung nhỏ nhất của đồ thị

D. Phát hiện chu trình âm trong đồ thị

26. Trong cấu trúc dữ liệu đồ thị, 'bậc' (degree) của một đỉnh là gì?

A. Số lượng đỉnh trong đồ thị

B. Số lượng cạnh trong đồ thị

C. Số lượng cạnh liên thuộc với đỉnh đó

D. Độ dài đường đi ngắn nhất từ đỉnh đó đến một đỉnh khác

27. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai hàng đợi ưu tiên (Priority Queue)?

A. Mảng

B. Ngăn xếp

C. Heap (Đống)

D. Danh sách liên kết đơn

28. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai chức năng 'undo' và 'redo' trong các ứng dụng?

A. Hàng đợi

B. Ngăn xếp

C. Cây nhị phân

D. Mảng

29. Điều gì xảy ra khi có 'xung đột' (collision) trong bảng băm?

A. Dữ liệu bị mất

B. Hai hoặc nhiều khóa băm vào cùng một vị trí trong bảng

C. Bảng băm tự động tăng kích thước

D. Chương trình bị lỗi

30. Đồ thị (Graph) có thể được biểu diễn bằng cấu trúc dữ liệu nào sau đây?

A. Mảng một chiều

B. Danh sách liên kết đơn

C. Ma trận kề (Adjacency Matrix) và Danh sách kề (Adjacency List)

D. Cây nhị phân cân bằng