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

1. Trong cây nhị phân tìm kiếm cân bằng (ví dụ: AVL tree, Red-Black tree), thao tác cân bằng cây được thực hiện để đảm bảo điều gì?

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

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

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

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

2. 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 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. Danh sách liên kết (Linked List)

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

3. 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. Cây nhị phân tìm kiếm (Binary Search Tree)

4. Phương pháp `tham lam` (Greedy) trong thiết kế thuật toán thường đưa ra quyết định tối ưu cục bộ với hy vọng đạt được điều gì?

A. Độ phức tạp thời gian thấp nhất

B. Lời giải tối ưu toàn cục

C. Lời giải gần đúng

D. Sử dụng ít bộ nhớ nhất

5. Trong 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 của giá trị?

A. Duyệt theo thứ tự trước (Pre-order traversal)

B. Duyệt theo thứ tự sau (Post-order traversal)

C. Duyệt theo thứ tự giữa (In-order traversal)

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

6. Trong đồ thị, ma trận kề (Adjacency Matrix) phù hợp nhất để biểu diễn đồ thị nào?

A. Đồ thị có số cạnh ít so với số đỉnh (sparse graph)

B. Đồ thị có trọng số âm

C. Đồ thị có số cạnh nhiều so với số đỉnh (dense graph)

D. Đồ thị vô hướng

7. Thuật toán nào sau đây tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm?

A. Thuật toán Floyd-Warshall

B. Thuật toán Bellman-Ford

C. Thuật toán Dijkstra

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

8. Khi nào thì độ phức tạp thời gian của thuật toán sắp xếp nhanh (Quick Sort) trở thành O(n^2)?

A. Khi mảng đã được sắp xếp hoặc gần sắp xếp

B. Khi phần tử chốt (pivot) luôn được chọn là phần tử lớn nhất hoặc nhỏ nhất

C. Khi mảng có kích thước nhỏ

D. Khi sử dụng phương pháp phân hoạch Lomuto

9. Trong lập trình động (Dynamic Programming), kỹ thuật `ghi nhớ` (memoization) được sử dụng để làm gì?

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

B. Tăng độ phức tạp thời gian

C. Lưu trữ kết quả của các bài toán con đã giải để tránh tính toán lại

D. Chia bài toán lớn thành các bài toán con độc lập

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

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Fleury

D. Thuật toán Kruskal

11. Thuật toán Bellman-Ford có thể xử lý đồ thị có trọng số cạnh âm, nhưng có một hạn chế quan trọng. Hạn chế đó là gì?

A. Không thể tìm đường đi ngắn nhất trong đồ thị có chu trình âm

B. Chỉ hoạt động với đồ thị có hướng

C. Độ phức tạp thời gian cao hơn thuật toán Dijkstra

D. Không xử lý được đồ thị vô hướng

12. Ư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 các phần tử nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi số lượng phần tử thay đổi

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

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

13. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân (Binary Search) trong trường hợp mảng đã được sắp xếp là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

14. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm (Hash Table) phụ thuộc vào yếu tố nào sau đây?

A. Kích thước của bảng băm

B. Hàm băm (Hash function) và phương pháp xử lý xung đột

C. Số lượng phần tử trong bảng băm

D. Loại dữ liệu được lưu trữ trong bảng băm

15. Trong thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh cần duyệt?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

16. Cấu trúc dữ liệu nào phù hợp nhất để 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 (Đống)

17. Trong cấu trúc dữ liệu 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 (Pre-order traversal)

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

C. Tìm kiếm một nút (Search)

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

18. Thuật toán Kruskal và thuật toán 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)

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

D. Tìm chu trình Hamilton

19. 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à thường được coi là hiệu quả nhất trong thực tế?

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)

20. Trong cấu trúc dữ liệu đồ thị, danh sách kề (Adjacency List) thường được ưu tiên sử dụng hơn ma trận kề (Adjacency Matrix) trong trường hợp nào?

A. Khi cần kiểm tra nhanh sự tồn tại của một cạnh giữa hai đỉnh

B. Khi đồ thị có số cạnh ít so với số đỉnh (sparse graph)

C. Khi cần thực hiện các phép toán trên ma trận

D. Khi đồ thị có trọng số không âm

21. Trong thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng (ngầm định hoặc tường minh) để theo dõi các đỉnh đã duyệt?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack) (ngầm định qua đệ quy hoặc dùng stack tường minh)

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

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

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

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

23. Phương pháp tiếp cận `chia để trị` (Divide and Conquer) thường được sử dụng trong thuật toán nào sau đây?

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)

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

A. Duyệt các phần tử theo thứ tự sắp xếp

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

C. Đảm bảo thứ tự các phần tử được duy trì

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

25. Thuật toán Floyd-Warshall giải quyết bài toán nào sau đây?

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

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

26. Cấu trúc dữ liệu Trie (cây tiền tố) được sử dụng hiệu quả nhất cho ứng dụng nào sau đây?

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

B. Tìm kiếm xâu tiền tố (prefix search) và gợi ý từ

C. Nén dữ liệu

D. Cài đặt hàng đợi ưu tiên

27. Khi nào thì nên sử dụng thuật toán sắp xếp chèn (Insertion Sort) thay vì sắp xếp nhanh (Quick Sort)?

A. Khi cần sắp xếp một mảng lớn

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

C. Khi cần độ phức tạp thời gian tốt nhất trong mọi trường hợp

D. Khi cần sắp xếp trực tuyến (online sorting)

28. Trong lập trình động, bài toán `dãy con chung dài nhất` (Longest Common Subsequence - LCS) thuộc loại bài toán nào?

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

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

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

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

29. Thuật toán sắp xếp nào sau đây luôn có độ phức tạp thời gian O(n^2) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất)?

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

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

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

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

30. Cấu trúc dữ liệu nào sau đây hỗ trợ hiệu quả nhất việc thêm và xóa phần tử ở cả hai đầu?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Deque (Double-ended queue - Hàng đợi hai đầu)

D. Mảng (Array)