1. Khi nào nên sử dụng sắp xếp vun đống (Heap Sort) thay vì sắp xếp trộn (Merge Sort)?
A. Khi cần một thuật toán sắp xếp ổn định.
B. Khi không gian bộ nhớ là một vấn đề quan trọng.
C. Khi dữ liệu gần như đã được sắp xếp.
D. Khi tốc độ là yếu tố quan trọng nhất.
2. Khi nào thì cây Splay được ưu tiên hơn cây AVL?
A. Khi cần đảm bảo thời gian truy cập trường hợp xấu nhất là O(log n).
B. Khi các truy cập gần đây có khả năng được truy cập lại sớm.
C. Khi cần một cấu trúc dữ liệu dễ cài đặt.
D. Khi dữ liệu được phân phối ngẫu nhiên.
3. 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
B. Ngăn xếp
C. Hàng đợi ưu tiên
D. Danh sách liên kết
4. Cây nào sau đây không phải là cây tự cân bằng?
A. Cây AVL
B. Cây đỏ đen
C. Cây B
D. Cây tìm kiếm nhị phân không cân bằng
5. Ưu điểm chính của việc sử dụng cây đỏ đen so với cây AVL là gì?
A. Cây đỏ đen có chiều cao nhỏ hơn.
B. Cây đỏ đen dễ cài đặt hơn.
C. Cây đỏ đen yêu cầu ít thao tác cân bằng hơn.
D. Cây đỏ đen đảm bảo thời gian tìm kiếm nhanh hơn.
6. Trong cây AVL, hệ số cân bằng của một nút được định nghĩa là gì?
A. Chiều cao của cây con trái trừ đi chiều cao của cây con phải.
B. Chiều cao của cây con phải trừ đi chiều cao của cây con trái.
C. Tổng chiều cao của cây con trái và cây con phải.
D. Số lượng nút trong cây con trái trừ đi số lượng nút trong cây con phải.
7. 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ừ nút nguồn đến các nút khác?
A. Hàng đợi
B. Ngăn xếp
C. Đồ thị
D. Hàng đợi ưu tiên
8. Ưu điểm chính của việc sử dụng cây B so với cây tìm kiếm nhị phân thông thường là gì?
A. Cây B dễ cài đặt hơn.
B. Cây B hiệu quả hơn cho dữ liệu được lưu trữ trên đĩa.
C. Cây B luôn có chiều cao nhỏ hơn.
D. Cây B chỉ có thể lưu trữ số nguyên.
9. Thuật toán nào sau đây đượ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. Tìm kiếm theo chiều rộng
10. Cây tìm kiếm nhị phân (BST) nào sau đây đảm bảo chiều cao là O(log n) trong trường hợp xấu nhất, với n là số lượng nút?
A. Cây tìm kiếm nhị phân không cân bằng
B. Cây AVL
C. Cây lệch trái
D. Cây Splay
11. Trong cây B, bậc của một nút được định nghĩa là gì?
A. Số lượng con tối thiểu mà một nút có thể có.
B. Số lượng con tối đa mà một nút có thể có.
C. Chiều cao của cây.
D. Số lượng nút trong cây.
12. 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 để thêm vào cây khung?
A. Ngăn xếp
B. Hàng đợi
C. Hàng đợi ưu tiên
D. Danh sách liên kết
13. Thuật toán nào sau đây được sử dụng để tìm kiếm một nút cụ thể trong đồ thị?
A. Sắp xếp tô pô (Topological Sort)
B. Tìm kiếm theo chiều sâu (Depth-First Search)
C. Cây khung nhỏ nhất (Minimum Spanning Tree)
D. Đường đi ngắn nhất (Shortest Path)
14. 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?
A. Mảng
B. Danh sách liên kết
C. Heap
D. Cây tìm kiếm nhị phân
15. Cho một mảng đã sắp xếp, thuật toán tìm kiếm nào sau đây hiệu quả nhất?
A. Tìm kiếm tuyến tính
B. Tìm kiếm nhị phân
C. Tìm kiếm theo chiều rộng
D. Tìm kiếm theo chiều sâu
16. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một dấu ngoặc đã cho có cân bằng hay không?
A. Hàng đợi
B. Ngăn xếp
C. Cây
D. Đồ thị
17. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick sort) là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
18. 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. 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 vun đống (Heap Sort)
19. Trong thuật toán Kruskal, tiêu chí nào được sử dụng để chọn cạnh để thêm vào cây khung nhỏ nhất?
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 liền kề với nút nguồn.
D. Cạnh được khám phá đầu tiên.
20. Trong cây đỏ đen, thuộc tính nào sau đây luôn đúng?
A. Tất cả các đường đi từ nút gốc đến nút lá đều có cùng số lượng nút đen.
B. Tất cả các nút đều có màu đỏ.
C. Tất cả các nút đều có màu đen.
D. Một nút đỏ có thể có một nút con đỏ.
21. 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(1)?
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. Không có thao tác nào ở trên
22. 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à bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
23. Ưu điểm chính của việc sử dụng bảng băm (hash table) là gì?
A. Truy cập phần tử trong thời gian O(1) trung bình.
B. Duy trì các phần tử theo thứ tự đã sắp xếp.
C. Hiệu quả cho dữ liệu động.
D. Yêu cầu ít bộ nhớ hơn các cấu trúc dữ liệu khác.
24. Độ phức tạp thời gian trường hợp xấu nhất của sắp xếp chèn (Insertion Sort) là gì?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
25. Khi nào nên sử dụng danh sách liên kết thay vì mảng?
A. Khi kích thước của dữ liệu đã biết trước.
B. Khi cần truy cập ngẫu nhiên 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ữ dữ liệu tuần tự trong bộ nhớ.
26. Cây khung nhỏ nhất của một đồ thị liên thông, có trọng số là gì?
A. Một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.
B. Một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
C. Một đồ thị con chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
D. Một đồ thị con chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.
27. Độ 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 là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(log n)
D. O(1)
28. Thuật toán nào sau đây sử dụng 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)
29. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất là O(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 nhanh (Quick Sort)
D. Sắp xếp trộn (Merge Sort)
30. Trong đồ thị có hướng, thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình?
A. Tìm kiếm theo chiều rộng
B. Tìm kiếm theo chiều sâu
C. Thuật toán Dijkstra
D. Thuật toán Prim
31. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là gì?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
32. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt, phần tử nào được đưa về đúng vị trí?
A. Phần tử nhỏ nhất
B. Phần tử lớn nhất
C. Phần tử ở giữa
D. Phần tử đầu tiên
33. Phương pháp nào sau đây được sử dụng để duyệt đồ thị theo chiều rộng (Breadth-First Search)?
A. Sử dụng ngăn xếp (Stack)
B. Sử dụng hàng đợi (Queue)
C. Sử dụng cây (Tree)
D. Sử dụng danh sách liên kết (Linked List)
34. 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)
35. Độ 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à gì?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
36. Mục đích chính của việc sử dụng hàm băm (Hash Function) trong bảng băm là gì?
A. Sắp xếp các phần tử
B. Chuyển đổi khóa thành chỉ số trong mảng
C. Tìm kiếm phần tử lớn nhất
D. Giải quyết xung đột
37. Thuật toán sắp xếp nào sau đây sử dụng phương pháp chia để trị?
A. Bubble Sort
B. Insertion Sort
C. Selection Sort
D. Merge Sort
38. Cây nào sau đây đảm bảo thời gian tìm kiếm, chèn và xóa là O(log n) trong trường hợp xấu nhất?
A. Cây nhị phân tìm kiếm (Binary Search Tree)
B. Cây AVL
C. Cây tìm kiếm B
D. Heap
39. Độ 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(n)
B. O(log n)
C. O(1)
D. O(n^2)
40. Thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree) của một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Ford-Fulkerson
C. Thuật toán Floyd-Warshall
D. Thuật toán Prim
41. Phương pháp nào sau đây được sử dụng để duyệt đồ thị theo chiều sâu (Depth-First Search)?
A. Sử dụng ngăn xếp (Stack)
B. Sử dụng hàng đợi (Queue)
C. Sử dụng cây (Tree)
D. Sử dụng danh sách liên kết (Linked List)
42. 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. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Danh sách liên kết (Linked List)
D. Cây (Tree)
43. Thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị có trọng số không âm?
A. Thuật toán Prim
B. Thuật toán Kruskal
C. Thuật toán Dijkstra
D. Thuật toán Ford-Fulkerson
44. Trong thuật toán sắp xếp trộn (Merge Sort), quá trình trộn hai mảng đã sắp xếp 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)
45. Trong thuật toán tham lam (Greedy Algorithm), quyết định được đưa ra dựa trên yếu tố nào?
A. Quyết định tốt nhất ở thời điểm hiện tại
B. Quyết định tốt nhất trong tương lai
C. Quyết định ngẫu nhiên
D. Quyết định dựa trên kinh nghiệm
46. 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 O(h), với h là chiều cao của cây?
A. Duyệt cây theo thứ tự trước (Preorder Traversal)
B. Duyệt cây theo thứ tự giữa (Inorder Traversal)
C. Tìm kiếm một phần tử
D. Duyệt cây theo thứ tự sau (Postorder Traversal)
47. Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) là gì?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
48. Trong thuật toán tìm kiếm nhị phân (Binary Search), điều kiện tiên quyết để thuật toán hoạt động đúng là gì?
A. Mảng phải được sắp xếp
B. Mảng phải chứa các số nguyên dương
C. Mảng phải có kích thước lớn hơn 100
D. Mảng không được chứa các phần tử trùng lặp
49. Ứng dụng nào sau đây không phải là ứng dụng của cấu trúc dữ liệu đồ thị?
A. Mạng xã hội
B. Hệ thống định vị GPS
C. Quản lý bộ nhớ
D. Mạng lưới giao thông
50. Trong bảng băm (Hash Table), kỹ thuật nào sau đây được sử dụng để giải quyết xung đột (Collision)?
A. Sắp xếp (Sorting)
B. Tìm kiếm (Searching)
C. Địa chỉ mở (Open Addressing)
D. Chia để trị (Divide and Conquer)
51. Đâu là một ví dụ về bài toán có thể 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ố âm
B. Bài toán người du lịch (Traveling Salesman Problem)
C. Bài toán cái túi (Knapsack Problem) với các vật có thể chia nhỏ
D. Tìm cây khung nhỏ nhất trong đồ thị
52. Đâu là một ví dụ về bài toán có thể giải quyết hiệu quả bằng kỹ thuật lập trình động?
A. Sắp xếp một mảng
B. Tìm kiếm một phần tử trong mảng
C. Tính số Fibonacci
D. Tính giai thừa của một số
53. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS) trên một đồ thị là gì?
A. O(V + E)
B. O(V * E)
C. O(V^2)
D. O(E^2)
54. Khi nào thuật toán sắp xếp chèn (Insertion Sort) hoạt động hiệu quả hơn thuật toán sắp xếp chọn (Selection Sort)?
A. Khi mảng đã được sắp xếp một phần
B. Khi mảng có kích thước lớn
C. Khi mảng chứa nhiều phần tử trùng lặp
D. Khi mảng chứa các số âm
55. Kỹ thuật lập trình động (Dynamic Programming) thường được áp dụng cho các bài toán có đặc điểm gì?
A. Bài toán không có nghiệm
B. Bài toán con độc lập
C. Bài toán con chồng lấn
D. Bài toán có độ phức tạp quá lớn
56. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt hàng đợi ưu tiên (Priority Queue)?
A. Mảng
B. Danh sách liên kết
C. Heap
D. Cây nhị phân tìm kiếm
57. Sự khác biệt chính giữa thuật toán tham lam và lập trình động là gì?
A. Thuật toán tham lam luôn tìm ra nghiệm tối ưu
B. Lập trình động luôn nhanh hơn thuật toán tham lam
C. Thuật toán tham lam đưa ra quyết định cục bộ, còn lập trình động xem xét tất cả các khả năng
D. Lập trình động chỉ áp dụng cho các bài toán tối ưu
58. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng (Breadth-First Search – BFS) trên một đồ thị là gì?
A. O(V + E)
B. O(V * E)
C. O(V^2)
D. O(E^2)
59. Cây nào sau đây là một ví dụ về cấu trúc dữ liệu tự cân bằng?
A. Cây nhị phân tìm kiếm (Binary Search Tree)
B. Cây AVL
C. Cây Huffman
D. Cây quyết định (Decision Tree)
60. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian O(n^2) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất)?
A. Quick Sort
B. Merge Sort
C. Heap Sort
D. Selection Sort
61. Độ 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)
62. Trong cây tìm kiếm nhị phân tự cân bằng (Self-Balancing Binary Search Tree), thao tác nào sau đây được sử dụng để duy trì sự cân bằng của cây sau khi chèn hoặc xóa một nút?
A. Sắp xếp lại các nút theo thứ tự tăng dần.
B. Xoay cây (Tree Rotation).
C. Thay đổi giá trị của các nút.
D. Loại bỏ các nút con.
63. Độ phức tạp thời gian tốt nhất của thuật toán Insertion Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
64. 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ì hiệu suất tốt của nó?
A. Bubble Sort
B. Insertion Sort
C. Selection Sort
D. Quick Sort
65. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
66. Khi nào thì nên sử dụng thuật toán tìm kiếm theo chiều rộng (Breadth-First Search) thay vì tìm kiếm theo chiều sâu (Depth-First Search)?
A. Khi cần tìm đường đi ngắn nhất trong đồ thị không trọng số.
B. Khi cần duyệt toàn bộ đồ thị.
C. Khi cần tìm một đỉnh cụ thể trong đồ thị.
D. Khi đồ thị có chu trình.
67. Trong cây tìm kiếm nhị phân (Binary Search Tree), điều kiện nào sau đây luôn đúng?
A. Giá trị của nút con trái lớn hơn giá trị của nút cha.
B. Giá trị của nút con phải nhỏ hơn giá trị của nút cha.
C. Giá trị của nút con trái nhỏ hơn hoặc bằng giá trị của nút cha và giá trị của nút con phải lớn hơn giá trị của nút cha.
D. Giá trị của nút con trái lớn hơn hoặc bằng giá trị của nút cha và giá trị của nút con phải nhỏ hơn giá trị của nút cha.
68. 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. Stack (Ngăn xếp)
B. Queue (Hàng đợi)
C. Linked List (Danh sách liên kết)
D. Tree (Cây)
69. Thuật toán nào sau đây là một ví dụ của thuật toán chia để trị (Divide and Conquer)?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
70. Ưu điểm chính của việc sử dụng bảng băm (Hash Table) là gì?
A. Duyệt các phần tử theo thứ tự đã sắp xếp.
B. Tìm kiếm, chèn và xóa phần tử nhanh chóng (trung bình O(1)).
C. Sử dụng bộ nhớ hiệu quả hơn so với mảng.
D. Dễ dàng triển khai và gỡ lỗi.
71. 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. Quick Sort
C. Heap Sort
D. Insertion Sort
72. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), điều gì xảy ra trong mỗi lần duyệt qua danh sách?
A. Phần tử lớn nhất được đặt vào vị trí đầu tiên.
B. Phần tử nhỏ nhất được đặt vào vị trí cuối cùng.
C. Các phần tử được sắp xếp hoàn toàn.
D. Phần tử lớn nhất được đặt vào vị trí đúng của nó ở cuối danh sách.
73. Khi nào thì thuật toán Insertion Sort được ưu tiên sử dụng hơn các thuật toán sắp xếp phức tạp hơn như Merge Sort hoặc Quick Sort?
A. Khi cần sắp xếp một lượng lớn dữ liệu.
B. Khi dữ liệu đã gần được sắp xếp.
C. Khi yêu cầu độ ổn định cao.
D. Khi cần sắp xếp dữ liệu ngẫu nhiên.
74. Thuật toán sắp xếp nào sau đây là ổn định (stable), nghĩa là nó duy trì thứ tự tương đối của các phần tử bằng nhau?
A. Quick Sort
B. Heap Sort
C. Selection Sort
D. Merge Sort
75. Thuật toán nào sau đây được sử dụng để duyệt đồ thị theo chiều sâu (Depth-First Search)?
A. Sử dụng hàng đợi (Queue).
B. Sử dụng ngăn xếp (Stack).
C. Sử dụng cây (Tree).
D. Sử dụng mảng (Array).
76. Ư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 phần tử nhanh hơn.
D. Sắp xếp phần tử dễ dàng hơn.
77. Độ phức tạp thời gian xấu nhất của thuật toán Merge Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
78. 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ử với độ phức tạp thời gian O(1)?
A. Danh sách liên kết (Linked List)
B. Cây (Tree)
C. Mảng (Array)
D. Hàng đợi (Queue)
79. Trong bảng băm (Hash Table), điều gì xảy ra khi có sự đụng độ (Collision)?
A. Phần tử mới sẽ ghi đè lên phần tử cũ.
B. Phần tử mới sẽ không được chèn vào bảng băm.
C. Cần sử dụng các kỹ thuật giải quyết đụng độ như separate chaining hoặc open addressing.
D. Bảng băm sẽ tự động tăng kích thước.
80. Trong thuật toán Dijkstra, điều gì đảm bảo rằng đường đi ngắn nhất được tìm thấy cho mỗi đỉnh?
A. Sử dụng hàng đợi FIFO.
B. Chọn đỉnh có khoảng cách ngắn nhất chưa được xử lý.
C. Duyệt tất cả các đường đi có thể.
D. Sử dụng hàm băm để lưu trữ khoảng cách.
81. Thuật toán nào sau đây có độ phức tạp thời gian O(n log n) trong mọi trường hợp?
A. Quick Sort
B. Insertion Sort
C. Heap Sort
D. Bubble Sort
82. Cấu trúc dữ liệu nào sau đây cho phép chèn và xóa các phần tử ở cả hai đầu?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Deque (Double-Ended Queue)
D. Danh sách liên kết đơn (Singly Linked List)
83. Trong đồ thị (Graph), 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 còn lại?
A. Breadth-First Search (BFS)
B. Depth-First Search (DFS)
C. Dijkstra’s Algorithm
D. Prim’s Algorithm
84. 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 (Hàng đợi)
B. Stack (Ngăn xếp)
C. Linked List (Danh sách liên kết)
D. Tree (Cây)
85. Thuật toán tìm kiếm nào sau đây sử dụng phương pháp ‘chia để trị’ để tìm kiếm một phần tử trong một mảng đã được sắp xếp?
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 theo chiều sâu (Depth-First Search)
86. Cấu trúc dữ liệu nào sau đây là một dạng cây, trong đó mỗi nút có thể có nhiều hơn hai nút con?
A. Cây nhị phân (Binary Tree)
B. Cây tìm kiếm nhị phân (Binary Search Tree)
C. Cây B
D. Cây AVL
87. Cây nào sau đây đảm bảo thời gian tìm kiếm, chèn và xóa là O(log n) trong trường hợp xấu nhất?
A. Cây tìm kiếm nhị phân (Binary Search Tree)
B. Cây AVL
C. Cây Heap
D. Cây Trie
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. Dijkstra’s Algorithm
B. Breadth-First Search (BFS)
C. Prim’s Algorithm
D. Depth-First Search (DFS)
89. Trong thuật toán tìm kiếm nhị phân (Binary Search), dữ liệu đầu vào cần phải như thế nào?
A. Được sắp xếp ngẫu nhiên
B. Được sắp xếp theo thứ tự tăng dần hoặc giảm dần
C. Không cần sắp xếp
D. Chỉ chứa các số nguyên dương
90. 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 (Array)
B. Danh sách liên kết (Linked List)
C. Heap (Đống)
D. Cây tìm kiếm nhị phân (Binary Search Tree)
91. Độ phức tạp thời gian tốt nhất của thuật toán Insertion Sort là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
92. Ưu điểm chính của thuật toán tìm kiếm nhị phân so với tìm kiếm tuyến tính là gì?
A. Tìm kiếm nhị phân nhanh hơn trên các mảng lớn đã được sắp xếp.
B. Tìm kiếm nhị phân có thể được sử dụng trên các mảng chưa được sắp xếp.
C. Tìm kiếm nhị phân dễ cài đặt hơn.
D. Tìm kiếm nhị phân sử dụng ít bộ nhớ hơn.
93. Thuật toán sắp xếp nào có độ phức tạp thời gian tốt nhất là O(n) khi dữ liệu đầu vào tuân theo một số điều kiện nhất định?
A. Quick Sort
B. Merge Sort
C. Counting Sort
D. Insertion Sort
94. Độ phức tạp thời gian xấu nhất của thuật toán Quick Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
95. Trong thuật toán Bubble Sort, số lượng phép so sánh trong trường hợp xấu nhất là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
96. Trong thuật toán 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. Hàng đợi
C. Heap
D. Đồ thị
97. Thuật toán sắp xếp nào sau đây không phải là so sánh (comparison-based) ?
A. Merge Sort
B. Quick Sort
C. Counting Sort
D. Insertion Sort
98. Thuật toán nào sau đây sử dụng chiến lược ‘chia để trị’ (divide and conquer)?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
99. Thuật toán sắp xếp nào là một thuật toán tại chỗ (in-place)?
A. Merge Sort
B. Quick Sort
C. Counting Sort
D. Radix Sort
100. Độ phức tạp không gian của thuật toán Quick Sort trong trường hợp trung bình là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
101. Thuật toán sắp xếp nào có hiệu suất tốt nhất trong trường hợp mảng gần như đã được sắp xếp?
A. Quick Sort
B. Merge Sort
C. Insertion Sort
D. Selection Sort
102. Độ phức tạp không gian của thuật toán Merge Sort là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
103. Trong thuật toán tìm kiếm nhị phân (Binary Search), điều kiện tiên quyết nào cần được đáp ứng?
A. Mảng phải được sắp xếp.
B. Mảng phải chứa các số nguyên dương.
C. Mảng phải có kích thước là lũy thừa của 2.
D. Mảng không được chứa các phần tử trùng lặp.
104. Ưu điểm của việc sử dụng thuật toán tìm kiếm nhị phân so với tìm kiếm tuyến tính trong một mảng lớn là gì?
A. Tìm kiếm nhị phân có độ phức tạp thời gian thấp hơn.
B. Tìm kiếm nhị phân có thể được sử dụng trên dữ liệu chưa được sắp xếp.
C. Tìm kiếm nhị phân dễ cài đặt hơn.
D. Tìm kiếm nhị phân sử dụng ít bộ nhớ hơn.
105. Khi nào thì thuật toán Insertion Sort được ưu tiên hơn các thuật toán sắp xếp phức tạp hơn như Quick Sort hay Merge Sort?
A. Khi mảng có kích thước lớn.
B. Khi cần sắp xếp dữ liệu trên đĩa.
C. Khi mảng gần như đã được sắp xếp.
D. Khi cần sắp xếp dữ liệu theo thứ tự ngược lại.
106. Trong thuật toán Selection Sort, điều gì xảy ra ở mỗi bước?
A. Tìm phần tử nhỏ nhất và đổi chỗ với phần tử đầu tiên chưa được sắp xếp.
B. Tìm phần tử lớn nhất và đổi chỗ với phần tử cuối cùng chưa được sắp xếp.
C. Đổi chỗ các cặp phần tử liền kề nếu chúng không đúng thứ tự.
D. Chèn phần tử vào vị trí đúng trong phần đã được sắp xếp.
107. Độ phức tạp thời gian trung bình của thuật toán Selection Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
108. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt qua mảng, điều gì được đảm bảo?
A. Phần tử lớn nhất đã được đặt đúng vị trí.
B. Mảng đã được sắp xếp hoàn toàn.
C. Phần tử nhỏ nhất đã được đặt đúng vị trí.
D. Không có sự thay đổi nào trong mảng.
109. Thuật toán sắp xếp nào có độ phức tạp thời gian luôn là O(n log n) trong mọi trường hợp?
A. Quick Sort
B. Merge Sort
C. Insertion Sort
D. Bubble Sort
110. Thuật toán sắp xếp nào sau đây là ổn định (stable)?
A. Quick Sort
B. Heap Sort
C. Selection Sort
D. Insertion Sort
111. Trong thuật toán Bubble Sort, điều gì xảy ra nếu không có sự đổi chỗ nào trong một lần duyệt?
A. Thuật toán kết thúc vì mảng đã được sắp xếp.
B. Thuật toán tiếp tục duyệt qua mảng cho đến khi có sự đổi chỗ.
C. Thuật toán báo lỗi.
D. Thuật toán đảo ngược thứ tự của mảng.
112. Trong thuật toán 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 trái của mảng.
B. Tìm kiếm tiếp tục ở nửa bên phải của mảng.
C. Thuật toán kết thúc và trả về ‘không tìm thấy’.
D. Thuật toán bắt đầu lại từ đầu mảng.
113. Khi nào nên sử dụng thuật toán tìm kiếm tuyến tính thay vì tìm kiếm nhị phân?
A. Khi mảng chưa được sắp xếp.
B. Khi mảng có kích thước lớn.
C. Khi cần tìm kiếm nhiều lần trong cùng một mảng.
D. Khi cần tìm kiếm phần tử lớn nhất trong mảng.
114. Trong thuật toán tìm kiếm tuyến tính (Linear Search), điều gì xảy ra?
A. Duyệt qua từng phần tử của mảng cho đến khi tìm thấy phần tử cần tìm hoặc đến cuối mảng.
B. Chia mảng thành các nửa và tìm kiếm trong nửa thích hợp.
C. Sắp xếp mảng trước khi tìm kiếm.
D. Chỉ tìm kiếm trong các phần tử có giá trị lớn hơn giá trị cần tìm.
115. Thuật toán sắp xếp nào sau đây thường được sử dụng trong thực tế vì hiệu suất trung bình tốt và là thuật toán tại chỗ?
A. Bubble Sort
B. Merge Sort
C. Quick Sort
D. Insertion Sort
116. Thuật toán sắp xếp nào sau đây là thích hợp nhất để sắp xếp một danh sách liên kết (linked list)?
A. Quick Sort
B. Merge Sort
C. Selection Sort
D. Bubble Sort
117. Thuật toán nào sau đây thường được sử dụng để sắp xếp các mảng nhỏ vì tính đơn giản của nó?
A. Quick Sort
B. Merge Sort
C. Insertion Sort
D. Heap Sort
118. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là bao nhiêu?
A. O(n log n)
B. O(n^2)
C. O(log n)
D. O(n)
119. Thuật toán nào sau đây có thể được sử dụng để tìm phần tử lớn thứ k trong một mảng không được sắp xếp?
A. Bubble Sort
B. Quick Select
C. Insertion Sort
D. Selection Sort
120. Thuật toán sắp xếp nào có độ phức tạp thời gian trung bình tốt hơn: Quick Sort hay Merge Sort?
A. Quick Sort
B. Merge Sort
C. Chúng có độ phức tạp thời gian trung bình như nhau.
D. Không thể so sánh vì phụ thuộc vào dữ liệu đầu vào.
121. Cấu trúc dữ liệu nào sau đây cho phép chèn và xóa ở cả hai đầu trong thời gian O(1)?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Deque (Double-ended queue)
D. Danh sách liên kết (Linked list)
122. Trong cây B, bậc của một nút là gì?
A. Số lượng nút con tối đa mà nút đó có thể có
B. Số lượng nút tối thiểu trong cây
C. Chiều cao của cây
D. Tổng số nút trong cây
123. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (quick sort) là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
124. Độ 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(log n)
D. O(n)
125. Độ 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à bao nhiêu?
A. O(n)
B. O(n log n)
C. O(log n)
D. O(1)
126. Thuật toán nào sau đây sử dụng chiến lược ‘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)
127. Độ phức tạp thời gian của thuật toán sắp xếp chọn (selection sort) là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
128. Thuật toán tìm kiếm nào sau đây yêu cầu dữ liệu phải được sắp xếp trước?
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)
129. Phương pháp nào sau đây thường được sử dụng để giải quyết xung đột trong bảng băm?
A. Sắp xếp chèn
B. Địa chỉ mở (Open addressing)
C. Tìm kiếm nhị phân
D. Đệ quy
130. Khi nào thì việc sử dụng danh sách liên kết kép (doubly linked list) hiệu quả hơn danh sách liên kết đơn (singly linked list)?
A. Khi chỉ cần duyệt danh sách theo một hướng
B. Khi cần chèn hoặc xóa nút ở đầu danh sách
C. Khi cần duyệt danh sách theo cả hai hướng
D. Khi cần tiết kiệm bộ nhớ
131. 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
B. Danh sách liên kết
C. Cây
D. Bảng băm
132. 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
B. Danh sách liên kết
C. Heap (đống)
D. Cây tìm kiếm nhị phân
133. Trong thuật toán Bellman-Ford, mục đích là gì?
A. Tìm cây bao trùm nhỏ nhất
B. Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút khác, kể cả khi có cạnh âm
C. Sắp xếp các nút trong đồ thị
D. Tìm đường đi ngắn nhất giữa tất cả các cặp nút
134. Trong thuật toán Floyd-Warshall, mục đích là gì?
A. Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút khác
B. Tìm đường đi ngắn nhất giữa tất cả các cặp nút trong một đồ thị
C. Tìm cây bao trùm nhỏ nhất
D. Sắp xếp các nút trong một đồ thị
135. Khi nào thì việc sử dụng danh sách kề (adjacency list) hiệu quả hơn ma trận kề (adjacency matrix) để biểu diễn đồ thị?
A. Khi đồ thị dày đặc (số lượng cạnh gần bằng số lượng nút bình phương)
B. Khi đồ thị thưa (số lượng cạnh ít hơn nhiều so với số lượng nút bình phương)
C. Khi cần truy cập nhanh các cạnh giữa hai nút bất kỳ
D. Khi cần lưu trữ trọng số của các cạnh
136. Trong cấu trúc dữ liệu heap (đống), phần tử nào luôn nằm ở gốc?
A. Phần tử lớn nhất
B. Phần tử nhỏ nhất
C. Phần tử trung vị
D. Phần tử đầu tiên được chèn vào
137. 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à bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
138. 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)
139. Trong thuật toán Dijkstra, mục đích của việc sử dụng hàng đợi ưu tiên (priority queue) là gì?
A. Để lưu trữ tất cả các nút trong đồ thị
B. Để chọn nút có khoảng cách ngắn nhất từ nút nguồn để thăm tiếp theo
C. Để sắp xếp các cạnh theo trọng số
D. Để theo dõi các nút đã được thăm
140. 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. Danh sách liên kết (Linked list)
D. Cây (Tree)
141. Trong cấu trúc dữ liệu đồ thị, ma trận kề (adjacency matrix) được sử dụng để làm gì?
A. Để lưu trữ danh sách các nút trong đồ thị
B. Để biểu diễn các cạnh giữa các nút trong đồ thị
C. Để lưu trữ trọng số của các cạnh
D. Cả hai đáp án B và C
142. Trong cây đỏ-đen (red-black tree), tính chất nào sau đây luôn đúng?
A. Tất cả các nút đều có màu đỏ
B. Tất cả các nút đều có màu đen
C. Số lượng nút đỏ bằng số lượng nút đen
D. Mọi đường đi từ gốc đến một nút lá đều có cùng số lượng nút đen
143. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) thay vì tìm kiếm theo chiều sâu (DFS)?
A. Khi không gian tìm kiếm rất sâu và có thể vô hạn
B. Khi cần tìm đường đi ngắn nhất giữa hai nút trong một đồ thị không trọng số
C. Khi bộ nhớ là một yếu tố hạn chế
D. Khi cần duyệt tất cả các nút trong đồ thị
144. Ưu điểm chính của việc sử dụng bảng băm (hash table) là gì?
A. Truy cập ngẫu nhiên các phần tử trong thời gian O(1) trung bình
B. Sắp xếp dữ liệu một cách tự động
C. Sử dụng ít bộ nhớ hơn so với mảng
D. Dễ dàng triển khai hơn so với các cấu trúc dữ liệu khác
145. Trong cấu trúc dữ liệu đồ thị, chu trình Euler là gì?
A. Đường đi đi qua tất cả các nút trong đồ thị
B. Đường đi đi qua tất cả các cạnh trong đồ thị mỗi cạnh đúng một lần
C. Đường đi ngắn nhất giữa hai nút
D. Đường đi dài nhất trong đồ thị
146. Cây tìm kiếm nhị phân (BST) nào sau đây đảm bảo chiều cao của cây là O(log n) trong trường hợp xấu nhất, với n là số lượng nút?
A. Cây tìm kiếm nhị phân thông thường
B. Cây AVL
C. Cây lệch (Skew tree)
D. Cây suy biến (Degenerate tree)
147. Trong cấu trúc dữ liệu đồ thị, điều gì xảy ra khi bạn thực hiện tìm kiếm theo chiều sâu (DFS) và gặp một nút đã được thăm?
A. Thuật toán kết thúc
B. Thuật toán tiếp tục từ một nút ngẫu nhiên khác
C. Thuật toán bỏ qua nút đó và tiếp tục tìm kiếm các nút lân cận chưa được thăm
D. Thuật toán quay lại nút cha của nút hiện tại
148. Thuật toán nào sau đây được sử dụng để tìm cây bao trùm nhỏ nhất (minimum spanning tree) trong một đồ thị có trọng số?
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 Kruskal
149. Độ 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)
150. Phương pháp nào sau đây được sử dụng để chuyển đổi khóa thành một chỉ mục trong bảng băm?
A. Sắp xếp
B. Hàm băm (Hash function)
C. Tìm kiếm
D. Đệ quy
