1. Trong thuật toán Kruskal để tìm cây khung nhỏ nhất, bước quan trọng nhất là gì?
A. Chọn cạnh có trọng số lớn nhất mà không tạo thành chu trình.
B. Chọn cạnh có trọng số nhỏ nhất mà không tạo thành chu trình.
C. Chọn cạnh ngẫu nhiên.
D. Chọn cạnh đầu tiên trong danh sách.
2. Sự khác biệt chính giữa thuật toán Prim và Kruskal là gì?
A. Prim bắt đầu từ một đỉnh, Kruskal bắt đầu từ một cạnh.
B. Prim bắt đầu từ một cạnh, Kruskal bắt đầu từ một đỉnh.
C. Prim sử dụng hàng đợi ưu tiên, Kruskal sử dụng ngăn xếp.
D. Prim luôn tìm ra cây khung nhỏ nhất, Kruskal thì không.
3. Điều kiện nào sau đây là cần thiết để một đồ thị có đường đi Euler?
A. Tất cả các đỉnh phải có bậc chẵn.
B. Có đúng hai đỉnh có bậc lẻ.
C. Đồ thị phải liên thông.
D. Cả B và C.
4. Thuật toán Edmonds-Karp cải thiện thuật toán Ford-Fulkerson như thế nào?
A. Luôn tìm thấy luồng cực đại nhanh hơn.
B. Đảm bảo thuật toán luôn kết thúc.
C. Có thể xử lý đồ thị có trọng số âm.
D. Đơn giản hóa việc triển khai.
5. Thuật toán Dijkstra được sử dụng để giải quyết vấn đề nào?
A. Tìm kiếm tuyến tính trong một mảng.
B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số không âm.
C. Sắp xếp một mảng theo thứ tự giảm dần.
D. Tìm kiếm nhị phân trong một mảng đã được sắp xếp.
6. Trong thuật toán Bellman-Ford, điều gì xảy ra nếu sau V-1 vòng lặp, khoảng cách đến một đỉnh vẫn còn giảm?
A. Đồ thị không có đường đi.
B. Đồ thị chứa chu trình âm.
C. Thuật toán đã hoàn thành.
D. Có lỗi trong thuật toán.
7. Trong thuật toán Ford-Fulkerson, mục tiêu chính là gì?
A. Tìm đường đi ngắn nhất.
B. Tìm luồng cực đại trong mạng.
C. Tìm cây khung nhỏ nhất.
D. Sắp xếp các đỉnh theo thứ tự tô pô.
8. Thuật toán Prim bắt đầu từ một đỉnh tùy ý và liên tục thêm các cạnh có trọng số nhỏ nhất để mở rộng cây. Điều này đúng hay sai?
A. Đúng
B. Sai
C. Chỉ đúng với đồ thị có trọng số dương
D. Chỉ đúng với đồ thị vô hướng
9. Ứng dụng thực tế của sắp xếp tô pô là gì?
A. Tìm đường đi ngắn nhất trong bản đồ.
B. Lập lịch các công việc phụ thuộc.
C. Tìm cây khung nhỏ nhất cho mạng lưới điện.
D. Sắp xếp các số theo thứ tự tăng dần.
10. Trong bài toán ghép cặp cực đại (maximum matching), mục tiêu là gì?
A. Tìm đường đi ngắn nhất giữa hai tập hợp.
B. Tìm số lượng cạnh lớn nhất mà không có hai cạnh nào có chung đỉnh.
C. Tìm cây khung nhỏ nhất.
D. Sắp xếp các đỉnh theo thứ tự.
11. Định lý luồng cực đại – lát cắt cực tiểu phát biểu điều gì?
A. Luồng cực đại bằng trọng số cạnh lớn nhất trong đồ thị.
B. Luồng cực đại bằng dung lượng của lát cắt cực tiểu.
C. Luồng cực đại bằng tổng dung lượng của tất cả các cạnh.
D. Luồng cực đại bằng số lượng đỉnh trong đồ thị.
12. Trong thuật toán sắp xếp trộn (merge sort), độ phức tạp thời gian tốt nhất là gì?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
13. Trong một mạng luồng, một ‘đường tăng’ là gì?
A. Đường đi ngắn nhất từ nguồn đến đích.
B. Đường đi từ nguồn đến đích có thể tăng luồng.
C. Đường đi dài nhất từ nguồn đến đích.
D. Đường đi từ đích đến nguồn.
14. Cho một đồ thị có hướng, thuật toán nào được sử dụng để phát hiện chu trình?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Tìm kiếm theo chiều sâu (DFS)
D. Tìm kiếm theo chiều rộng (BFS)
15. Ứng dụng thực tế của bài toán ghép cặp cực đại là gì?
A. Tìm đường đi ngắn nhất.
B. Gán công việc cho nhân viên.
C. Tìm cây khung nhỏ nhất.
D. Sắp xếp các số.
16. Thuật toán Bellman-Ford giải quyết vấn đề đường đi ngắn nhất nào?
A. Đường đi ngắn nhất giữa tất cả các cặp đỉnh.
B. Đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác, ngay cả khi có trọng số âm.
C. Đường đi ngắn nhất trong đồ thị không trọng số.
D. Đường đi ngắn nhất trong đồ thị có hướng không chu trình.
17. Ứng dụng nào sau đây KHÔNG phải là ứng dụng của cây khung nhỏ nhất?
A. Thiết kế mạng lưới điện.
B. Tìm đường đi ngắn nhất giữa hai thành phố.
C. Xây dựng mạng lưới đường bộ.
D. Phân cụm dữ liệu.
18. Điều gì xảy ra khi thuật toán Ford-Fulkerson không tìm thấy đường tăng nào?
A. Đã tìm thấy luồng cực tiểu.
B. Đã tìm thấy luồng cực đại.
C. Mạng không có luồng.
D. Có chu trình âm trong mạng.
19. Trong bài toán luồng cực đại, ‘lát cắt’ là gì?
A. Một đường đi từ nguồn đến đích.
B. Một tập hợp các cạnh chia đồ thị thành hai phần, một chứa nguồn và một chứa đích.
C. Một tập hợp các đỉnh trong đồ thị.
D. Một chu trình trong đồ thị.
20. Thuật toán Hungarian đượ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 ghép cặp cực đại trong đồ thị hai phía.
C. Tìm cây khung nhỏ nhất.
D. Sắp xếp các đỉnh theo thứ tự.
21. Nếu tất cả các cạnh trong đồ thị có trọng số bằng nhau, thuật toán nào sẽ hiệu quả nhất để tìm cây khung nhỏ nhất?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Tìm kiếm theo chiều rộng (BFS)
D. Thuật toán Kruskal
22. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng (BFS) trong đồ thị được biểu diễn bằng danh sách kề là bao nhiêu, với V là số đỉnh và E là số cạnh?
A. O(V)
B. O(E)
C. O(V + E)
D. O(V * E)
23. Điều kiện nào sau đây phải đúng để thuật toán Dijkstra hoạt động chính xác?
A. Đồ thị phải có hướng.
B. Đồ thị phải không có chu trình.
C. Tất cả các trọng số cạnh phải không âm.
D. Đồ thị phải là đồ thị đầy đủ.
24. Trong thuật toán Edmonds-Karp, đường tăng được chọn như thế nào?
A. Đường tăng có dung lượng lớn nhất.
B. Đường tăng ngắn nhất (ít cạnh nhất).
C. Đường tăng được chọn ngẫu nhiên.
D. Đường tăng dài nhất.
25. Thuật toán sắp xếp tô pô được sử dụng cho loại đồ thị nào?
A. Đồ thị vô hướng.
B. Đồ thị có hướng không chu trình (DAG).
C. Đồ thị đầy đủ.
D. Đồ thị có trọng số âm.
26. Ứng dụng thực tế của bài toán luồng cực đại là gì?
A. Tìm đường đi ngắn nhất trong bản đồ.
B. Lập lịch thi đấu thể thao.
C. Tìm cây khung nhỏ nhất.
D. Sắp xếp các số theo thứ tự tăng dần.
27. Độ phức tạp thời gian của thuật toán Floyd-Warshall là bao nhiêu, với V là số đỉnh?
A. O(V)
B. O(V^2)
C. O(V^3)
D. O(V log V)
28. Cây khung nhỏ nhất (Minimum Spanning Tree – MST) của một đồ thị liên thông, vô hướng, có trọng số là gì?
A. Một cây chứa tất cả các đỉnh của đồ thị với tổng trọng số cạnh là lớn nhất.
B. Một cây chứa tất cả các đỉnh của đồ thị với tổng trọng số cạnh là nhỏ nhất.
C. Một đồ thị con không chứa chu trình.
D. Một đồ thị con chứa tất cả các cạnh của đồ thị gốc.
29. Cấu trúc dữ liệu nào thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều sâu (DFS)?
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)
30. Thuật toán Floyd-Warshall được sử dụng để giải quyết vấn đề nào?
A. Tìm cây khung nhỏ nhất.
B. 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ố.
C. Sắp xếp tô pô một đồ thị.
D. Tìm luồng cực đại trong mạng.
31. Nguyên tắc cơ bản của kỹ thuật tham lam (greedy algorithm) là gì?
A. Luôn chọn phương án tốt nhất tại mỗi bước
B. Duyệt qua tất cả các phương án và chọn phương án tốt nhất
C. Chia bài toán thành các bài toán con và giải quyết chúng
D. Sử dụng heuristic để ước tính chi phí
32. Ưu điểm chính của thuật toán sắp xếp đếm (counting sort) là gì?
A. Có thể sắp xếp dữ liệu số thực
B. Có độ phức tạp thời gian tốt hơn so với các thuật toán sắp xếp so sánh trong một số trường hợp
C. Luôn ổn định (stable)
D. Yêu cầu ít bộ nhớ hơn các thuật toán sắp xếp khác
33. 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 nén dữ liệu
34. Trong bài toán cái túi (knapsack problem), mục tiêu là gì?
A. Tìm cách sắp xếp các vật phẩm vào túi sao cho tổng trọng lượng là lớn nhất
B. Tìm cách sắp xếp các vật phẩm vào túi sao cho tổng giá trị là lớn nhất mà không vượt quá trọng lượng tối đa
C. Tìm cách sắp xếp các vật phẩm vào túi sao cho số lượng vật phẩm là lớn nhất
D. Tìm cách sắp xếp các vật phẩm vào túi sao cho tổng trọng lượng là nhỏ nhất
35. Trong thuật toán sắp xếp trộn (merge sort), thao tác chính nào được sử dụng để kết hợp hai mảng con đã được sắp xếp?
A. Đổi chỗ (swapping)
B. Chèn (insertion)
C. Chọn (selection)
D. Trộn (merging)
36. Ứng dụng nào sau đây phù hợp nhất với thuật toán tìm kiếm theo chiều sâu (DFS)?
A. Tìm đường đi ngắn nhất trong một mê cung
B. Kiểm tra tính liên thông của đồ thị
C. Tìm kiếm trên một không gian trạng thái rộng lớn với chi phí thấp
D. Tìm tất cả các đường đi từ một đỉnh đến một đỉnh khác trong đồ thị
37. Sự khác biệt chính giữa tìm kiếm theo chiều rộng (BFS) và tìm kiếm theo chiều sâu (DFS) là gì?
A. BFS sử dụng hàng đợi, DFS sử dụng ngăn xếp
B. BFS sử dụng ngăn xếp, DFS sử dụng hàng đợi
C. BFS luôn tìm thấy đường đi ngắn nhất, DFS thì không
D. BFS duyệt theo chiều sâu, DFS duyệt theo chiều rộng
38. Trong thuật toán sắp xếp nhanh (quick sort), yếu tố nào ảnh hưởng lớn nhất đến hiệu suất của thuật toán?
A. Số lượng phần tử trong mảng
B. Cách chọn phần tử chốt (pivot)
C. Kích thước bộ nhớ
D. Tốc độ CPU
39. Độ 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(n log n)
C. O(n)
D. O(log n)
40. Ứng dụng chính của thuật toán tìm kiếm A* là gì?
A. Tìm đường đi ngắn nhất trong đồ thị
B. Sắp xếp dữ liệu
C. Nén dữ liệu
D. Mã hóa dữ liệu
41. Giải thuật Prim dùng để giải quyết bài toán nào?
A. Tìm cây khung nhỏ nhất
B. Tìm đường đi ngắn nhất
C. Tìm luồng cực đại trong mạng
D. Tìm khớp và cầu trong đồ thị
42. Giải thuật Kruskal dùng để giải quyết bài toán nào?
A. Tìm cây khung nhỏ nhất
B. Tìm đường đi ngắn nhất
C. Tìm luồng cực đại trong mạng
D. Tìm khớp và cầu trong đồ thị
43. Thuật toán tìm kiếm nào sau đây đảm bảo tìm thấy đường đi ngắn nhất nếu có một đường đi tồn tại?
A. Tìm kiếm leo đồi (hill climbing)
B. Tìm kiếm tham lam (greedy search)
C. Tìm kiếm theo chiều rộng (breadth-first search)
D. Tìm kiếm theo chiều sâu (depth-first search)
44. Bài toán nào sau đây thường được giải quyết bằng thuật toán tham lam?
A. Tìm đường đi ngắn nhất trong đồ thị có trọng số dương (Dijkstra)
B. Bài toán tô màu đồ thị
C. Bài toán người du lịch (traveling salesman problem)
D. Bài toán tìm cây khung nhỏ nhất (minimum spanning tree) – Kruskal
45. Thuật toán sắp xếp nào sau đây là một thuật toán sắp xếp tại chỗ (in-place sorting algorithm)?
A. Sắp xếp trộn (merge sort)
B. Sắp xếp đếm (counting sort)
C. Sắp xếp nổi bọt (bubble sort)
D. Sắp xếp cơ số (radix sort)
46. Sự khác biệt chính giữa lập trình động (dynamic programming) và kỹ thuật tham lam (greedy algorithm) là gì?
A. Lập trình động luôn tìm ra giải pháp tối ưu, tham lam thì không
B. Tham lam luôn tìm ra giải pháp tối ưu, lập trình động thì không
C. Lập trình động không sử dụng bộ nhớ, tham lam thì có
D. Tham lam không sử dụng bộ nhớ, lập trình động thì có
47. Độ phức tạp thời gian xấu nhất của thuật toán sắp xếp nổi bọt (bubble sort) là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
48. Bài toán nào sau đây thường được giải quyết bằng kỹ thuật lập trình động?
A. Tìm đường đi ngắn nhất trong đồ thị không trọng số
B. Bài toán cái túi (knapsack problem)
C. Sắp xếp một mảng số nguyên
D. Tìm kiếm một phần tử trong mảng đã sắp xếp
49. Trong thuật toán tìm kiếm nhị phân (binary search), dữ liệu đầu vào cần phải đáp ứng điều kiện 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 là duy nhất
D. Dữ liệu phải có kích thước nhỏ
50. Heuristic trong thuật toán tìm kiếm A* được sử dụng để làm gì?
A. Đảm bảo tìm thấy đường đi ngắn nhất
B. Ước tính chi phí từ một nút đến mục tiêu
C. Lưu trữ các nút đã được duyệt
D. Sắp xếp các nút theo thứ tự ưu tiên
51. 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. Sắp xếp chọn (selection sort)
B. Sắp xếp nổi bọt (bubble sort)
C. Sắp xếp chèn (insertion sort)
D. Sắp xếp trộn (merge sort)
52. Ưu điểm chính của thuật toán tìm kiếm tuyến tính (linear search) là gì?
A. Có thể tìm kiếm trên dữ liệu chưa được sắp xếp
B. Có độ phức tạp thời gian tốt hơn so với tìm kiếm nhị phân
C. Yêu cầu ít bộ nhớ hơn tìm kiếm nhị phân
D. Luôn tìm thấy phần tử cần tìm
53. Trong thuật toán tìm kiếm theo chiều sâu (depth-first search – DFS), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ các nút sẽ được duyệt?
A. Hàng đợi (queue)
B. Ngăn xếp (stack)
C. Cây (tree)
D. Đồ thị (graph)
54. Giải thuật Dijkstra dùng để giải quyết bài toán nào?
A. Tìm cây khung nhỏ nhất
B. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm
C. Tìm chu trình Hamilton
D. Tìm luồng cực đại trong mạng
55. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
56. Trong thuật toán sắp xếp cơ số (radix sort), cơ sở (radix) là gì?
A. Số lượng các phần tử trong mảng
B. Giá trị lớn nhất trong mảng
C. Hệ số mà các phần tử được chia để sắp xếp
D. Số lượng các lần lặp cần thiết để sắp xếp
57. Thuật toán sắp xếp nào sau đây thường được sử dụng để sắp xếp các mảng lớn với dữ liệu phân tán ngẫu nhiên?
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 đếm (counting sort)
58. Giải thuật Ford-Fulkerson dùng để giải quyết bài toán nào?
A. Tìm cây khung nhỏ nhất
B. Tìm đường đi ngắn nhất
C. Tìm luồng cực đại trong mạng
D. Tìm khớp và cầu trong đồ thị
59. Giải thuật Floyd-Warshall dùng để giải quyết bài toán nào?
A. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số
B. Tìm cây khung nhỏ nhất
C. Tìm luồng cực đại trong mạng
D. Tìm khớp và cầu trong đồ thị
60. Trong thuật toán tìm kiếm theo chiều rộng (breadth-first search – BFS), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ các nút sẽ được duyệt?
A. Ngăn xếp (stack)
B. Hàng đợi (queue)
C. Cây (tree)
D. Đồ thị (graph)
61. Trong thuật toán sắp xếp nhanh, kỹ thuật phân vùng (partitioning) có vai trò gì?
A. Chia mảng thành hai nửa bằng nhau
B. Tìm phần tử lớn nhất trong mảng
C. Sắp xếp mảng con bên trái và bên phải của phần tử chốt
D. Chọn phần tử chốt
62. Độ 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)
63. Nhược điểm của tìm kiếm nội suy là gì?
A. Không thể sử dụng trên các mảng đã sắp xếp
B. Độ phức tạp thời gian cao hơn trong trường hợp xấu nhất
C. Yêu cầu nhiều bộ nhớ hơn
D. Khó cài đặt hơn tìm kiếm nhị phân
64. Trong thuật toán sắp xếp trộn, quá trình nào sau đây được sử dụng để kết hợp hai mảng con đã sắp xếp?
A. Hoán đổi
B. Tìm kiếm
C. Hợp nhất
D. Chia
65. Ưu điểm của tìm kiếm nhị phân so với tìm kiếm tuyến tính là gì?
A. Dễ cài đặt hơn
B. Yêu cầu ít bộ nhớ hơn
C. Nhanh hơn cho các mảng lớn
D. Có thể được sử dụng trên các mảng chưa được sắp xếp
66. Cấu trúc dữ liệu nào sau đây phù hợp nhất để thực hiện tìm kiếm theo chiều rộng (BFS)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
67. Trong thuật toán sắp xếp trộn (merge sort), độ phức tạp thời gian tốt nhất là gì?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
68. Cấu trúc dữ liệu nào sau đây phù hợp nhất để thực hiện tìm kiếm theo chiều sâu (DFS)?
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)
69. Ứng dụng chính của tìm kiếm theo chiều rộng (BFS) là gì?
A. Tìm đường đi ngắn nhất trong một đồ thị không trọng số
B. Tìm đường đi dài nhất trong một đồ thị có trọng số
C. Tìm chu trình trong một đồ thị
D. Sắp xếp các nút trong một đồ thị
70. Khi nào thì nên sử dụng thuật toán sắp xếp trộn thay vì sắp xếp nhanh?
A. Khi bộ nhớ là một hạn chế lớn
B. Khi cần độ ổn định
C. Khi tốc độ là ưu tiên hàng đầu
D. Khi dữ liệu gần như đã được sắp xếp
71. Độ phức tạp thời gian của tìm kiếm nhị phân là gì?
A. O(n)
B. O(log n)
C. O(n log n)
D. O(1)
72. Điều kiện tiên quyết để sử dụng tìm kiếm nhị phân là gì?
A. Mảng phải được sắp xếp
B. Mảng phải chứa các số nguyên
C. Mảng phải là một mảng tĩnh
D. Mảng phải có kích thước lớn
73. Thuật toán nào sau đây thường được sử dụng để sắp xếp các danh sách liên kết?
A. Sắp xếp chọn (Selection sort)
B. Sắp xếp nổi bọt (Bubble sort)
C. Sắp xếp trộn (Merge sort)
D. Sắp xếp chèn (Insertion sort)
74. Thuật toán nào sau đây là một ví dụ về kỹ thuật ‘chia để trị’?
A. Sắp xếp chèn (Insertion sort)
B. Sắp xếp chọn (Selection sort)
C. Sắp xếp nổi bọt (Bubble sort)
D. Sắp xếp nhanh (Quick sort)
75. Thuật toán nào sau đây có độ phức tạp thời gian O(n) trong trường hợp tốt nhất?
A. Tìm kiếm nhị phân
B. Tìm kiếm nội suy
C. Tìm kiếm tuyến tính
D. Tìm kiếm theo chiều rộng
76. Thuật toán sắp xếp nào sau đây có thể được thực hiện tại chỗ (in-place)?
A. Sắp xếp trộn (Merge sort)
B. Sắp xếp đếm (Counting sort)
C. Sắp xếp nhanh (Quick sort)
D. Sắp xếp cơ số (Radix sort)
77. Tìm kiếm nội suy (interpolation search) cải thiện tìm kiếm nhị phân như thế nào?
A. Bằng cách sử dụng hàm băm
B. Bằng cách ước tính vị trí của phần tử dựa trên giá trị của nó
C. Bằng cách tìm kiếm song song
D. Bằng cách loại bỏ đệ quy
78. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trường hợp xấu nhất là O(n log n)?
A. Sắp xếp chèn (Insertion sort)
B. Sắp xếp nổi bọt (Bubble sort)
C. Sắp xếp trộn (Merge sort)
D. Sắp xếp nhanh (Quick sort)
79. Điều gì xảy ra nếu tất cả các phần tử trong mảng đã được sắp xếp trước khi áp dụng thuật toán sắp xếp nhanh?
A. Thuật toán sẽ chạy nhanh hơn
B. Thuật toán sẽ chạy chậm hơn
C. Độ phức tạp thời gian sẽ là O(n log n)
D. Thuật toán sẽ không hoạt động
80. Sự khác biệt chính giữa tìm kiếm theo chiều rộng (BFS) và tìm kiếm theo chiều sâu (DFS) là gì?
A. BFS sử dụng hàng đợi, DFS sử dụng ngăn xếp
B. BFS sử dụng ngăn xếp, DFS sử dụng hàng đợi
C. BFS nhanh hơn DFS
D. DFS nhanh hơn BFS
81. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (quick sort) là gì?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
82. Trong tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa mảng, điều gì xảy ra?
A. Tìm kiếm tiếp tục ở nửa bên phải của mảng
B. Tìm kiếm tiếp tục ở nửa bên trái của mảng
C. Phần tử được tìm thấy
D. Thuật toán kết thúc
83. Khi nào tìm kiếm tuyến tính là lựa chọn tốt hơn so với tìm kiếm nhị phân?
A. Khi mảng đã được sắp xếp
B. Khi cần tìm phần tử lớn nhất
C. Khi mảng có kích thước nhỏ
D. Khi cần tìm tất cả các phần tử trong mảng
84. Trong thuật toán sắp xếp nhanh (quick sort), lựa chọn phần tử chốt (pivot) ảnh hưởng đến điều gì?
A. Độ phức tạp không gian
B. Độ ổn định của thuật toán
C. Độ phức tạp thời gian
D. Số lượng phép so sánh
85. Khi nào tìm kiếm nội suy hoạt động tốt hơn tìm kiếm nhị phân?
A. Khi dữ liệu được phân phối không đồng đều
B. Khi dữ liệu được sắp xếp theo thứ tự ngược lại
C. Khi dữ liệu được phân phối đồng đều
D. Khi dữ liệu chứa nhiều phần tử trùng lặp
86. Ưu điểm chính của thuật toán sắp xếp trộn (merge sort) so với sắp xếp nhanh (quick sort) là gì?
A. Yêu cầu ít bộ nhớ hơn
B. Độ phức tạp thời gian trường hợp xấu nhất tốt hơn
C. Dễ cài đặt hơn
D. Chạy nhanh hơn trong thực tế
87. Nhược điểm chính của thuật toán sắp xếp nhanh là gì?
A. Độ phức tạp không gian cao
B. Độ phức tạp thời gian trường hợp xấu nhất là O(n^2)
C. Không ổn định
D. Khó cài đặt
88. Thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị có trọng số?
A. Tìm kiếm theo chiều rộng (BFS)
B. Tìm kiếm theo chiều sâu (DFS)
C. Thuật toán Dijkstra
D. Thuật toán Prim
89. Ứng dụng chính của tìm kiếm theo chiều sâu (DFS) là gì?
A. Tìm đường đi ngắn nhất trong một đồ thị
B. Kiểm tra tính liên thông của một đồ thị
C. Tìm đường đi dài nhất trong một đồ thị
D. Sắp xếp các nút trong một đồ thị
90. Thuật toán nào sau đây sử dụng chiến lược ‘chia để trị’ để tìm kiếm một phần tử trong một mảng đã sắp xếp?
A. Tìm kiếm tuyến tính
B. Tìm kiếm nhị phân
C. Tìm kiếm nội suy
D. Tìm kiếm theo chiều rộng
91. Ưu điểm chính của bảng băm (hash table) so với mảng (array) là gì?
A. Bảng băm sử dụng ít bộ nhớ hơn.
B. Bảng băm cho phép truy cập phần tử trong thời gian O(1) trung bình.
C. Bảng băm dễ cài đặt hơn.
D. Bảng băm có thể lưu trữ các phần tử có kiểu dữ liệu khác nhau.
92. Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình âm trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Kruskal
D. Thuật toán Bellman-Ford
93. Ưu điểm chính của việc sử dụng cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) so với cây tìm kiếm nhị phân không cân bằng là gì?
A. Cây cân bằng dễ cài đặt hơn.
B. Cây cân bằng luôn có số lượng nút ít hơn.
C. Cây cân bằng đảm bảo thời gian tìm kiếm, chèn và xóa phần tử là O(log n) trong trường hợp xấu nhất.
D. Cây cân bằng sử dụng ít bộ nhớ hơn.
94. Thuật toán nào sau đây có độ phức tạp thời gian O(V + E) để duyệt một đồ thị, với V là số đỉnh và E là số cạnh?
A. Thuật toán Dijkstra
B. Thuật toán Bellman-Ford
C. Tìm kiếm theo chiều sâu (DFS) và Tìm kiếm theo chiều rộng (BFS)
D. Thuật toán Floyd-Warshall
95. 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. Sắp xếp nổi bọt (Bubble sort)
B. Sắp xếp chèn (Insertion sort)
C. Sắp xếp chọn (Selection sort)
D. Sắp xếp trộn (Merge sort)
96. Thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán tìm kiếm theo chiều sâu (DFS)
C. Thuật toán Prim
D. Thuật toán tìm kiếm theo chiều rộng (BFS)
97. Độ 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)
B. O(n log n)
C. O(n^2)
D. O(log n)
98. Cây nào sau đây đảm bảo rằng khoảng cách từ gốc đến bất kỳ lá nào khác nhau không quá một?
A. Cây tìm kiếm nhị phân (Binary search tree)
B. Cây AVL
C. Cây đỏ-đen (Red-black tree)
D. Cây B
99. Trong cây tìm kiếm nhị phân, thao tác nào sau đây có độ phức tạp thời gian O(h), với h là chiều cao của cây?
A. Tìm kiếm (Search)
B. Chèn (Insert)
C. Xóa (Delete)
D. Tất cả các đáp án trên
100. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Bellman-Ford
C. Thuật toán Floyd-Warshall
D. Thuật toán Prim
101. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các đỉnh sẽ được duyệt?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
102. Thuật toán nào sau đây sử dụng kỹ thuật ‘tham lam’ (greedy) để giải quyết bài toán?
A. Tìm kiếm nhị phân (Binary search)
B. Sắp xếp trộn (Merge sort)
C. Thuật toán Dijkstra tìm đường đi ngắn nhất
D. Tìm kiếm theo chiều sâu (DFS)
103. Trong một bảng băm, hiện tượng ‘xung đột’ (collision) xảy ra khi nào?
A. Khi bảng băm đầy.
B. Khi hai khóa khác nhau được băm vào cùng một vị trí.
C. Khi một khóa được băm vào một vị trí trống.
D. Khi một khóa được băm vào một vị trí đã chứa một khóa giống hệt.
104. Cây B (B-tree) được sử dụng chủ yếu cho mục đích gì?
A. Lưu trữ dữ liệu trong bộ nhớ trong (RAM).
B. Lưu trữ dữ liệu trên đĩa cứng (disk) và tối ưu hóa số lượng truy cập đĩa.
C. Triển khai hàng đợi ưu tiên.
D. Triển khai bảng băm.
105. 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. Danh sách liên kết (Linked list)
C. Ngăn xếp (Stack)
D. Cây (Tree)
106. Trong thuật toán tìm kiếm A* (A star), hàm heuristic được sử dụng để làm gì?
A. Để đảm bảo rằng thuật toán luôn tìm thấy đường đi ngắn nhất.
B. Để ước tính khoảng cách từ một đỉnh đến đỉnh đích.
C. Để xác định thứ tự duyệt các đỉnh.
D. Để tránh duyệt lại các đỉnh đã duyệt.
107. Trong thuật toán sắp xếp nhanh (quick sort), việc chọn phần tử chốt (pivot) ảnh hưởng như thế nào đến hiệu suất của thuật toán?
A. Không ảnh hưởng.
B. Nếu phần tử chốt luôn là phần tử nhỏ nhất hoặc lớn nhất, thuật toán sẽ có hiệu suất tốt nhất.
C. Nếu phần tử chốt được chọn ngẫu nhiên, thuật toán sẽ có hiệu suất tốt nhất.
D. Nếu phần tử chốt được chọn sao cho chia mảng thành hai phần gần bằng nhau, thuật toán sẽ có hiệu suất tốt nhất.
108. Khi nào nên sử dụng danh sách liên kết (linked list) thay vì mảng (array)?
A. Khi cần truy cập ngẫu nhiên đến các phần tử.
B. Khi biết trước kích thước của dữ liệu.
C. Khi cần chèn hoặc xóa phần tử ở giữa danh sách một cách hiệu quả.
D. Mảng luôn tốt hơn danh sách liên kết.
109. Thuật toán nào sau đây có thể được sử dụng để tìm chu trình Euler trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Fleury
D. Thuật toán Kruskal
110. Độ phức tạp thời gian để tìm kiếm một phần tử trong danh sách liên kết đơn (singly linked list) là bao nhiêu trong trường hợp xấu nhất?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
111. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm sử dụng phương pháp ‘dây chuyền’ (separate chaining) để giải quyết xung đột là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
112. Trong thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị có trọng số, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ đỉnh nguồn đến các đỉnh khác?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Mảng (Array) hoặc Bảng băm (Hash table)
D. Cây (Tree)
113. Độ 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)
114. Thuật toán nào sau đây là một thuật toán chia để trị (divide and conquer)?
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 chọn (Selection sort)
D. Sắp xếp nhanh (Quick sort)
115. Thuật toán nào sau đây được sử dụng để giải bài toán luồng cực đại (maximum flow)?
A. Thuật toán Dijkstra
B. Thuật toán Ford-Fulkerson
C. Thuật toán Prim
D. Thuật toán Kruskal
116. Trong cấu trúc dữ liệu heap, phần tử lớn nhất (hoặc nhỏ nhất) luôn nằm ở đâu?
A. Ở lá ngoài cùng bên phải.
B. Ở lá ngoài cùng bên trái.
C. Ở gốc (root).
D. Ở mức giữa của heap.
117. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai 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 tìm kiếm nhị phân (Binary search tree)
D. Heap
118. Cây đỏ-đen (red-black tree) đảm bảo tính cân bằng bằng cách nào?
A. Bằng cách luôn đảm bảo rằng tất cả các lá đều ở cùng một độ sâu.
B. Bằng cách sử dụng các phép quay và tô màu lại các nút để duy trì các thuộc tính nhất định.
C. Bằng cách sắp xếp lại các nút sau mỗi lần chèn hoặc xóa.
D. Bằng cách chọn gốc một cách ngẫu nhiên.
119. Khi nào thì thuật toán sắp xếp chèn (insertion sort) hoạt động hiệu quả hơn so với thuật toán sắp xếp chọn (selection sort)?
A. Khi dữ liệu đã được sắp xếp một phần.
B. Khi dữ liệu hoàn toàn ngẫu nhiên.
C. Khi dữ liệu được sắp xếp theo thứ tự ngược lại.
D. Sắp xếp chọn luôn hiệu quả hơn sắp xếp chèn.
120. Trong thuật toán sắp xếp trộn (merge sort), giai đoạn nào chiếm phần lớn thời gian thực hiện?
A. Giai đoạn chia dãy thành các dãy con.
B. Giai đoạn so sánh các phần tử trong dãy.
C. Giai đoạn trộn (merge) các dãy con đã sắp xếp.
D. Thời gian thực hiện được phân bổ đều cho cả ba giai đoạn.
121. Chức năng chính của hàm băm (hash function) trong bảng băm là gì?
A. Sắp xếp các phần tử trong bảng.
B. Chuyển đổi khóa thành chỉ số trong bảng.
C. Tìm kiếm phần tử lớn nhất trong bảng.
D. Đếm số lượng phần tử trong bảng.
122. Cây tìm kiếm nhị phân (BST) có đặc điểm nào sau đây?
A. Mỗi nút có tối đa ba con.
B. Giá trị của nút cha lớn hơn giá trị của tất cả các nút con bên trái và nhỏ hơn giá trị của tất cả các nút con bên phải.
C. Tất cả các nút lá đều ở cùng một mức.
D. Giá trị của nút cha nhỏ hơn giá trị của tất cả các nút con bên trái và lớn hơn giá trị của tất cả các nút con bên phải.
123. Trong cấu trúc dữ liệu đồ thị, một đồ thị vô hướng liên thông là gì?
A. Đồ thị có các cạnh có hướng.
B. Đồ thị không có chu trình.
C. Đồ thị trong đó có một đường đi giữa mọi cặp đỉnh.
D. Đồ thị không có cạnh.
124. Thuật toán Dijkstra được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.
B. Tìm chu trình Euler trong đồ thị.
C. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô.
D. Tìm cây khung nhỏ nhất của đồ thị.
125. Thuật toán Kruskal được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô.
D. Tìm chu trình Hamilton trong đồ thị.
126. Hàng đợi hai đầu (deque) là gì?
A. Một hàng đợi chỉ cho phép thêm và xóa phần tử ở một đầu.
B. Một hàng đợi chỉ cho phép thêm phần tử ở một đầu và xóa phần tử ở đầu kia.
C. Một hàng đợi cho phép thêm và xóa phần tử ở cả hai đầu.
D. Một hàng đợi không cho phép thêm hoặc xóa phần tử.
127. Stack (ngăn xếp) hoạt động theo nguyên tắc nào?
A. FIFO (First-In, First-Out)
B. LIFO (Last-In, First-Out)
C. Ngẫu nhiên
D. Ưu tiên
128. Trong thuật toán sắp xếp vun đống (heap sort), cấu trúc dữ liệu nào được sử dụng?
A. Hàng đợi (queue)
B. Ngăn xếp (stack)
C. Cây nhị phân hoàn chỉnh (complete binary tree)
D. Danh sách liên kết (linked list)
129. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm sử dụng phương pháp giải quyết xung đột bằng danh sách liên kết là:
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
130. Trong cây, nút nào không có nút con được gọi là gì?
A. Nút gốc
B. Nút trung gian
C. Nút lá
D. Nút cha
131. Trong thuật toán sắp xếp trộn (merge sort), độ phức tạp thời gian tốt nhất thường là:
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
132. Ưu điểm chính của việc sử dụng bảng băm (hash table) là gì?
A. Duy trì thứ tự các phần tử.
B. Truy cập phần tử nhanh chóng (trung bình O(1)).
C. Tiết kiệm bộ nhớ tuyệt đối.
D. Dễ dàng triển khai và gỡ lỗi.
133. Độ phức tạp thời gian trung bình của thuật toán tìm kiếm nhị phân (binary search) là bao nhiêu?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(1)
134. Khi nào nên sử dụng cấu trúc dữ liệu hàng đợi ưu tiên (priority queue)?
A. Khi cần truy cập các phần tử theo thứ tự thêm vào.
B. Khi cần truy cập phần tử có độ ưu tiên cao nhất một cách nhanh chóng.
C. Khi cần sắp xếp các phần tử theo thứ tự tăng dần.
D. Khi cần tìm kiếm các phần tử một cách nhanh chóng.
135. Thuật toán Prim được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô.
D. Tìm chu trình Hamilton trong đồ thị.
136. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều sâu (DFS)?
A. Queue
B. Stack
C. Linked List
D. Heap
137. Khi nào nên sử dụng danh sách liên kết (linked list) thay vì mảng (array)?
A. Khi cần truy cập các phần tử một cách ngẫu nhiên với thời gian O(1).
B. Khi kích thước của dữ liệu không thay đổi.
C. Khi cần chèn hoặc xóa các phần tử ở giữa danh sách một cách thường xuyên.
D. Khi cần tiết kiệm bộ nhớ một cách tối đa.
138. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều rộng (BFS)?
A. Stack
B. Queue
C. Linked List
D. Tree
139. Độ phức tạp thời gian của thao tác chèn vào đầu danh sách liên kết đơn (singly linked list) là:
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
140. Trong cây, nút nào chỉ có một nút cha?
A. Nút gốc
B. Nút lá
C. Tất cả các nút trừ nút gốc
D. Tất cả các nút
141. Trong cây tìm kiếm nhị phân, phép duyệt nào sau đây sẽ cho ra các nút theo thứ tự tăng dần?
A. Duyệt trước (preorder)
B. Duyệt sau (postorder)
C. Duyệt giữa (inorder)
D. Duyệt theo mức (level order)
142. Khi nào nên sử dụng thuật toán sắp xếp chèn (insertion sort)?
A. Khi dữ liệu đã gần được sắp xếp.
B. Khi cần sắp xếp một lượng lớn dữ liệu.
C. Khi cần sắp xếp dữ liệu trên đĩa.
D. Khi cần sắp xếp dữ liệu một cách ngẫu nhiên.
143. Điều gì xảy ra khi bạn cố gắng lấy một phần tử từ một hàng đợi (queue) trống?
A. Trả về giá trị mặc định (ví dụ: 0 hoặc null).
B. Gây ra lỗi ‘tràn hàng đợi’.
C. Gây ra lỗi ‘hàng đợi rỗng’ (underflow).
D. Tự động thêm một phần tử mới vào hàng đợi.
144. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp nổi bọt (bubble sort) là:
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(1)
145. Trong cấu trúc dữ liệu đồ thị, một chu trình Euler là gì?
A. Một đường đi đi qua tất cả các đỉnh của đồ thị một lần.
B. Một đường đi đi qua tất cả các cạnh của đồ thị một lần.
C. Một đường đi ngắn nhất giữa hai đỉnh.
D. Một đường đi dài nhất trong đồ thị.
146. Độ phức tạp thời gian của thao tác tìm kiếm trong cây tìm kiếm nhị phân cân bằng (ví dụ: cây AVL, cây đỏ-đen) là:
A. O(n)
B. O(n log n)
C. O(1)
D. O(log n)
147. Cây khung nhỏ nhất (Minimum Spanning Tree) của một đồ thị là gì?
A. Cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là lớn nhất.
B. Cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất.
C. Cây bao gồm một phần các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất.
D. Cây bao gồm một phần các đỉnh của đồ thị và có tổng trọng số các cạnh là lớn nhất.
148. Thuật toán nào sau đây là một thuật toán chia để trị?
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 chọn (selection sort)
D. Sắp xếp nhanh (quick sort)
149. Trong đồ thị có hướng, thành phần liên thông mạnh (strongly connected component) là gì?
A. Một tập hợp các đỉnh mà giữa bất kỳ hai đỉnh nào cũng có đường đi đến nhau.
B. Một tập hợp các đỉnh mà không có đường đi giữa bất kỳ hai đỉnh nào.
C. Một tập hợp các đỉnh mà chỉ có đường đi một chiều giữa chúng.
D. Một tập hợp các đỉnh mà tất cả các đỉnh đều có bậc vào bằng bậc ra.
150. Trong cây, nút nào không có nút cha được gọi là gì?
A. Nút gốc
B. Nút lá
C. Nút trung gian
D. Nút con
