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

1. Cấu trúc dữ liệu nào sau đây tuân 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 (Tree)

2. Ư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

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

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

3. Giải thuật nào sau đây thường được sử dụng để tìm kiếm đường đi trong một mê cung?

A. Bubble Sort

B. Depth-First Search (DFS)

C. Binary Search

D. Merge Sort

4. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn mối quan hệ 'cha-con' trong hệ thống phân cấp?

A. Mảng

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

C. Cây

D. Hàng đợi

5. Ưu điểm của việc sử dụng bảng băm (hash table) so với cây tìm kiếm là gì?

A. Bảng băm luôn được sắp xếp

B. Bảng băm có độ phức tạp thời gian tốt hơn cho các thao tác chèn, xóa và tìm kiếm trung bình

C. Bảng băm sử dụng ít bộ nhớ hơn

D. Bảng băm dễ triển khai hơn

6. Trong đồ thị, thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác?

A. Depth-First Search (DFS)

B. Breadth-First Search (BFS)

C. Dijkstra's Algorithm

D. Prim's Algorithm

7. Độ phức tạp không gian của thuật toán tìm kiếm tuyến tính (Linear Search) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

8. Độ phức tạp thời gian để chèn một phần tử vào đầu một 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)

9. Độ phức tạp thời gian tốt nhất của thuật toán Bubble Sort là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(1)

10. Cây tìm kiếm nhị phân tự cân bằng nào sau đây đảm bảo rằng chiều cao của cây luôn là O(log n), trong đó n là số lượng nút?

A. Cây nhị phân hoàn chỉnh

B. Cây AVL

C. Cây suy biến

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

11. 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 chưa được sắp xếp?

A. Binary Search

B. Linear Search

C. Merge Sort

D. Quick Sort

12. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để triển khai hàng đợi ưu tiên?

A. Mảng

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

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

D. Heap

13. Trong các thuật toán sắp xếp sau, thuật toán nào ổn định (stable)?

A. Quick Sort

B. Heap Sort

C. Selection Sort

D. Insertion Sort

14. Trong cấu trúc dữ liệu cây, duyệt theo thứ tự nào sẽ in ra các nút theo thứ tự tăng dần trong cây nhị phân tìm kiếm?

A. Preorder

B. Inorder

C. Postorder

D. Level order

15. 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. Dijkstra's Algorithm

B. Kruskal's Algorithm

C. Depth-First Search (DFS)

D. Breadth-First Search (BFS)

16. 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

B. Insertion Sort

C. Merge Sort

D. Selection Sort

17. Trong bảng băm (hash table), kỹ thuật nào sau đây được sử dụng để giải quyết xung đột (collision)?

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

B. Tìm kiếm nhị phân (Binary Search)

C. Địa chỉ mở (Open Addressing)

D. Duyệt theo chiều sâu (Depth-First Search)

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

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Insertion Sort

19. Thuật toán nào sau đây tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Prim

D. Thuật toán Kruskal

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

D. Tree

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

22. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là bao nhiêu?

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

23. Trong một cây nhị phân tìm kiếm (BST), 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 thứ tự giữa (Inorder Traversal)

24. Kỹ thuật lập trình động (Dynamic Programming) thường được sử dụng để giải quyết loại bài toán nào?

A. Bài toán tìm kiếm

B. Bài toán tối ưu hóa

C. Bài toán sắp xếp

D. Bài toán duyệt đồ thị

25. Cấu trúc dữ liệu nào sau đây thường được sử dụng để kiểm tra xem một dấu ngoặc (ví dụ: '(', '{', '[') đã được đóng đúng cách hay chưa?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

D. Cây (Tree)

26. Thuật toán nào sau đây là một ví dụ về kỹ thuật 'chia để trị' (Divide and Conquer)?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

27. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong một mảng đã được sắp xếp bằng thuật toán tìm kiếm nhị phân là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

28. Heap Sort có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

29. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên đến các phần tử với độ phức tạp thời gian O(1)?

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

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

C. Mảng

D. Hàng đợi

30. Trong cây, nút nào không có nút con được gọi là gì?

A. Nút gốc (Root)

B. Nút lá (Leaf)

C. Nút trung gian (Internal Node)

D. Nút cha (Parent Node)