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

1. Trong cấu trúc dữ liệu đồ thị, thuật toán nào thường đượ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 trong đồ thị có trọng số không âm?

A. Thuật toán tìm kiếm theo chiều sâu (DFS)

B. Thuật toán tìm kiếm theo chiều rộng (BFS)

C. Thuật toán Dijkstra

D. Thuật toán Floyd-Warshall

2. Giải thuật 'chia để trị' (Divide and Conquer) thường được áp dụng hiệu quả nhất cho loại bài toán nào?

A. Bài toán có thể chia nhỏ thành các bài toán con độc lập và tương tự

B. Bài toán yêu cầu tìm kiếm tuần tự trong dữ liệu không có cấu trúc

C. Bài toán có dữ liệu đầu vào nhỏ

D. Bài toán yêu cầu tối ưu hóa cục bộ

3. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử đầu và cuối trong thời gian O(1)?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Deque (Double-ended Queue)

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

4. Ưu điểm chính của việc sử dụng bảng băm (Hash Table) là gì?

A. Dữ liệu luôn được sắp xếp

B. Tìm kiếm, chèn, xóa phần tử có độ phức tạp thời gian trung bình O(1)

C. Duyệt phần tử theo thứ tự nhanh chóng

D. Tiết kiệm bộ nhớ hơn so với mảng

5. Điều gì xảy ra khi bạn cố gắng lấy một phần tử ra khỏi một ngăn xếp (Stack) rỗng?

A. Trả về giá trị NULL

B. Gây ra lỗi tràn ngăn xếp (Stack Overflow)

C. Gây ra lỗi tràn bộ nhớ (Memory Overflow)

D. Gây ra lỗi ngăn xếp rỗng (Stack Underflow)

6. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

7. Thuật toán Kruskal tìm cây khung nhỏ nhất (MST) hoạt động dựa trên nguyên tắc nào?

A. Chọn cạnh có trọng số nhỏ nhất mà không tạo thành chu trình

B. Chọn đỉnh gần cây MST đang xây dựng nhất

C. Chia đồ thị thành các thành phần liên thông nhỏ hơn

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

8. Thuật toán Prim và Kruskal được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?

A. Tìm đường đi ngắn nhất

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)

C. Tìm luồng cực đại (Maximum Flow)

D. Tìm chu trình Euler

9. 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 nút (Search)

D. Duyệt cây theo thứ tự giữa (Inorder traversal)

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

A. Truy cập phần tử ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước dữ liệu không cố định

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

D. Sắp xếp phần tử nhanh hơn

11. Thuật toán sắp xếp nào có độ phức tạp thời gian trung bình tốt nhất trong số các thuật toán sắp xếp so sánh?

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 nhanh (Quick Sort)

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

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

A. Mảng (Array)

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

C. Cây nhị phân tìm kiếm (Binary Search Tree)

D. Heap (Vun đống)

13. Trong cây nhị phân tìm kiếm, duyệt cây theo thứ tự giữa (Inorder traversal) sẽ cho ra kết quả gì?

A. Các nút được duyệt theo thứ tự mức

B. Các nút được duyệt theo thứ tự giảm dần

C. Các nút được duyệt theo thứ tự tăng dần

D. Thứ tự duyệt không xác định

14. Thuật toán Floyd-Warshall được sử dụng để giải quyết bài toán nào trong đồ thị?

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

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

C. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)

D. Tìm luồng cực đại (Maximum Flow)

15. Thuật toán tìm kiếm nào sau đây có độ phức tạp thời gian tốt nhất là O(1)?

A. Tìm kiếm tuyến tính (Linear Search)

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

C. Tìm kiếm trong bảng băm (Hash Table Lookup)

D. Tìm kiếm theo chiều rộng (Breadth-First Search)

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

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(1)

17. Thuật toán nào sau đây không phải là thuật toán sắp xếp so sánh?

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 đếm (Counting Sort)

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

18. Trong cây nhị phân cân bằng (ví dụ AVL tree, Red-Black tree), mục đích chính của việc cân bằng cây là gì?

A. Giảm độ phức tạp không gian

B. Tăng tốc độ duyệt cây

C. Đảm bảo độ phức tạp thời gian O(log n) cho các thao tác tìm kiếm, chèn, xóa

D. Đơn giản hóa việc cài đặt cây

19. Thuật toán nào sau đây là thuật toán sắp xếp ổn định (stable sorting algorithm)?

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

B. Sắp xếp vun đống (Heap Sort)

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

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

20. Thuật toán tìm kiếm theo chiều rộng (BFS) thường được sử dụng để làm gì trong đồ thị?

A. Tìm đường đi ngắn nhất trong đồ thị không trọng số

B. Tìm đường đi ngắn nhất trong đồ thị có trọng số

C. Phát hiện chu trình âm

D. Sắp xếp các đỉnh của đồ thị

21. Khi nào nên sử dụng danh sách liên kết đôi (Doubly Linked List) thay vì danh sách liên kết đơn (Singly Linked List)?

A. Khi cần tiết kiệm bộ nhớ

B. Khi cần duyệt danh sách theo cả hai chiều (tiến và lùi)

C. Khi cần truy cập phần tử ngẫu nhiên nhanh chóng

D. Khi số lượng phần tử trong danh sách rất lớn

22. Trong cây nhị phân tìm kiếm, khi xóa một nút có hai con, nút nào thường được chọn để thay thế?

A. Nút con trái lớn nhất của cây con trái

B. Nút con phải nhỏ nhất của cây con phải

C. Bất kỳ nút lá nào trong cây

D. Nút gốc của cây

23. Thuật toán sắp xếp nào sau đây hoạt động tốt nhất trên dữ liệu gần như đã được sắp xếp?

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

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

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

D. Sắp xếp vun đống (Heap Sort)

24. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) nào mô tả một tập hợp các phần tử mà việc thêm và xóa phần tử chỉ được thực hiện ở một đầu?

A. Hàng đợi (Queue)

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

C. Ngăn xếp (Stack)

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

25. Cấu trúc dữ liệu nào 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)

26. Trong thuật toán tìm kiếm nhị phân (Binary Search), dữ liệu đầu vào cần phải có đặc điểm gì?

A. Dữ liệu phải được sắp xếp

B. Dữ liệu phải là số nguyên

C. Dữ liệu phải có kích thước nhỏ

D. Dữ liệu phải là duy nhất

27. Cấu trúc dữ liệu nào phù hợp nhất để kiểm tra xem một chuỗi ngoặc có hợp lệ hay không (ví dụ: '()[]{}' là hợp lệ, '([)]' là không hợp lệ)?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Cây (Tree)

D. Mảng (Array)

28. Độ phức tạp không gian của thuật toán sắp xếp vun đống (Heap Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(1)

29. Cấu trúc dữ liệu nào thích hợp nhất để biểu diễn mối quan hệ 'nhiều-nhiều' giữa các đối tượng?

A. Mảng (Array)

B. Cây (Tree)

C. Đồ thị (Graph)

D. Hàng đợi (Queue)

30. Độ phức tạp thời gian trường hợp xấu nhất của thuật toán sắp xếp trộn (Merge Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)