Đề 3 – Đề thi, câu hỏi trắc nghiệm online Cấu trúc dữ liệu và giải thuật

1. Độ phức tạp thời gian của thao tác chèn một phần tử vào đầu danh sách liên kết đơn (singly linked list) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

2. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều rộng (Breadth-First Search)?

A. Stack

B. Queue

C. Linked List

D. Heap

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

A. O(n)

B. O(1)

C. O(log n)

D. O(n^2)

4. Độ phức tạp không gian của thuật toán Merge Sort là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

5. Trong biểu diễn đồ thị bằng danh sách kề (adjacency list), mỗi nút (node) trong đồ thị sẽ chứa thông tin về:

A. Tất cả các nút khác trong đồ thị.

B. Tất cả các cạnh trong đồ thị.

C. Các nút lân cận (adjacent nodes) của nó.

D. Đường đi ngắn nhất đến tất cả các nút khác.

6. Ứng dụng nào sau đây là phù hợp nhất cho cấu trúc dữ liệu Queue?

A. Quản lý lịch sử truy cập trang web.

B. Đảo ngược một chuỗi.

C. In các tài liệu theo thứ tự gửi đến.

D. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức.

7. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n) và hoạt động tốt nhất trên dữ liệu đã gần được sắp xếp?

A. Quick Sort

B. Merge Sort

C. Insertion Sort

D. Heap Sort

8. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một biểu thức toán học có cân bằng dấu ngoặc hay không?

A. Queue

B. Linked List

C. Stack

D. Binary Tree

9. Thuật toán sắp xếp nào sau đây hoạt động bằng cách chia mảng thành các phần nhỏ hơn, sắp xếp chúng và sau đó hợp nhất lại?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

10. Trong cây tìm kiếm nhị phân, phép duyệt nào sau đây in ra các nút theo thứ tự tăng dần?

A. Preorder Traversal

B. Postorder Traversal

C. Inorder Traversal

D. Level Order Traversal

11. Độ phức tạp thời gian của thuật toán Bubble Sort trong trường hợp xấu nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(n log n)

12. Thuật toán nào sau đây có độ phức tạp thời gian trung bình tốt nhất?

A. Bubble Sort

B. Insertion Sort

C. Quick Sort

D. Selection Sort

13. 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. Stack

B. Queue

C. Heap

D. Linked List

14. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu (data compression)?

A. Bubble Sort

B. Huffman Coding

C. Binary Search

D. Dijkstra's Algorithm

15. Trong cây quyết định (decision tree), mục tiêu của việc cắt tỉa (pruning) là gì?

A. Tăng độ phức tạp của cây.

B. Giảm độ chính xác của cây.

C. Ngăn chặn hiện tượng quá khớp (overfitting).

D. Tăng tốc độ xây dựng cây.

16. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai bộ nhớ cache?

A. Stack

B. Queue

C. Hash Table

D. Linked List

17. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất là O(n) khi dữ liệu đã được sắp xếp?

A. Quick Sort

B. Bubble Sort

C. Selection Sort

D. Insertion Sort

18. Hash table (bảng băm) giải quyết xung đột (collision) bằng phương pháp nào sau đây?

A. Luôn tạo ra một bảng mới lớn hơn.

B. Sử dụng một hàm băm khác.

C. Sử dụng các kỹ thuật như chaining hoặc open addressing.

D. Loại bỏ các phần tử trùng lặp.

19. Độ phức tạp không gian của thuật toán Quick Sort trong trường hợp trung bình là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

20. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút khác trong một đồ thị có trọng số không âm?

A. Depth-First Search (DFS)

B. Breadth-First Search (BFS)

C. Dijkstra's Algorithm

D. Prim's Algorithm

21. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm đường đi ngắn nhất trong trò chơi điện tử?

A. Stack

B. Queue

C. Graph

D. Linked List

22. Trong cây tìm kiếm nhị phân, thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n)?

A. Duyệt cây theo chiều rộng (Breadth-First Traversal).

B. Tìm kiếm một phần tử.

C. Duyệt cây theo chiều sâu (Depth-First Traversal).

D. Tìm phần tử lớn nhất trong cây.

23. Thuật toán nào sau đây có tính ổn định (stable), nghĩa là các phần tử bằng nhau giữ nguyên thứ tự tương đối sau khi sắp xếp?

A. Quick Sort

B. Heap Sort

C. Selection Sort

D. Merge Sort

24. Độ phức tạp thời gian của thao tác tìm kiếm trong hash table (bảng băm) với giải quyết xung đột tốt là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

25. Trong một đồ thị có hướng (directed graph), thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình (cycle)?

A. Breadth-First Search (BFS)

B. Prim's Algorithm

C. Depth-First Search (DFS)

D. Dijkstra's Algorithm

26. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong mảng đã được sắp xếp?

A. Linear Search

B. Binary Search

C. Depth-First Search (DFS)

D. Breadth-First Search (BFS)

27. Thuật toán nào sau đây thường được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị?

A. Depth-First Search (DFS)

B. Breadth-First Search (BFS)

C. Dijkstra's Algorithm

D. Prim's Algorithm

28. 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. Queue

B. Linked List

C. Stack

D. Binary Tree

29. Cây nào sau đây đảm bảo rằng độ dài đường đi từ gốc đến bất kỳ lá nào khác biệt không quá một hằng số?

A. Binary Search Tree

B. AVL Tree

C. Complete Binary Tree

D. Skewed Binary Tree

30. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên (random access) đến các phần tử?

A. Linked List

B. Stack

C. Queue

D. Array