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

1. 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)?

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

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

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

D. Merge Sort (Sắp xếp trộ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 duyệt đồ thị theo chiều rộng (BFS)?

A. Stack

B. Queue

C. Tree

D. Graph

3. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi có phải là palindrome hay không?

A. Queue

B. Stack

C. Linked List

D. Tree

4. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

5. Cấu trúc dữ liệu nào sau đây sử dụng con trỏ để liên kết các phần tử?

A. Mảng (Array)

B. Hàng đợi (Queue)

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

D. Ngăn xếp (Stack)

6. Phương pháp tiếp cận 'chia để trị' (divide and conquer) được sử dụng trong thuật toán nào sau đây?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

7. Độ 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à gì?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(n log n)

8. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất là O(n)?

A. Quick Sort

B. Merge Sort

C. Insertion Sort

D. Bubble Sort

9. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ nút nguồn đến các nút khác?

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

C. Priority Queue (Hàng đợi ưu tiên)

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

10. Trong cây tìm kiếm nhị phân (binary search tree), thứ tự duyệt nào sau đây sẽ in ra các nút theo thứ tự tăng dần?

A. Preorder

B. Inorder

C. Postorder

D. Level order

11. Trong cấu trúc dữ liệu đồ thị, một cạnh (edge) nối một nút với chính nó được gọi là gì?

A. Parallel Edge

B. Bridge

C. Loop

D. Cut Vertex

12. Trong cấu trúc dữ liệu đồ thị (graph), thuật ngữ nào sau đây mô tả một đường đi đi qua mỗi cạnh đúng một lần?

A. Hamiltonian Cycle

B. Eulerian Path

C. Shortest Path

D. Critical Path

13. 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 (Hàng đợi)

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

C. Stack (Ngăn xếp)

D. Tree (Cây)

14. Trong thuật toán Quick Sort, kỹ thuật nào được sử dụng để phân vùng mảng?

A. Merging

B. Swapping

C. Partitioning

D. Dividing

15. Thuật toán nào sau đây có độ phức tạp thời gian trung bình tốt hơn so với Bubble Sort?

A. Selection Sort

B. Insertion Sort

C. Merge Sort

D. Tất cả các đáp án trên

16. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp?

A. Queue (Hàng đợi)

B. Stack (Ngăn xếp)

C. Graph (Đồ thị)

D. Tree (Cây)

17. Độ phức tạp không gian của thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) trên một đồ thị là gì, trong đó V là số đỉnh và E là số cạnh?

A. O(1)

B. O(V)

C. O(E)

D. O(V + E)

18. Độ phức tạp thời gian của thao tác xóa một phần tử khỏi đầ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)

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

A. Linear Search

B. Binary Search

C. Depth-First Search

D. Breadth-First Search

20. 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. Linked List

B. Stack

C. Heap

D. Queue

21. Ư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 ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi biết trước kích thước

C. Dễ dàng chèn và xóa các phần tử

D. Tìm kiếm nhanh hơn

22. Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình trong một đồ thị?

A. Dijkstra's algorithm

B. Depth-First Search (DFS)

C. Breadth-First Search (BFS)

D. Prim's algorithm

23. Trong cây AVL, thao tác nào sau đây được sử dụng để duy trì tính cân bằng của cây?

A. Tìm kiếm

B. Chèn

C. Xoay (Rotation)

D. Xóa

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

C. Array

D. Stack

25. 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) của một đồ thị?

A. Dijkstra

B. Bellman-Ford

C. Prim

D. Depth-First Search

26. Cấu trúc dữ liệu nào sau đây cho phép truy cập các phần tử theo thứ tự FIFO (First In, First Out)?

A. Stack

B. Queue

C. Tree

D. Graph

27. Độ 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)

28. Trong cây nhị phân tìm kiếm (binary search tree), 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 thứ tự trước (preorder traversal)

B. Duyệt cây theo thứ tự sau (postorder traversal)

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

D. Duyệt cây theo chiều rộng (breadth-first traversal)

29. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa hai nút trong một đồ thị có trọng số âm?

A. Dijkstra

B. Breadth-First Search (BFS)

C. Depth-First Search (DFS)

D. Bellman-Ford

30. Độ phức tạp thời gian của thao tác chèn vào một bảng băm (hash table) trong trường hợp trung bình là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)