1. Độ phức tạp thời gian trung bình của thuật toán QuickSort là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
2. 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 mảng thành các mảng con.
B. Giai đoạn so sánh các phần tử.
C. Giai đoạn trộn (merge) các mảng con đã sắp xếp.
D. Giai đoạn khởi tạo mảng.
3. Độ 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 (BST) lệch (skewed tree) là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
4. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất?
A. Merge Sort
B. QuickSort
C. Heap Sort
D. Insertion Sort
5. Trong thuật toán tô màu đồ thị (graph coloring), mục tiêu là gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm cây khung nhỏ nhất.
C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau có cùng màu.
D. Tìm chu trình Hamilton.
6. Trong biểu đồ (graph), thuật toán nào sau đây được sử dụng để tìm chu trình Euler?
A. Thuật toán Dijkstra
B. Thuật toán Kruskal
C. Thuật toán Fleury
D. Thuật toán Prim
7. Trong thuật toán Floyd-Warshall, mục đích chính là gì?
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 trong đồ thị.
C. Tìm cây khung nhỏ nhất của đồ thị.
D. Tìm chu trình Euler trong đồ thị.
8. Ưu điểm chính của 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 thông thường là gì?
A. Đơn giản hơn trong việc cài đặt.
B. Tiêu thụ ít bộ nhớ hơn.
C. Đảm bảo thời gian tìm kiếm, chèn, xóa là O(log n) trong trường hợp xấu nhất.
D. Cho phép duyệt cây theo thứ tự ngược.
9. Trong biểu đồ có hướng (directed graph), 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à không có đường đi giữa chúng.
B. Một tập hợp các đỉnh mà có đường đi từ mọi đỉnh đến mọi đỉnh khác trong tập hợp.
C. Một tập hợp các đỉnh mà có đường đi từ một đỉnh đến tất cả các đỉnh khác trong đồ thị.
D. Một tập hợp các đỉnh mà tất cả đều có bậc vào và bậc ra bằng nhau.
10. Loại đồ thị nào sau đây có thể được biểu diễn bằng ma trận kề (adjacency matrix) một cách hiệu quả nhất?
A. Đồ thị thưa (sparse graph)
B. Đồ thị dày (dense graph)
C. Cây (tree)
D. Danh sách liên kết (linked list)
11. Khi nào thì thuật toán Bubble Sort hoạt động hiệu quả nhất?
A. Khi dữ liệu đã được sắp xếp gần như hoàn chỉnh.
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.
D. Bubble Sort không bao giờ hoạt động hiệu quả.
12. Trong cây AVL, hệ số cân bằng (balance factor) của một nút được định nghĩa như thế nào?
A. Hiệu của chiều cao cây con trái và chiều cao cây con phải.
B. Tổng của chiều cao cây con trái và chiều cao cây con phải.
C. Tích của chiều cao cây con trái và chiều cao cây con phải.
D. Thương của chiều cao cây con trái và chiều cao cây con phải.
13. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (depth-first search) thay vì tìm kiếm theo chiều rộng (breadth-first search)?
A. Khi cần tìm đường đi ngắn nhất.
B. Khi không gian tìm kiếm rất rộng và có thể có đường đi dài.
C. Khi cần duyệt tất cả các đỉnh trong đồ thị.
D. Khi biết trước đích đến nằm gần đỉnh xuất phát.
14. Khi nào nên sử dụng danh sách liên kết đơn (singly 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. Khi cần tiết kiệm bộ nhớ.
15. Trong cây đỏ-đen (Red-Black tree), một nút có thể có bao nhiêu màu?
A. Một màu (đen)
B. Hai màu (đỏ hoặc đen)
C. Ba màu (đỏ, đen, hoặc xám)
D. Vô số màu
16. Trong thuật toán sắp xếp vun đống (heap sort), thao tác ‘vun đống’ (heapify) có tác dụng gì?
A. Sắp xếp các phần tử trong mảng theo thứ tự tăng dần.
B. Đảm bảo rằng cây nhị phân thỏa mãn tính chất của heap.
C. Chia mảng thành các mảng con.
D. Tìm phần tử lớn nhất trong mảng.
17. Trong cây B, bậc của cây (order) được định nghĩa là gì?
A. Số lượng nút tối thiểu trong cây.
B. Số lượng nút tối đa trong cây.
C. Số lượng con tối đa mà một nút có thể có.
D. Chiều cao của cây.
18. Cấu trúc dữ liệu nào sau đây 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. Heap
D. Cây tìm kiếm nhị phân (binary search tree)
19. Trong thuật toán Prim để tìm cây khung nhỏ nhất, cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ các đỉnh chưa được thêm vào cây khung?
A. Hàng đợi (queue)
B. Ngăn xếp (stack)
C. Hàng đợi ưu tiên (priority queue)
D. Danh sách liên kết (linked list)
20. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong mảng đã được sắp xếp?
A. Tìm kiếm tuyến tính (Linear Search)
B. Tìm kiếm theo chiều rộng (Breadth-First Search)
C. Tìm kiếm nhị phân (Binary Search)
D. Tìm kiếm theo chiều sâu (Depth-First Search)
21. Ưu điểm của việc sử dụng bảng băm (hash table) so với mảng (array) là gì?
A. Bảng băm luôn sử dụng ít bộ nhớ hơn mảng.
B. Bảng băm cho phép truy cập các phần tử trong thời gian O(1) trung bình, trong khi mảng cần O(n) trong trường hợp xấu nhất.
C. Bảng băm cho phép lưu trữ dữ liệu theo thứ tự.
D. Bảng băm không cần phải xác định kích thước trước.
22. Trong thuật toán A* tìm đường đi, hàm heuristic (h(n)) được sử dụng để làm gì?
A. Ước tính chi phí từ đỉnh hiện tại đến đỉnh đích.
B. Tính chi phí thực tế từ đỉnh bắt đầu đến đỉnh hiện tại.
C. Lưu trữ các đỉnh đã được duyệt.
D. Đảm bảo rằng thuật toán luôn tìm thấy đường đi ngắn nhất.
23. 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. Merge Sort
B. QuickSort
C. Counting Sort
D. Radix Sort
24. Trong thuật toán Kruskal để tìm cây khung nhỏ nhất, bước nào sau đây được thực hiện?
A. Chọn cạnh có trọng số lớn nhất và thêm vào cây khung.
B. Chọn cạnh có trọng số nhỏ nhất và thêm vào cây khung nếu nó không tạo thành chu trình.
C. Loại bỏ tất cả các cạnh có trọng số âm.
D. Chọn một đỉnh ngẫu nhiên và thêm tất cả các cạnh kề với đỉnh đó vào cây khung.
25. Thuật toán tìm kiếm nào sau đây có độ phức tạp thời gian O(1) trong trường hợp tốt nhấ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 rộng (breadth-first search)
D. Tìm kiếm bằng hàm băm (hashing)
26. Khi nào nên sử dụng cây Trie (prefix tree)?
A. Khi cần lưu trữ và tìm kiếm các số nguyên.
B. Khi cần lưu trữ và tìm kiếm các chuỗi ký tự với tiền tố chung.
C. Khi cần sắp xếp dữ liệu.
D. Khi cần biểu diễn mối quan hệ giữa các đối tượng.
27. Trong cây quyết định (decision tree), mục đích của việc tỉa cây (pruning) là gì?
A. Tăng độ chính xác của cây.
B. Giảm kích thước của cây và tránh overfitting.
C. Tăng tốc độ xây dựng cây.
D. Đơn giản hóa việc biểu diễn cây.
28. 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. Hàng đợi ưu tiên (Priority Queue)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
29. Khi sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách ước tính từ đỉnh nguồn đến các đỉnh khác?
A. Hàng đợi (queue)
B. Ngăn xếp (stack)
C. Hàng đợi ưu tiên (priority queue)
D. Danh sách liên kết (linked list)
30. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi có phải là palindrome hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Đồ thị (Graph)
31. Thuật toán sắp xếp nào sau đây là 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 cơ số (radix sort)
C. Sắp xếp chèn (insertion sort)
D. Sắp xếp đếm (counting sort)
32. Loại cấu trúc dữ liệu nào thường được sử dụng để triển khai liên kết riêng (separate chaining) trong bảng băm (hash table)?
A. Mảng
B. Danh sách liên kết
C. Cây nhị phân tìm kiếm
D. Hàng đợi
33. Độ phức tạp không gian của thuật toán sắp xếp trộn (merge sort) là gì?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
34. 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^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)
35. Cho một mảng đã được sắp xếp. Thuật toán sắp xếp nào sau đây sẽ có hiệu suất tốt 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 vun đống (heap sort)
36. Thuật toán sắp xếp nào sau đây phù hợp nhất để sắp xếp một mảng gần như đã được sắp xếp?
A. Sắp xếp nhanh (quick sort)
B. Sắp xếp vun đống (heap sort)
C. Sắp xếp chèn (insertion sort)
D. Sắp xếp trộn (merge sort)
37. Độ phức tạp thời gian tốt nhất 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)
38. Điều gì xảy ra nếu bảng băm (hash table) trở nên quá đầy?
A. Hiệu suất của bảng băm giảm.
B. Bảng băm tự động sắp xếp lại.
C. Bảng băm tăng kích thước gấp đôi.
D. Bảng băm ngừng hoạt động.
39. Ưu điểm chính của phương pháp liên kết riêng (separate chaining) so với địa chỉ mở (open addressing) là gì?
A. Liên kết riêng yêu cầu ít bộ nhớ hơn.
B. Liên kết riêng dễ cài đặt hơn.
C. Liên kết riêng có hiệu suất tốt hơn khi bảng băm gần đầy.
D. Liên kết riêng tránh được hiện tượng gom cụm (clustering).
40. Điều gì xảy ra khi hai khóa (key) khác nhau được băm (hash) vào cùng một chỉ số (index) trong bảng băm (hash table)?
A. Xảy ra tràn số.
B. Xảy ra đụng độ (collision).
C. Xảy ra lỗi bộ nhớ.
D. Xảy ra lỗi cú pháp.
41. Khi nào thì thuật toán sắp xếp đếm (counting sort) được sử dụng hiệu quả nhất?
A. Khi các phần tử trong mảng có giá trị rất lớn.
B. Khi các phần tử trong mảng có giá trị âm.
C. Khi các phần tử trong mảng có giá trị nằm trong một phạm vi nhỏ.
D. Khi cần sắp xếp các số thực.
42. 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. Chọn phần tử chốt gần với giá trị trung bình giúp cải thiện hiệu suất.
C. Chọn phần tử chốt lớn nhất giúp cải thiện hiệu suất.
D. Chọn phần tử chốt nhỏ nhất giúp cải thiện hiệu suất.
43. Phương pháp nào sau đây là một kỹ thuật địa chỉ mở (open addressing) trong bảng băm (hash table)?
A. Liên kết riêng (separate chaining)
B. Băm kép (double hashing)
C. Sắp xếp tuyến tính (linear probing)
D. Cây nhị phân tìm kiếm (binary search tree)
44. Trong thuật toán sắp xếp cơ số (radix sort), các phần tử được sắp xếp dựa trên điều gì?
A. Giá trị của phần tử.
B. Số lượng chữ số của phần tử.
C. Vị trí của chữ số trong phần tử.
D. Tổng các chữ số của phần tử.
45. Hàm băm (hash function) nào sau đây được coi là tốt nhất?
A. Hàm băm luôn trả về cùng một giá trị.
B. Hàm băm phân phối đều các khóa (key) trên toàn bộ bảng băm.
C. Hàm băm luôn tạo ra đụng độ (collision).
D. Hàm băm chỉ hoạt động với các số nguyên.
46. Mục đích chính của việc sử dụng hàm băm (hash function) trong bảng băm (hash table) là gì?
A. Để sắp xếp các phần tử.
B. Để mã hóa các phần tử.
C. Để chuyển đổi khóa (key) thành chỉ số (index) trong mảng.
D. Để nén dữ liệu.
47. Ứng dụng nào sau đây phù hợp nhất với thuật toán sắp xếp trộn (merge sort)?
A. Sắp xếp một mảng nhỏ các số nguyên.
B. Sắp xếp một danh sách liên kết.
C. Sắp xếp một mảng đã gần như được sắp xếp.
D. Sắp xếp một mảng tại chỗ (in-place).
48. Trong trường hợp nào thì thuật toán sắp xếp nhanh (quick sort) có hiệu suất kém nhất?
A. Khi mảng đã được sắp xếp.
B. Khi mảng có các phần tử trùng lặp.
C. Khi mảng có kích thước nhỏ.
D. Khi mảng có các phần tử ngẫu nhiên.
49. Trong thuật toán sắp xếp cơ số (radix sort), cơ số (radix) thường được chọn là bao nhiêu khi sắp xếp các số nguyên dương?
50. Ư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. Sắp xếp trộn có độ phức tạp thời gian tốt hơn trong trường hợp xấu nhất.
B. Sắp xếp trộn có độ phức tạp không gian tốt hơn.
C. Sắp xếp trộn dễ cài đặt hơn.
D. Sắp xếp trộn ổn định hơn.
51. Thuật toán sắp xếp nào sau đây có thể được sử dụng để sắp xếp dữ liệu trên đĩa ngoài (external sorting)?
A. Sắp xếp chèn (insertion sort)
B. Sắp xếp chọn (selection sort)
C. Sắp xếp vun đống (heap sort)
D. Sắp xếp trộn (merge sort)
52. Thuật toán sắp xếp nào sau đây không phải là thuật toán so sánh (comparison sort)?
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 đếm (counting sort)
53. 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 log n)?
A. Sắp xếp nhanh (quick sort)
B. Sắp xếp chèn (insertion sort)
C. Sắp xếp chọn (selection sort)
D. Sắp xếp vun đống (heap sort)
54. Phương pháp nào sau đây được sử dụng để giải quyết đụng độ (collision) trong bảng băm (hash table)?
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)
55. Khi nào thì việc sử dụng bảng băm (hash table) không phù hợp?
A. Khi cần tìm kiếm nhanh các phần tử.
B. Khi cần sắp xếp các phần tử.
C. Khi cần chèn và xóa các phần tử thường xuyên.
D. Khi cần lưu trữ một lượng lớn dữ liệu.
56. Cho một mảng gồm các số [5, 2, 8, 1, 9]. Sau bước đầu tiên của thuật toán sắp xếp chọn (selection sort), mảng sẽ như thế nào?
A. [1, 2, 8, 5, 9]
B. [2, 5, 8, 1, 9]
C. [1, 5, 8, 2, 9]
D. [9, 8, 5, 2, 1]
57. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong bảng băm (hash table) là gì?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
58. 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 nhỏ mảng thành các mảng con.
B. Giai đoạn so sánh các phần tử trong mảng.
C. Giai đoạn trộn (merge) các mảng con đã sắp xếp.
D. Giai đoạn tạo ra các mảng con.
59. Trong bảng băm (hash table), yếu tố tải (load factor) được định nghĩa là gì?
A. Số lượng phần tử trong bảng băm.
B. Kích thước của bảng băm.
C. Tỷ lệ giữa số lượng phần tử và kích thước của bảng băm.
D. Số lượng đụng độ (collision) trong bảng băm.
60. 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. Cây nhị phân tìm kiếm
B. Đồ thị
C. Hàng đợi
D. Vun đống (heap)
61. 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 Bellman-Ford
C. Thuật toán Prim
D. Tìm kiếm theo chiều sâu (DFS)
62. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai hàng đợi ưu tiên (priority queue)?
A. Mảng
B. Danh sách liên kết
C. Cây tìm kiếm nhị phân
D. Heap
63. 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 (selection sort)
C. Sắp xếp chèn (insertion sort)
D. Sắp xếp trộn (merge sort)
64. Trong thuật toán sắp xếp theo cơ số (radix sort), cơ sở (base) được chọn có ảnh hưởng như thế nào đến hiệu suất?
A. Không ảnh hưởng
B. Cơ sở lớn hơn luôn tốt hơn
C. Cơ sở nhỏ hơn luôn tốt hơn
D. Cơ sở phù hợp có thể tối ưu hiệu suất
65. Cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree) là gì?
A. Cây luôn có chiều cao bằng nhau
B. Cây tự động sắp xếp lại các nút để đảm bảo độ cao cân bằng
C. Cây không cho phép chèn các nút mới
D. Cây chỉ chứa các số nguyên
66. 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. Luôn cải thiện hiệu suất
C. Có thể ảnh hưởng đáng kể đến hiệu suất
D. Chỉ ảnh hưởng đến bộ nhớ sử dụng
67. Trong thuật toán sắp xếp vun đống (heap sort), thao tác vun đống (heapify) có độ phức tạp thời gian là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
68. Thuật toán sắp xếp nào sau đây đảm bảo tính ổn định (stable sorting)?
A. Sắp xếp nhanh (quick sort)
B. Sắp xếp chọn (selection sort)
C. Sắp xếp chèn (insertion sort)
D. Sắp xếp vun đống (heap sort)
69. Ứ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ý lịch sử duyệt web
B. Quản lý hàng đợi in
C. Gọi đệ quy
D. Kiểm tra dấu ngoặc hợp lệ
70. Khi nào nên sử dụng danh sách liên kết thay vì mảng?
A. Khi cần truy cập ngẫu nhiên các phần tử
B. Khi biết trước số lượng phần tử
C. Khi cần chèn hoặc xóa phần tử thường xuyên
D. Khi cần tiết kiệm bộ nhớ
71. 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
D. Mảng
72. Độ 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 khi dữ liệu đã được sắp xếp?
A. O(n^2)
B. O(log n)
C. O(n)
D. O(n log n)
73. Ưu điểm chính của thuật toán sắp xếp đếm (counting sort) là gì?
A. Hoạt động tốt với mọi loại dữ liệu
B. Độ phức tạp thời gian rất thấp khi phạm vi giá trị nhỏ
C. Không sử dụng bộ nhớ phụ
D. Dễ dàng cài đặt
74. Khi nào nên sử dụng thuật toán sắp xếp chèn (insertion sort) thay vì các thuật toán sắp xếp phức tạp hơn?
A. Khi dữ liệu rất lớn
B. Khi dữ liệu gần như đã được sắp xếp
C. Khi yêu cầu độ ổn định cao
D. Khi cần độ phức tạp thời gian tốt nhất
75. Độ phức tạp thời gian để tìm kiếm một phần tử trong bảng băm (hash table) với độ phân giải xung đột tốt là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
76. 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 chỉ hoạt động với đồ thị có hướng, Kruskal chỉ hoạt động với đồ thị vô hướng
C. Prim luôn tìm ra cây khung nhỏ nhất, Kruskal thì không
D. Prim có độ phức tạp thời gian tốt hơn Kruskal
77. Trong đồ thị có trọng số âm, thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất?
A. Thuật toán Dijkstra
B. Thuật toán tìm kiếm theo chiều rộng (BFS)
C. Thuật toán Bellman-Ford
D. Thuật toán Prim
78. Độ phức tạp thời gian của thao tác tìm kiếm trong danh sách liên kết đơn là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
79. Ưu điểm của danh sách liên kết đôi so với danh sách liên kết đơn 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
D. Dễ cài đặt hơn
80. Ứ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. Mạng xã hội
C. Tính toán số Fibonacci
D. Sắp xếp mảng số nguyên
81. Thuật toán duyệt đồ thị nào sau đây sử dụng hàng đợi (queue) để lưu trữ các đỉnh?
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 Bellman-Ford
82. Ứng dụng thực tế của thuật toán tìm đường đi ngắn nhất là gì?
A. Xây dựng cây khung nhỏ nhất
B. Tìm đường đi trên bản đồ
C. Sắp xếp dữ liệu
D. Nén dữ liệu
83. 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 nhanh (quick sort)
D. Sắp xếp theo cơ số (radix sort)
84. Trong thuật toán Dijkstra, mục đích chính là gì?
A. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác
B. Tìm chu trình âm trong đồ thị
C. Tìm cây khung nhỏ nhất
D. Sắp xếp các đỉnh của đồ thị
85. 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 trung bình là O(log n)?
A. Duyệt cây theo chiều rộng
B. Tìm kiếm một phần tử
C. Tìm phần tử lớn nhất
D. Tìm phần tử nhỏ nhất
86. Trong thuật toán sắp xếp trộn (merge sort), giai đoạn nào đóng vai trò quan trọng trong việc kết hợp các mảng con đã được sắp xếp?
A. Giai đoạn phân chia
B. Giai đoạn trộn
C. Giai đoạn so sánh
D. Giai đoạn hoán đổi
87. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc FIFO (First In, First Out)?
A. Ngăn xếp (stack)
B. Hàng đợi (queue)
C. Cây
D. Đồ thị
88. Sự khác biệt chính giữa cây và đồ thị là gì?
A. Cây có chu trình, đồ thị không có chu trình
B. Cây là đồ thị có hướng, đồ thị là cây vô hướng
C. Cây không có chu trình, đồ thị có thể có chu trình
D. Cây có nhiều gốc, đồ thị chỉ có một gốc
89. Độ 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)
90. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu ngăn xếp (stack)?
A. Quản lý hàng đợi in
B. Duyệt cây theo chiều rộng
C. Tính giá trị biểu thức hậu tố (postfix)
D. Tìm đường đi ngắn nhất
91. Khi nào nên sử dụng bảng băm (hash table) thay vì cây tìm kiếm nhị phân (binary search tree)?
A. Khi cần duyệt các phần tử theo thứ tự.
B. Khi cần tìm kiếm phần tử nhỏ nhất hoặc lớn nhất.
C. Khi cần 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).
D. Khi cần đảm bảo độ phức tạp thời gian O(log n) trong trường hợp xấu nhất.
92. Khi nào nên sử dụng thuật toán sắp xếp cơ số (radix sort)?
A. Khi cần sắp xếp các số thực.
B. Khi cần sắp xếp các chuỗi ký tự.
C. Khi cần sắp xếp các số nguyên có phạm vi giá trị nhỏ.
D. Khi cần sắp xếp các số nguyên có phạm vi giá trị lớn và số lượng chữ số ít.
93. Trong thuật toán Ford-Fulkerson, mục tiêu chính là gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Tìm luồng cực đại trong mạng lưới.
D. Tìm chu trình Euler trong đồ thị.
94. Độ 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).
95. Trong cấu trúc dữ liệu đồ thị, điều gì phân biệt đồ thị có hướng (directed graph) và đồ thị vô hướng (undirected graph)?
A. Số lượng đỉnh và cạnh.
B. Đồ thị có hướng có trọng số trên các cạnh, đồ thị vô hướng thì không.
C. Các cạnh trong đồ thị có hướng có hướng, còn đồ thị vô hướng thì không.
D. Đồ thị có hướng luôn là đồ thị liên thông, đồ thị vô hướng thì không.
96. Cây đỏ đen (red-black tree) là một dạng của cấu trúc dữ liệu nào?
A. Heap.
B. Graph.
C. Balanced Binary Search Tree.
D. Linked List.
97. Trong cây AVL, thao tác xoay (rotation) được sử dụng để làm gì?
A. Tìm kiếm một nút.
B. Cân bằng lại cây sau khi thêm hoặc xóa một nút.
C. Duyệt cây theo thứ tự giữa (inorder traversal).
D. Tăng chiều cao của cây.
98. Cấu trúc dữ liệu nào sau đây thích hợp để triển khai thuật toán ‘undo’ và ‘redo’ trong một trình soạn thảo văn bản?
A. Queue.
B. Stack.
C. Linked List.
D. Hash Table.
99. Trong thuật toán Kruskal để tìm cây khung nhỏ nhất, tiêu chí nào được sử dụng để chọn cạnh tiếp theo?
A. Cạnh có trọng số lớn nhất mà không tạo thành chu trình.
B. Cạnh có trọng số nhỏ nhất mà không tạo thành chu trình.
C. Cạnh kết nối hai thành phần liên thông mạnh nhất.
D. Cạnh được duyệt đầu tiên.
100. Thuật toán duyệt đồ thị theo chiều sâu (depth-first search – DFS) sử dụng cấu trúc dữ liệu nào để lưu trữ các đỉnh cần duyệt?
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).
101. 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 là O(n) trong trường hợp xấu nhất?
A. Tìm kiếm một nút.
B. Chèn một nút.
C. Xóa một nút.
D. Duyệt cây theo thứ tự giữa (inorder traversal).
102. 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 nhỏ mảng thành các mảng con.
B. Giai đoạn so sánh và tráo đổi các phần tử.
C. Giai đoạn trộn (merge) các mảng con đã sắp xếp.
D. Giai đoạn chọn phần tử chốt (pivot).
103. Ưu điểm chính của thuật toán sắp xếp nhanh (quick sort) so với sắp xếp trộn (merge sort) là gì?
A. Độ phức tạp thời gian trong trường hợp xấu nhất tốt hơn.
B. Không gian bộ nhớ sử dụng ít hơn.
C. Dễ cài đặt và gỡ lỗi hơn.
D. Luôn ổn định (stable).
104. Sự khác biệt chính giữa danh sách liên kết đơn (singly linked list) và danh sách liên kết kép (doubly linked list) là gì?
A. Danh sách liên kết kép có thể lưu trữ nhiều dữ liệu hơn.
B. Danh sách liên kết kép cho phép duyệt theo cả hai chiều.
C. Danh sách liên kết đơn nhanh hơn trong việc chèn và xóa phần tử.
D. Danh sách liên kết đơn yêu cầu nhiều bộ nhớ hơn.
105. 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 (array).
B. Danh sách liên kết (linked list).
C. Cây (tree).
D. Bảng băm (hash table).
106. Thuật toán tìm kiếm nhị phân (binary search) có thể được áp dụng trên cấu trúc dữ liệu nào?
A. Danh sách liên kết đơn (singly linked list).
B. Mảng chưa được sắp xếp (unsorted array).
C. Mảng đã được sắp xếp (sorted array).
D. Cây tìm kiếm nhị phân không cân bằng (unbalanced binary search tree).
107. Khi nào nên sử dụng thuật toán sắp xếp vun đống (heap sort) thay vì sắp xếp nhanh (quick sort)?
A. Khi cần độ ổn định (stability) trong sắp xếp.
B. Khi cần sắp xếp tại chỗ (in-place) và không gian bộ nhớ là yếu tố quan trọng.
C. Khi dữ liệu đã gần được sắp xếp.
D. Khi cần đảm bảo độ phức tạp thời gian O(n log n) trong mọi trường hợp.
108. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để tìm thành phần liên thông mạnh (strongly connected components)?
A. Dijkstra.
B. Prim.
C. Kruskal.
D. Kosaraju.
109. Ứ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 lệnh gọi hàm trong một chương trình.
B. In các tài liệu theo thứ tự gửi đến máy in.
C. Tìm đường đi trong một mê cung.
D. Lưu trữ lịch sử các trang web đã truy cập.
110. Trong thuật toán Dijkstra tìm đường đi ngắn nhất, 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. Mảng (array).
B. Danh sách liên kết (linked list).
C. Hàng đợi ưu tiên (priority queue).
D. Cây tìm kiếm nhị phân (binary search tree).
111. Sự khác biệt chính giữa cấu trúc dữ liệu ‘heap’ và ‘binary search tree’ là gì?
A. Heap cho phép truy cập ngẫu nhiên, binary search tree thì không.
B. Heap đảm bảo độ phức tạp O(log n) cho tất cả các thao tác, binary search tree thì không.
C. Heap chỉ cho phép truy cập phần tử lớn nhất hoặc nhỏ nhất, binary search tree cho phép tìm kiếm theo giá trị.
D. Heap sử dụng mảng, binary search tree sử dụng danh sách liên kết.
112. Độ phức tạp thời gian của thao tác tìm kiếm trong bảng băm (hash table) trong trường hợp xấu nhất là gì?
A. O(1).
B. O(log n).
C. O(n).
D. O(n^2).
113. Trong cây tìm kiếm nhị phân (binary search tree), thao tác nào 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.
D. Duyệt cây theo chiều rộng (breadth-first traversal).
114. Trong thuật toán Prim để tìm cây khung nhỏ nhất (minimum spanning tree), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ các cạnh có thể thêm vào cây?
A. Hàng đợi (queue).
B. Ngăn xếp (stack).
C. Hàng đợi ưu tiên (priority queue).
D. Bảng băm (hash table).
115. Ư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 các phần tử có giá trị âm.
B. Có thể sắp xếp các phần tử có giá trị thực.
C. Có độ phức tạp thời gian là O(n log n).
D. Có độ phức tạp thời gian là O(n+k) với k là phạm vi giá trị của các phần tử.
116. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu?
A. Dijkstra’s Algorithm.
B. Huffman Coding.
C. Merge Sort.
D. Binary Search.
117. Cấu trúc dữ liệu nào sau đây tuân theo nguyên tắc LIFO (Last-In, First-Out)?
A. Queue.
B. Stack.
C. Linked List.
D. Array.
118. 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 để quản lý các đỉnh sẽ được duyệt?
A. Stack.
B. Queue.
C. Linked List.
D. Tree.
119. Kỹ thuật nào sau đây được sử dụng để giải quyết các bài toán tối ưu hóa có tính chất chồng chéo (overlapping subproblems) và cấu trúc con tối ưu (optimal substructure)?
A. Tham lam (greedy).
B. Chia để trị (divide and conquer).
C. Quy hoạch động (dynamic programming).
D. Tìm kiếm vét cạn (brute force).
120. Cấu trúc dữ liệu nào sau đây đảm bảo thời gian truy cập phần tử là O(1) trong trường hợp trung bình?
A. Danh sách liên kết (linked list).
B. Cây tìm kiếm nhị phân (binary search tree).
C. Mảng (array).
D. Hàng đợi (queue).
121. Thuật toán sắp xếp nào sau đây không ổn định và có độ phức tạp thời gian trung bình là O(n log n)?
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 đếm (counting sort).
122. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian xấu nhất 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 vun đống (heap sort).
D. Sắp xếp shell (shell sort).
123. Ứng dụng thực tế nào sau đây phù hợp nhất với thuật toán sắp xếp theo bucket (bucket sort)?
A. Sắp xếp điểm thi của sinh viên.
B. Sắp xếp tên trong danh bạ.
C. Sắp xếp số điện thoại.
D. Sắp xếp dữ liệu có phân phối đều trong một khoảng nhất định.
124. Trong trường hợp nào thì thuật toán sắp xếp nổi bọt (bubble sort) hoạt động hiệu quả nhất?
A. Khi mảng đã được sắp xếp hoàn toàn.
B. Khi mảng có kích thước rất lớn.
C. Khi mảng gần như đã được sắp xếp.
D. Khi mảng chứa các số ngẫu nhiên.
125. Thuật toán sắp xếp nào sau đây có thể được sử dụng để sắp xếp một mảng các số âm và dương một cách hiệu quả?
A. Sắp xếp đếm (counting sort).
B. Sắp xếp trộn (merge sort).
C. Sắp xếp nổi bọt (bubble sort).
D. Sắp xếp chọn (selection sort).
126. Nhược điểm chính của thuật toán sắp xếp trộn (merge sort) là gì?
A. Độ phức tạp thời gian cao.
B. Yêu cầu bộ nhớ phụ lớn.
C. Khó cài đặt.
D. Không ổn định.
127. Ưu điểm chính của thuật toán sắp xếp nhanh (quick sort) so với sắp xếp chèn (insertion sort) là gì?
A. Sắp xếp nhanh luôn ổn định hơn.
B. Sắp xếp nhanh có độ phức tạp thời gian trung bình tốt hơn.
C. Sắp xếp nhanh dễ cài đặt hơn.
D. Sắp xếp nhanh không cần thêm bộ nhớ.
128. Độ 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)
129. 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. Độ phức tạp không gian của thuật toán.
B. Độ ổn định của thuật toán.
C. Độ phức tạp thời gian của thuật toán.
D. Số lượng phép so sánh cần thiết.
130. Trong thuật toán sắp xếp theo bucket (bucket sort), điều gì xảy ra nếu có quá nhiều phần tử rơi vào cùng một bucket?
A. Thuật toán sẽ bị lỗi.
B. Độ phức tạp thời gian của thuật toán tăng lên.
C. Các bucket sẽ được trộn lại với nhau.
D. Các phần tử sẽ bị bỏ qua.
131. 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).
132. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình tốt nhất trong thực tế?
A. Sắp xếp nổi bọt (bubble sort).
B. Sắp xếp chọn (selection sort).
C. Sắp xếp nhanh (quick sort).
D. Sắp xếp chèn (insertion sort).
133. 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. Cây nhị phân tìm kiếm.
B. Đồ thị.
C. Hàng đợi.
D. Vun đống (heap).
134. Để sắp xếp một danh sách liên kết đơn, thuật toán sắp xếp nào sau đây là phù hợp nhất?
A. Sắp xếp vun đống (heap sort).
B. Sắp xếp nhanh (quick sort).
C. Sắp xếp trộn (merge sort).
D. Sắp xếp chọn (selection sort).
135. Trong thuật toán sắp xếp cơ số (radix sort), thứ tự sắp xếp các phần tử dựa trên điều gì?
A. Giá trị của phần tử.
B. Kích thước của phần tử.
C. Chữ số hoặc ký tự tại một vị trí nhất định.
D. Địa chỉ bộ nhớ của phần tử.
136. Thuật toán sắp xếp nào sau đây là ổn định (stable)?
A. Sắp xếp nhanh (quick sort).
B. Sắp xếp chọn (selection sort).
C. Sắp xếp vun đống (heap sort).
D. Sắp xếp chèn (insertion sort).
137. Trong thuật toán sắp xếp cơ số (radix sort), cơ sở (base) được chọn ảnh hưởng đến điều gì?
A. Độ ổn định của thuật toán.
B. Số lượng các lần lặp cần thiết.
C. Độ phức tạp không gian của thuật toán.
D. Độ phức tạp thời gian của thuật toán.
138. Để sắp xếp một mảng các số thực có giá trị nằm trong khoảng từ 0 đến 1 một cách hiệu quả nhất, thuật toán nào sau đây nên được sử dụng?
A. Sắp xếp nhanh (quick sort).
B. Sắp xếp trộn (merge sort).
C. Sắp xếp theo bucket (bucket sort).
D. Sắp xếp vun đống (heap sort).
139. 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 mảng thành các mảng con.
B. Giai đoạn so sánh các phần tử trong mảng.
C. Giai đoạn trộn (merge) các mảng con đã sắp xếp.
D. Giai đoạn khởi tạo mảng ban đầu.
140. Thuật toán sắp xếp nào sau đây không phải là thuật toán so sánh (comparison sort)?
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 đếm (counting sort).
141. Trong thuật toán sắp xếp chọn (selection sort), số lượng phép hoán đổi (swaps) tối đa là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
142. Khi nào nên sử dụng sắp xếp shell (shell sort) thay vì sắp xếp chèn (insertion sort)?
A. Khi cần một thuật toán ổn định.
B. Khi mảng có kích thước nhỏ.
C. Khi mảng đã được sắp xếp hoàn toàn.
D. Khi mảng có kích thước lớn và chưa được sắp xếp.
143. Trong thuật toán sắp xếp vun đống (heap sort), thao tác ‘heapify’ có tác dụng gì?
A. Sắp xếp toàn bộ mảng.
B. Chuyển đổi mảng thành một vun đống (heap).
C. Tìm phần tử lớn nhất trong mảng.
D. Loại bỏ các phần tử trùng lặp.
144. Để sắp xếp một mảng lớn các số nguyên, trong đó các số có giá trị gần nhau, thuật toán nào sau đây có thể hiệu quả nhất?
A. Sắp xếp nhanh (quick sort).
B. Sắp xếp chèn (insertion sort).
C. Sắp xếp trộn (merge sort).
D. Sắp xếp vun đống (heap sort).
145. Trong thuật toán sắp xếp chèn (insertion sort), số lượng phép so sánh tối đa trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
146. Thuật toán sắp xếp nào sau đây phù hợp nhất để sắp xếp một tập dữ liệu lớn không thể chứa hết trong bộ nhớ?
A. Sắp xếp nhanh (quick sort).
B. Sắp xếp vun đống (heap sort).
C. Sắp xếp trộn ngoài (external merge sort).
D. Sắp xếp chèn (insertion sort).
147. Ứng dụng nào sau đây phù hợp nhất với thuật toán sắp xếp đếm (counting sort)?
A. Sắp xếp một mảng lớn các số thực.
B. Sắp xếp một mảng các chuỗi ký tự.
C. Sắp xếp một mảng các số nguyên có phạm vi nhỏ.
D. Sắp xếp một mảng đã gần như được sắp xếp.
148. Để sắp xếp một mảng các đối tượng theo nhiều tiêu chí (ví dụ: tên, tuổi, địa chỉ), thuật toán nào sau đây phù hợp nhất?
A. Sắp xếp nổi bọt (bubble sort).
B. Sắp xếp chọn (selection sort).
C. Sắp xếp trộn (merge sort).
D. Sắp xếp cơ số (radix sort).
149. Thuật toán sắp xếp nào sau đây có độ phức tạp không gian là O(1)?
A. Sắp xếp trộn (merge sort).
B. Sắp xếp nhanh (quick sort).
C. Sắp xếp vun đống (heap sort).
D. Sắp xếp đếm (counting sort).
150. Trong thuật toán sắp xếp vun đống (heap sort), việc xây dựng vun đống (heap) ban đầu có độ phức tạp thời gian là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
