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

1. 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 cây khung nhỏ nhất (MST)

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

C. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác

D. Tìm chu trình Euler

2. Trong ngữ cảnh của cấu trúc dữ liệu, 'Abstract Data Type' (ADT) là gì?

A. Một kiểu dữ liệu cụ thể được cài đặt bằng ngôn ngữ lập trình C++

B. Một mô hình trừu tượng mô tả các thao tác có thể thực hiện trên dữ liệu và các tính chất của dữ liệu đó, mà không quan tâm đến cách cài đặt cụ thể

C. Một cấu trúc dữ liệu vật lý lưu trữ dữ liệu trên bộ nhớ

D. Một thuật toán cụ thể để sắp xếp dữ liệu

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

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

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

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

D. Sắp xếp đồ thị

4. Khi nào thì nên sử dụng thuật toán sắp xếp trộn (Merge Sort) thay vì sắp xếp nhanh (Quick Sort)?

A. Khi cần sắp xếp tại chỗ (in-place)

B. Khi cần đảm bảo độ phức tạp thời gian O(n log n) trong mọi trường hợp

C. Khi dữ liệu gần như đã được sắp xếp

D. Khi bộ nhớ là yếu tố hạn chế

5. Trong cây AVL, thao tác xoay cây được thực hiện để làm gì?

A. Tăng tốc độ tìm kiếm

B. Giảm độ cao của cây

C. Cân bằng cây

D. Xóa nút khỏi cây

6. Kỹ thuật 'quy hoạch động' (Dynamic Programming) thường được áp dụng cho các bài toán có đặc điểm nào?

A. Bài toán có thể chia nhỏ thành các bài toán con độc lập

B. Bài toán có cấu trúc con tối ưu và các bài toán con chồng lấp

C. Bài toán yêu cầu giải pháp tham lam

D. Bài toán có không gian tìm kiếm nhỏ

7. Độ 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(log n)

C. O(n log n)

D. O(n)

8. Ưu điểm của việc sử dụng danh sách liên kết so với mảng khi thêm hoặc xóa phần tử ở giữa danh sách là gì?

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

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

C. Không cần dịch chuyển các phần tử khác

D. Dễ dàng cài đặt hơn

9. Khi nào việc sử dụng đệ quy (recursion) trong giải thuật có thể không hiệu quả?

A. Khi bài toán có thể chia nhỏ thành các bài toán con độc lập

B. Khi độ sâu đệ quy quá lớn, dẫn đến tràn bộ nhớ ngăn xếp (stack overflow)

C. Khi cần giải quyết bài toán bằng phương pháp 'chia để trị'

D. Khi bài toán có cấu trúc dữ liệu dạng cây

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

11. Cấu trúc dữ liệu đồ thị (Graph) thích hợp để giải quyết loại bài toán nào sau đây?

A. Sắp xếp danh sách sinh viên theo điểm

B. Tìm đường đi ngắn nhất giữa hai thành phố

C. Lưu trữ thông tin về gia phả

D. Cả 2 và 3

12. Cấu trúc dữ liệu nào thường được sử dụng để triển khai thuật toán BFS (Breadth-First Search) trong đồ thị?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây (Tree)

D. Mảng (Array)

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

14. Giải thuật tham lam (Greedy algorithm) thường được sử dụng để giải quyết loại bài toán nào?

A. Tìm kiếm đường đi ngắn nhất trong đồ thị

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

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

D. Tìm kiếm phần tử trong mảng

15. Thuật toán 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. Mảng chưa sắp xếp

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

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

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

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

A. Quick Sort

B. Heap Sort

C. Selection Sort

D. Merge Sort

17. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để chọn đỉnh có khoảng cách ngắn nhất từ đỉnh nguồn?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

D. Mảng (Array)

18. 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ử với độ phức tạp thời gian O(1)?

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

B. Ngăn xếp (Stack)

C. Mảng (Array)

D. Hàng đợi (Queue)

19. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ 'cha-con' trong một hệ thống phân cấp?

A. Mảng (Array)

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

C. Cây (Tree)

D. Hàng đợi (Queue)

20. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (Binary Search Tree), thứ tự duyệt nào sau đây sẽ cho ra các nút theo thứ tự tăng dần?

A. Pre-order (Tiền thứ tự)

B. Post-order (Hậu thứ tự)

C. In-order (Trung thứ tự)

D. Breadth-first (Duyệt theo chiều rộng)

21. Ưu điểm chính của 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. Truy cập phần tử nhanh hơn

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

D. Thêm và xóa phần tử ở đầu danh sách nhanh hơn

22. Trong một cây nhị phân đầy đủ (Full Binary Tree) có chiều cao h, số lượng nút tối đa có thể có là bao nhiêu?

A. h

B. 2h

C. 2^(h+1) - 1

D. 2^h - 1

23. Trong cấu trúc dữ liệu Heap (Đống), phần tử gốc (root) luôn có giá trị như thế nào so với các phần tử con?

A. Lớn hơn hoặc bằng

B. Nhỏ hơn hoặc bằng

C. Bằng

D. Không có quy tắc cụ thể

24. Thuật toán nào sau đây là một ví dụ của kỹ thuật 'chia để trị' (divide and conquer)?

A. Insertion Sort

B. Bubble Sort

C. Merge Sort

D. Linear Search

25. Hash table (Bảng băm) thường được sử dụng để tối ưu hóa thao tác nào sau đây?

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

B. Tìm kiếm dữ liệu

C. Duyệt dữ liệu theo thứ tự

D. Lưu trữ dữ liệu tuần tự

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

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. TimSort

27. Khi nào nên sử dụng cấu trúc dữ liệu đồ thị có hướng (Directed Graph) thay vì đồ thị vô hướng (Undirected Graph)?

A. Khi các mối quan hệ giữa các đối tượng là hai chiều

B. Khi cần biểu diễn mạng xã hội

C. Khi các mối quan hệ giữa các đối tượng có hướng

D. Khi cần tìm đường đi ngắn nhất

28. Điểm khác biệt chính giữa thuật toán DFS (Depth-First Search) và BFS (Breadth-First Search) trong duyệt đồ thị là gì?

A. DFS nhanh hơn BFS

B. BFS sử dụng ngăn xếp, DFS sử dụng hàng đợi

C. DFS duyệt theo chiều sâu, BFS duyệt theo chiều rộng

D. BFS luôn tìm được đường đi ngắn nhất, DFS thì không

29. Trong cây đỏ-đen (Red-Black Tree), thuộc tính nào sau đây KHÔNG phải là thuộc tính của cây đỏ-đen?

A. Mỗi nút có màu đỏ hoặc đen

B. Gốc cây luôn có màu đen

C. Tất cả các đường đi từ gốc đến nút lá đều có cùng số nút đen

D. Nút đỏ có thể có con màu đỏ

30. 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. Mảng (Array)