1. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt bộ nhớ cache?
A. Mảng
B. Danh sách liên kết
C. Hash Table
D. Cây
2. Trong thuật toán duyệt cây theo thứ tự trước (Preorder Traversal), thứ tự duyệt các nút là gì?
A. Gốc – Trái – Phải
B. Trái – Gốc – Phải
C. Trái – Phải – Gốc
D. Phải – Gốc – Trái
3. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn một mạng xã hội?
A. Mảng
B. Danh sách liên kết
C. Đồ thị
D. Cây
4. Kỹ thuật nào sau đây được sử dụng để giải quyết xung đột trong hash table?
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 cây (Tree Traversal)
5. Trong một cây AVL, thao tác nào được sử dụng để duy trì tính cân bằng sau khi chèn hoặc xóa một nút?
A. Sắp xếp
B. Xoay
C. Tìm kiếm
D. Băm
6. Trong thuật toán Prim, cấu trúc dữ liệu nào được sử dụng để lưu trữ các cạnh có thể thêm vào cây khung nhỏ nhất?
A. Stack
B. Queue
C. Heap
D. Linked List
7. 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. Queue
B. Heap
C. Stack
D. Linked List
8. Trong thuật toán Quick Sort, phần tử nào được sử dụng để phân vùng mảng?
A. Phần tử đầu tiên
B. Phần tử cuối cùng
C. Phần tử ngẫu nhiên
D. Tất cả các đáp án trên
9. Ưu điểm của việc sử dụng 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. Sử dụng ít bộ nhớ hơn
B. Duyệt theo cả hai hướng
C. Chèn và xóa phần tử nhanh hơn
D. Tìm kiếm nhanh hơn
10. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong một cây nhị phân tìm kiếm cân bằng là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
11. Trong thuật toán Bellman-Ford, mục đích chính của việc lặp lại các cạnh trong đồ thị là gì?
A. Tìm chu trình âm
B. Tìm đường đi ngắn nhất
C. Sắp xếp các đỉnh
D. Tìm cây khung nhỏ nhất
12. Trong thuật toán sắp xếp Merge Sort, quá trình chia mảng ban đầu thành các mảng con được thực hiện như thế nào?
A. Chia ngẫu nhiên
B. Chia theo thứ tự tăng dần
C. Chia đệ quy cho đến khi mỗi mảng con chỉ có một phần tử
D. Chia theo thứ tự giảm dần
13. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt 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
14. 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ử?
A. Linked List
B. Queue
C. Stack
D. Array
15. Độ phức tạp thời gian trung bình để chèn một phần tử vào một hash table là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
16. Khi nào nên sử dụng cấu trúc dữ liệu đồ thị thay vì cây?
A. Khi cần biểu diễn mối quan hệ phân cấp
B. Khi cần biểu diễn mối quan hệ phức tạp giữa các đối tượng mà không có thứ tự phân cấp rõ ràng
C. Khi cần tìm kiếm nhanh chóng
D. Khi cần sắp xếp dữ liệu
17. Thuật toán nào sau đây thường được sử dụng để duyệt cây theo chiều rộng (Breadth-First Search)?
A. Đệ quy
B. Stack
C. Queue
D. Heap
18. Độ 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(log n)
C. O(1)
D. O(n^2)
19. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất?
A. Stack
B. Queue
C. Heap
D. Linked List
20. Trong một đồ thị có trọng số, 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?
A. Dijkstra
B. Bellman-Ford
C. Floyd-Warshall
D. Prim
21. Cấu trúc dữ liệu nào sau đây có thể được sử dụng để kiểm tra xem một biểu thức toán học có cân bằng dấu ngoặc hay không?
A. Queue
B. Stack
C. Linked List
D. Heap
22. Trong thuật toán Kruskal, làm thế nào để xác định xem hai đỉnh có thuộc cùng một tập hợp hay không?
A. Sử dụng tìm kiếm nhị phân
B. Sử dụng cấu trúc dữ liệu Union-Find
C. Sử dụng sắp xếp
D. Sử dụng băm
23. Ưu điểm chính của việc sử dụng cây nhị phân tìm kiếm (Binary Search Tree) so với mảng là gì?
A. Tìm kiếm nhanh hơn trong mọi trường hợp
B. Chèn và xóa phần tử nhanh hơn
C. Sử dụng ít bộ nhớ hơn
D. Dễ dàng duyệt qua tất cả các phần tử hơn
24. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ ‘cha-con’ trong một gia đình?
A. Mảng
B. Danh sách liên kết
C. Cây
D. Hash Table
25. Cấu trúc dữ liệu nào sau đây cho phép chèn và xóa phần tử ở cả hai đầu?
A. Stack
B. Queue
C. Deque
D. Linked List
26. Thuật toán nào sau đây thường được sử dụng để tìm chu trình trong đồ thị?
A. Tìm kiếm tuyến tính (Linear Search)
B. Tìm kiếm theo chiều sâu (Depth-First Search)
C. Tìm kiếm theo chiều rộng (Breadth-First Search)
D. Sắp xếp nổi bọt (Bubble Sort)
27. Một cây khung nhỏ nhất (Minimum Spanning Tree) của một đồ thị liên thông có trọng số là gì?
A. Một cây bao gồm tất cả các đỉnh của đồ thị với tổng trọng số cạnh lớn nhất
B. Một cây bao gồm tất cả các đỉnh của đồ thị với tổng trọng số cạnh nhỏ nhất
C. Một đồ thị con của đồ thị ban đầu
D. Một đường đi ngắn nhất giữa hai đỉnh
28. Trong một cây quyết định, nút lá đại diện cho điều gì?
A. Một thuộc tính để kiểm tra
B. Một quyết định hoặc kết quả
C. Một nhánh của cây
D. Một tập hợp các thuộc tính
29. Cây đỏ đen (Red-Black Tree) là một loại cây gì?
A. Cây tìm kiếm nhị phân không cân bằng
B. Cây tìm kiếm nhị phân cân bằng
C. Cây quyết định
D. Cây khung nhỏ nhất
30. Trong cây nhị phân, nút nào là tổ tiên của tất cả các nút khác?
A. Nút lá
B. Nút gốc
C. Nút trong
D. Nút con
31. Trong các thuật toán sắp xếp sau, thuật toán nào thường được sử dụng trong thực tế khi cần sắp xếp một mảng lớn?
A. Bubble Sort
B. Insertion Sort
C. Quick Sort
D. Selection Sort
32. 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. Merge Sort
B. Quick Sort
C. Counting Sort
D. Radix Sort
33. Cho một mảng đã được sắp xếp, thuật toán nào sau đây hiệu quả nhất để tìm kiếm một phần tử?
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 theo chiều sâu (DFS)
D. Tìm kiếm theo chiều rộng (BFS)
34. Cho đồ thị G có V đỉnh và E cạnh, độ phức tạp thời gian của thuật toán Kruskal để tìm cây khung nhỏ nhất (Minimum Spanning Tree) là bao nhiêu?
A. O(V)
B. O(E)
C. O(E log V)
D. O(V log E)
35. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất trong một đồ thị có trọng số không âm?
A. Tìm kiếm theo chiều sâu (DFS)
B. Tìm kiếm theo chiều rộng (BFS)
C. Thuật toán Dijkstra
D. Thuật toán Prim
36. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu hàng đợi (Queue)?
A. Quản lý các cuộc gọi đến trong tổng đài điện thoại
B. Hoàn tác (Undo) trong trình soạn thảo văn bản
C. Duyệt cây theo chiều sâu (DFS)
D. Tính toán biểu thức số học
37. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt hàng đợi ưu tiên?
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
38. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt thuật toán LFU (Least Frequently Used) cache?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Heap kết hợp với bảng băm
D. Cây nhị phân tìm kiếm (Binary Search Tree)
39. Trong các cấu trúc dữ liệu sau, cấu trúc nào thích hợp nhất để kiểm tra một biểu thức ngoặc có hợp lệ hay không (ví dụ: ‘(){}[]’)?
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)
40. Trong cây nhị phân, chiều cao của cây được định nghĩa là gì?
A. Số lượng nút trên đường đi dài nhất từ gốc đến một nút lá
B. Số lượng cạnh trên đường đi dài nhất từ gốc đến một nút lá
C. Số lượng nút trong cây
D. Số lượng lá trong cây
41. Độ 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) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n log n)
D. O(1)
42. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (DFS) thay vì tìm kiếm theo chiều rộng (BFS)?
A. Khi cần tìm đường đi ngắn nhất
B. Khi không gian tìm kiếm rất lớn và chiều sâu của cây tìm kiếm không bị giới hạn
C. Khi cần duyệt tất cả các đỉnh của đồ thị
D. Khi biết trước mục tiêu tìm kiếm nằm gần đỉnh bắt đầu
43. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu đồ thị?
A. Quản lý danh sách sinh viên
B. Lưu trữ dữ liệu cấu hình của hệ điều hành
C. Mạng xã hội (Social Network)
D. Quản lý hàng đợi in
44. 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 xấu nhất là O(n)?
A. Tìm kiếm một phần tử
B. Chèn một phần tử
C. Xóa một phần tử
D. Tất cả các đáp án trên
45. Thuật toán 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. Insertion Sort
C. Tìm kiếm theo chiều sâu (DFS)
D. Merge Sort
46. 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
47. Trong ngữ cảnh của đồ thị, chu trình Euler là gì?
A. Đường đi qua tất cả các đỉnh của đồ thị đúng một lần
B. Đường đi qua tất cả các cạnh của đồ thị đúng một lần
C. Đường đi ngắn nhất giữa hai đỉnh
D. Đường đi dài nhất giữa hai đỉnh
48. Ư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ủa các phần tử
B. Tìm kiếm, chèn và xóa phần tử với độ phức tạp thời gian trung bình là O(1)
C. Sử dụng ít bộ nhớ hơn so với các cấu trúc dữ liệu khác
D. Dễ dàng cài đặt
49. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ cha-con trong một tổ chức?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Bảng băm (Hash Table)
50. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử đầu tiên và phần tử cuối cùng trong thời gian O(1)?
A. Mảng (Array)
B. Danh sách liên kết đơn (Singly Linked List)
C. Danh sách liên kết kép (Doubly Linked List)
D. Hàng đợi (Queue) cài đặt bằng mảng vòng
51. Cho một đồ thị vô hướng liên thông, phát biểu nào sau đây là đúng?
A. Luôn tồn tại một chu trình Euler
B. Luôn tồn tại một đường đi Hamilton
C. Luôn tồn tại một cây khung (spanning tree)
D. Không thể có chu trình
52. Trong các thuật toán sắp xếp sau, thuật toán nào 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
53. Độ phức tạp thời gian 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?
A. Kích thước của bảng băm
B. Hàm băm (hash function) và phương pháp giải quyết xung đột
C. Số lượng phần tử trong bảng băm
D. Thứ tự của các phần tử trong bảng băm
54. 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
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 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ớ
55. Độ 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)
56. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất, trung bình và xấu nhất đều là O(n log n)?
A. Quick Sort
B. Heap Sort
C. Insertion Sort
D. Bubble Sort
57. Trong 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ó cùng giá trị băm
C. Khi một khóa không có giá trị băm
D. Khi một khóa có giá trị băm âm
58. Thuật toán nào sau đây là một thuật toán chia để trị (Divide and Conquer)?
A. Bubble Sort
B. Insertion Sort
C. Quick Sort
D. Selection Sort
59. 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 (Tree)
60. Ưu điểm của việc sử dụng cây tìm kiếm cân bằng (ví dụ: AVL tree, Red-Black tree) so với cây nhị phân tìm kiếm thông thường là gì?
A. Dễ cài đặt hơn
B. Sử dụng ít bộ nhớ hơn
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 và xóa
D. Cho phép duyệt cây theo thứ tự nhanh hơn
61. Độ phức tạp thời gian của thuật toán Dijkstra (sử dụng priority queue) để 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ị là bao nhiêu (với V là số đỉnh và E là số cạnh)?
A. O(V^2)
B. O(E)
C. O(V + E)
D. O(E log V)
62. Phương pháp nào sau đây thường được sử dụng để giải quyết các bài toán tối ưu hóa trên đồ thị, như tìm đường đi ngắn nhất?
A. Brute force
B. Divide and conquer
C. Dynamic programming
D. Random search
63. Cho một đồ thị có trọng số, thuật toán Floyd-Warshall được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh cụ thể.
B. Tìm cây khung nhỏ nhất.
C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.
D. Tìm chu trình Euler.
64. Ứng dụng nào sau đây thể hiện việc sử dụng đồ thị có trọng số âm?
A. Tìm đường đi ngắn nhất giữa các thành phố với khoảng cách là trọng số.
B. Biểu diễn mạng xã hội với số lượng bạn bè là trọng số.
C. Phân tích chu kỳ kinh doanh, trong đó lợi nhuận và thua lỗ được biểu diễn bằng trọng số.
D. Lập lịch trình các công việc với thời gian hoàn thành là trọng số.
65. Cho một đồ thị vô hướng liên thông có 6 đỉnh và 8 cạnh. Số lượng cạnh tối thiểu cần loại bỏ để đồ thị trở thành cây là bao nhiêu?
66. Nếu bạn cần tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có số lượng đỉnh lớn (hàng ngàn đỉnh) và số lượng cạnh tương đối ít (sparse graph), thuật toán nào sẽ hiệu quả hơn: Dijkstra chạy từ mỗi đỉnh hay Floyd-Warshall?
A. Dijkstra chạy từ mỗi đỉnh.
B. Floyd-Warshall.
C. Cả hai đều hiệu quả như nhau.
D. Không thể xác định.
67. Bài toán ‘Người du lịch’ (Traveling Salesperson Problem – TSP) thuộc loại bài toán nào?
A. Bài toán P.
B. Bài toán NP.
C. Bài toán NP-complete.
D. Bài toán dễ (tractable).
68. Trong bài toán tô màu đồ thị, mục tiêu là gì?
A. Tìm số lượng thành phần liên thông trong đồ thị.
B. Tìm một chu trình Hamilton trong đồ thị.
C. Gán màu cho các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau có cùng màu.
D. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
69. Trong thuật toán Dijkstra, 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 và chọn đỉnh có khoảng cách nhỏ nhất để xét tiếp theo?
A. Stack
B. Queue
C. Priority queue
D. Linked list
70. Trong thuật toán Kruskal, cấu trúc dữ liệu disjoint set (union-find) được sử dụng để làm gì?
A. Lưu trữ các cạnh đã được chọn vào cây khung nhỏ nhất.
B. Kiểm tra xem hai đỉnh có thuộc cùng một thành phần liên thông hay không.
C. Sắp xếp các cạnh theo trọng số.
D. Tìm đường đi ngắn nhất giữa hai đỉnh.
71. Trong thuật toán Prim, việc lựa chọn đỉnh tiếp theo để thêm vào cây khung nhỏ nhất dựa trên tiêu chí nào?
A. Đỉnh có bậc cao nhất.
B. Đỉnh có trọng số cạnh nhỏ nhất nối với cây hiện tại.
C. Đỉnh được duyệt đến đầu tiên.
D. Đỉnh có khoảng cách xa nhất từ cây hiện tại.
72. Trong thuật toán Ford-Fulkerson, ‘đường tăng luồng’ (augmenting path) là gì?
A. Đường đi ngắn nhất từ đỉnh nguồn đến đỉnh đích.
B. Đường đi từ đỉnh nguồn đến đỉnh đích có thể tăng thêm luồng.
C. Đường đi có luồng lớn nhất từ đỉnh nguồn đến đỉnh đích.
D. Đường đi duy nhất từ đỉnh nguồn đến đỉnh đích.
73. Cho một đồ thị đầy đủ (complete graph) có n đỉnh. Số lượng cạnh của đồ thị này là bao nhiêu?
A. n
B. n – 1
C. n(n – 1) / 2
D. n^2
74. Khi nào thì thuật toán Dijkstra không thể áp dụng để tìm đường đi ngắn nhất?
A. Khi đồ thị là đồ thị có hướng.
B. Khi đồ thị có trọng số âm.
C. Khi đồ thị là đồ thị không liên thông.
D. Khi đồ thị có chu trình.
75. Trong bài toán luồng cực đại (maximum flow), lát cắt (cut) của đồ thị là gì?
A. Một đường đi từ đỉnh nguồn đến đỉnh đích.
B. Một tập hợp các cạnh có tổng trọng số nhỏ nhất.
C. Một cách chia tập đỉnh thành hai tập hợp, trong đó một tập chứa đỉnh nguồn và tập còn lại chứa đỉnh đích.
D. Một chu trình trong đồ thị.
76. Trong một đồ thị có hướng, một đỉnh được gọi là ‘sink’ nếu nó có tính chất gì?
A. Không có cạnh đi vào.
B. Không có cạnh đi ra.
C. Có số lượng cạnh đi vào bằng số lượng cạnh đi ra.
D. Có bậc cao nhất trong đồ thị.
77. Cho một đồ thị có 5 đỉnh, mỗi đỉnh có bậc là 2. Đồ thị này có thể là gì?
A. Một cây.
B. Một đồ thị đầy đủ.
C. Một chu trình.
D. Một đồ thị không liên thông.
78. Trong một đồ thị có hướng, một 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 hai đỉnh bất kỳ đều có đường đi đến nhau.
B. Một tập hợp các đỉnh mà không có đường đi giữa hai đỉnh bất kỳ.
C. Một tập hợp các đỉnh mà chỉ có một đường đi duy nhất giữa hai đỉnh bất kỳ.
D. Một tập hợp tất cả các đỉnh của đồ thị.
79. Trong bài toán tìm chu trình Euler, điều kiện cần và đủ để một đồ thị có chu trình Euler là gì?
A. Đồ thị phải liên thông và có ít nhất một đỉnh bậc lẻ.
B. Đồ thị phải liên thông và tất cả các đỉnh phải có bậc chẵn.
C. Đồ thị phải là đồ thị đầy đủ.
D. Đồ thị phải là một cây.
80. Khi nào thì thuật toán Bellman-Ford được ưu tiên sử dụng hơn thuật toán Dijkstra?
A. Khi đồ thị có số lượng đỉnh rất lớn.
B. Khi đồ thị không có chu trình.
C. Khi đồ thị có cạnh trọng số âm.
D. Khi cần tìm đường đi ngắn nhất giữa hai đỉnh cụ thể.
81. Thuật toán nào sau đây thường được sử dụng để tìm các thành phần liên thông mạnh trong một đồ thị có hướng?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Kosaraju
D. Thuật toán Floyd-Warshall
82. Trong bài toán tô màu đồ thị, số màu sắc tối thiểu cần thiết để tô màu một đồ thị được gọi là gì?
A. Bậc của đồ thị.
B. Số cạnh của đồ thị.
C. Số màu sắc của đồ thị.
D. Số chromatic của đồ thị.
83. Thuật toán Prim và Kruskal đều được sử dụng để tìm cây khung nhỏ nhất của một đồ thị. Điểm khác biệt chính giữa hai thuật toán này là gì?
A. Prim bắt đầu từ một đỉnh, Kruskal bắt đầu từ cạnh có trọng số nhỏ nhất.
B. Prim sử dụng cấu trúc dữ liệu heap, Kruskal sử dụng cấu trúc dữ liệu disjoint set.
C. Prim luôn tạo ra một cây liên thông, Kruskal có thể tạo ra nhiều cây con trước khi hợp nhất.
D. Prim chỉ áp dụng cho đồ thị có hướng, Kruskal chỉ áp dụng cho đồ thị vô hướng.
84. Trong bài toán luồng cực đại, định lý Max-Flow Min-Cut phát biểu điều gì?
A. Luồng cực đại bằng tổng trọng số các cạnh.
B. Luồng cực đại bằng dung lượng nhỏ nhất của một lát cắt.
C. Luồng cực đại luôn lớn hơn dung lượng của mọi lát cắt.
D. Luồng cực đại luôn nhỏ hơn dung lượng của mọi lát cắt.
85. Thuật toán Bellman-Ford được sử dụng để giải quyết bài toán nào và có ưu điểm gì so với thuật toán Dijkstra?
A. Tìm cây khung nhỏ nhất, ưu điểm là đơn giản hơn Dijkstra.
B. Tìm đường đi ngắn nhất, ưu điểm là xử lý được đồ thị có cạnh âm.
C. Tìm luồng cực đại, ưu điểm là nhanh hơn Dijkstra.
D. Tìm chu trình Hamilton, ưu điểm là dễ cài đặt hơn Dijkstra.
86. Ứng dụng thực tế nào sau đây thể hiện việc sử dụng thuật toán tìm cây khung nhỏ nhất?
A. Tìm đường đi ngắn nhất trên bản đồ.
B. Kết nối các máy tính trong mạng với chi phí dây cáp tối thiểu.
C. Lập lịch trình sản xuất trong nhà máy.
D. Tìm đường đi cho robot hút bụi.
87. Thuật toán Ford-Fulkerson được sử 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 chu trình Hamilton.
88. Ứng dụng thực tế nào sau đây không phù hợp với thuật toán tìm đường đi ngắn nhất?
A. Tìm đường đi nhanh nhất trên bản đồ.
B. Định tuyến gói tin trên mạng Internet.
C. Lập lịch trình sản xuất trong nhà máy.
D. Tìm đường đi cho robot hút bụi.
89. Cho một đồ thị biểu diễn mạng lưới giao thông, với các đỉnh là các thành phố và các cạnh là các con đường. Nếu bạn muốn tìm tất cả các thành phố có thể đến được từ một thành phố xuất phát, thuật toán nào sẽ phù hợp 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.
90. Trong thuật toán tìm kiếm theo chiều sâu (DFS) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh sẽ được duyệt?
A. Queue
B. Stack
C. Priority Queue
D. Heap
91. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (binary search tree), điều kiện nào sau đây luôn đúng với mọi nút?
A. Giá trị của nút lớn hơn tất cả các nút con bên trái và nhỏ hơn tất cả các nút con bên phải
B. Giá trị của nút nhỏ hơn tất cả các nút con bên trái và lớn hơn tất cả các nút con bên phải
C. Giá trị của nút lớn hơn hoặc bằng tất cả các nút con bên trái và nhỏ hơn hoặc bằng tất cả các nút con bên phải
D. Giá trị của nút lớn hơn tất cả các nút con bên phải và nhỏ hơn tất cả các nút con bên trái
92. Ưu điểm của việc sử dụng cây so với danh sách liên kết (linked list) để lưu trữ dữ liệu là gì?
A. Cây sử dụng ít bộ nhớ hơn
B. Cây cho phép tìm kiếm, chèn và xóa nhanh hơn trong nhiều trường hợp
C. Cây dễ cài đặt hơn
D. Cây có thể lưu trữ dữ liệu tuần tự tốt hơn
93. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một từ có phải là palindrome (đọc xuôi ngược như nhau) hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Mảng (Array)
D. Danh sách liên kết (Linked List)
94. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong bảng băm (hash table) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
95. Trong bảng băm (hash table), phương pháp 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. Địa chỉ mở (Open Addressing)
C. Tìm kiếm nhị phân (Binary Search)
D. Đệ quy (Recursion)
96. Thuật toán nào sau đây được sử dụng để duyệt cây theo thứ tự trước (preorder traversal)?
A. Duyệt nút gốc, sau đó duyệt cây con trái, sau đó duyệt cây con phải
B. Duyệt cây con trái, sau đó duyệt nút gốc, sau đó duyệt cây con phải
C. Duyệt cây con trái, sau đó duyệt cây con phải, sau đó duyệt nút gốc
D. Duyệt theo chiều rộng
97. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt hàng đợi (queue)?
A. Cây nhị phân tìm kiếm
B. Đồ thị
C. Mảng (array) hoặc danh sách liên kết (linked list)
D. Bảng băm (hash table)
98. 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)
99. Thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong một đồ thị có trọng số không âm?
A. Tìm kiếm theo chiều sâu (Depth-First Search)
B. Tìm kiếm theo chiều rộng (Breadth-First Search)
C. Thuật toán Dijkstra
D. Thuật toán Prim
100. Khi nào nên sử dụng thuật toán sắp xếp nhanh (quick sort) thay vì sắp xếp trộn (merge sort)?
A. Khi cần đảm bảo độ ổn định của thuật toán sắp xếp
B. Khi dữ liệu gần như đã được sắp xếp
C. Khi yêu cầu bộ nhớ phụ là một vấn đề quan trọng
D. Khi cần độ phức tạp thời gian tốt nhất trong mọi trường hợp
101. Trong thuật toán sắp xếp, thuật toán nào có độ phức tạp thời gian trung bình là O(n^2)?
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 vun đống (Heap Sort)
102. Ứng dụng thực tế nào sau đây sử dụng cấu trúc dữ liệu đồ thị (graph)?
A. Quản lý danh sách liên lạc trong điện thoại
B. Tính toán đường đi ngắn nhất giữa hai thành phố trên bản đồ
C. Lưu trữ dữ liệu về sản phẩm trong một cửa hàng
D. Quản lý danh sách các việc cần làm
103. Thuật toán nào sau đây có thể đượ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. Tìm kiếm nhị phân (Binary Search)
B. Tìm kiếm tuyến tính (Linear Search)
C. Sắp xếp nhanh (Quick Sort)
D. Sắp xếp trộn (Merge Sort)
104. Trong bảng băm (hash table), ‘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 (hash) vào cùng một vị trí
C. Khi một khóa không tồn tại trong bảng băm
D. Khi một phần tử bị xóa khỏi bảng băm
105. Trong cấu trúc dữ liệu cây, nút gốc (root) là gì?
A. Nút có nhiều con nhất
B. Nút không có cha
C. Nút nằm ở mức sâu nhất
D. Nút có giá trị lớn nhất
106. Trong cây nhị phân, ‘chiều cao’ của cây được định nghĩa là gì?
A. Số lượng nút trong cây
B. Độ dài đường đi dài nhất từ nút gốc đến nút lá
C. Số lượng nút lá trong cây
D. Độ dài đường đi ngắn nhất từ nút gốc đến nút lá
107. 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 có kích thước lớn và không gần như đã được sắp xếp
B. Khi cần sắp xếp dữ liệu trực tuyến (online)
C. Khi cần đảm bảo độ 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 dữ liệu trên đĩa cứng
108. Trong cấu trúc dữ liệu đồ thị (graph), sự khác biệt chính giữa đồ thị có hướng (directed graph) và đồ thị vô hướng (undirected graph) là gì?
A. Đồ thị có hướng có trọng số, đồ thị vô hướng thì không
B. Các cạnh trong đồ thị có hướng có hướng, trong khi các cạnh trong đồ thị vô hướng thì không
C. Đồ thị vô hướng có thể chứa chu trình, đồ thị có hướng thì không
D. Đồ thị có hướng luôn có số lượng đỉnh lớn hơn đồ thị vô hướng
109. Ư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 khi kích thước đã biết trước
C. Dễ dàng chèn và xóa phần tử ở giữa danh sách
D. Tìm kiếm phần tử nhanh hơn
110. Thuật toán nào sau đây thường được sử dụng để duyệt cây theo chiều rộng (breadth-first traversal)?
A. Đệ quy
B. Sử dụng ngăn xếp (stack)
C. Sử dụng hàng đợi (queue)
D. Sử dụng danh sách liên kết
111. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai chức năng ‘undo’ trong một trình soạn thảo văn bản?
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)
112. 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
C. Khi cần truy cập ngẫu nhiên vào các phần tử
D. Khi cần chèn phần tử vào đầu danh sách
113. Ứng dụng thực tế nào sau đây sử dụng cấu trúc dữ liệu hàng đợi (queue)?
A. Quản lý các cuộc gọi đến trong tổng đài điện thoại
B. Quản lý lịch sử duyệt web
C. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức
D. Tìm kiếm đường đi trong mê cung
114. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để phát hiện chu trình (cycle) trong đồ thị có hướng?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Tìm kiếm theo chiều sâu (Depth-First Search)
D. Tìm kiếm theo chiều rộng (Breadth-First Search)
115. 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. Thuật toán Dijkstra
B. Thuật toán Floyd-Warshall
C. Thuật toán Kruskal
D. Tìm kiếm theo chiều sâu (Depth-First Search)
116. Trong thuật toán sắp xếp trộn (merge sort), độ phức tạp thời gian là bao nhiêu?
A. O(n^2)
B. O(log n)
C. O(n log n)
D. O(n)
117. Độ 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(log n)
C. O(1)
D. O(n^2)
118. Trong cấu trúc dữ liệu cây, nút lá (leaf node) là gì?
A. Nút có giá trị lớn nhất
B. Nút không có con
C. Nút nằm ở mức cao nhất
D. Nút có nhiều cha nhất
119. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp, chẳng hạn như cây thư mục trong hệ điều hành?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Bảng băm (Hash Table)
120. Khái niệm ‘đệ quy’ (recursion) trong lập trình là gì?
A. Một vòng lặp vô hạn
B. Một hàm gọi chính nó
C. Một biến toàn cục
D. Một cấu trúc dữ liệu phức tạp
121. 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)
122. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt 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
123. Khi nào thì việc sử dụng bảng băm (Hash Table) là không phù hợp?
A. Khi cần tìm kiếm nhanh
B. Khi cần lưu trữ một lượng lớn dữ liệu
C. Khi cần duy trì thứ tự của các phần tử
D. Khi cần kiểm tra sự tồn tại của một phần tử
124. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (DFS) thay vì tìm kiếm theo chiều rộng (BFS)?
A. Khi cần tìm đường đi ngắn nhất
B. Khi không gian tìm kiếm rất lớn và chiều sâu không giới hạn
C. Khi cần duyệt tất cả các đỉnh
D. Khi biết trước mục tiêu nằm gần gốc
125. Trong cấu trúc dữ liệu đồ thị, thuật ngữ ‘đỉnh cô lập’ (isolated vertex) dùng để chỉ điều gì?
A. Đỉnh có bậc bằng 0
B. Đỉnh có bậc lớn nhất
C. Đỉnh nằm ở trung tâm của đồ thị
D. Đỉnh có đường đi ngắn nhất đến tất cả các đỉnh khác
126. 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ử?
A. Danh sách liên kết đơn (Singly Linked List)
B. Hàng đợi (Queue)
C. Mảng (Array)
D. Ngăn xếp (Stack)
127. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất là O(n)?
A. Quick Sort
B. Merge Sort
C. Counting Sort
D. Insertion Sort
128. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong cây nhị phân tìm kiếm cân bằng (Balanced Binary Search Tree) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
129. Độ phức tạp thời gian của thuật toán sắp xếp chèn (Insertion Sort) trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(n log n)
130. Ư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 khi kích thước không xác định trước
C. Tìm kiếm nhanh hơn
D. Sắp xếp dễ dàng hơn
131. Trong cấu trúc dữ liệu đồ thị, thuật toán nào được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm?
A. Breadth-First Search (BFS)
B. Depth-First Search (DFS)
C. Dijkstra
D. Prim
132. Trong thuật toán Prim, cấu trúc dữ liệu nào thường được sử dụng để chọn cạnh có trọng số nhỏ nhất?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Heap
D. Mảng
133. 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. Mảng
B. Ngăn xếp (Stack)
C. Hàng đợi (Queue)
D. Danh sách liên kết
134. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn một mạng xã hội?
A. Mảng
B. Danh sách liên kết
C. Đồ thị
D. Cây
135. Trong thuật toán tìm kiếm nhị phân (Binary Search), điều kiện tiên quyết là gì?
A. Mảng phải được sắp xếp
B. Mảng không được chứa các phần tử trùng lặp
C. Mảng phải có kích thước cố định
D. Mảng phải chứa các số nguyên
136. 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. Chia mảng thành các mảng con
B. So sánh các phần tử
C. Trộn các mảng con đã sắp xếp
D. Hoán đổi các phần tử
137. Ứng dụng nào sau đây phù hợp nhất với cấu trúc dữ liệu hàng đợi (Queue)?
A. Quản lý các cuộc gọi đến tổng đài
B. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức
C. Duyệt cây theo chiều sâu (Depth-First Search)
D. Tìm đường đi ngắn nhất trên đồ thị
138. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt bộ nhớ cache?
A. Mảng
B. Danh sách liên kết
C. Bảng băm
D. Cây
139. Trong cấu trúc dữ liệu cây, thuật ngữ ‘lá’ (leaf) dùng để chỉ điều gì?
A. Nút gốc của cây
B. Nút không có con
C. Nút có hai con
D. Nút nằm ở mức cao nhất của cây
140. Khi nào nên sử dụng thuật toán Quick Sort thay vì Merge Sort?
A. Khi cần độ ổn định của thuật toán sắp xếp
B. Khi dữ liệu gần như đã được sắp xếp
C. Khi không gian bộ nhớ là yếu tố quan trọng
D. Khi dữ liệu quá lớn để vừa vào bộ nhớ
141. 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 một 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
142. Cấu trúc dữ liệu nào sau đây cho phép cả chèn và xóa ở cả hai đầu?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Deque
D. Danh sách liên kết đơn
143. Trong cấu trúc dữ liệu cây, chiều cao của một nút được định nghĩa như thế nào?
A. Số lượng nút trên đường đi dài nhất từ nút đó đến một nút lá
B. Số lượng cạnh trên đường đi dài nhất từ nút đó đến một nút lá
C. Số lượng nút trên đường đi ngắn nhất từ nút đó đến nút gốc
D. Số lượng cạnh trên đường đi ngắn nhất từ nút đó đến nút gốc
144. Trong thuật toán Dijkstra, tập hợp nào được sử dụng để theo dõi các đỉnh đã được xử lý?
A. Stack
B. Queue
C. Set
D. List
145. Độ 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) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
146. 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 đến điều gì?
A. Độ ổn định của thuật toán
B. Độ phức tạp thời gian trung bình
C. Độ phức tạp thời gian trong trường hợp xấu nhất
D. Tất cả các đáp án trên
147. Ưu điểm của việc sử dụng cây nhị phân tìm kiếm (Binary Search Tree) so với mảng đã sắp xếp (Sorted Array) là gì?
A. Tìm kiếm nhanh hơn
B. Chèn và xóa phần tử nhanh hơn
C. Truy cập ngẫu nhiên nhanh hơn
D. Sử dụng ít bộ nhớ hơn
148. Trong cấu trúc dữ liệu đồ thị, thuật ngữ ‘chu trình’ (cycle) dùng để chỉ điều gì?
A. Đường đi giữa hai đỉnh bất kỳ
B. Đường đi bắt đầu và kết thúc tại cùng một đỉnh
C. Đường đi ngắn nhất giữa hai đỉnh
D. Tập hợp các đỉnh liên thông
149. 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 sử dụng trong thực tế?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
150. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra tính hợp lệ của dấu ngoặc trong một biểu thức?
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)
