1. Trong ngữ cảnh của cấu trúc dữ liệu đồ thị, thuật ngữ ‘bậc của một đỉnh’ (degree of a vertex) đề cập đến điều gì?
A. Số lượng đỉnh trong đồ thị.
B. Số lượng cạnh trong đồ thị.
C. Số lượng cạnh kết nối với đỉnh đó.
D. Độ dài đường đi ngắn nhất từ đỉnh đó đến một đỉnh khác.
2. 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. 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)
3. Độ 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)
4. Độ phức tạp thời gian để chèn một phần tử vào đầu một danh sách liên kết đơn (singly linked list) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
5. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ ‘cha-con’ trong một hệ thống phân cấp?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
6. Phương pháp tiếp cận lập trình nào thường được sử dụng để giải quyết các bài toán tối ưu hóa, bằng cách chia bài toán thành các bài toán con và lưu trữ kết quả của các bài toán con này để tránh tính toán lại?
A. Tham lam (Greedy)
B. Chia để trị (Divide and Conquer)
C. Quy hoạch động (Dynamic Programming)
D. Backtracking
7. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
8. Cấu trúc dữ liệu nào 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
D. Cây tìm kiếm nhị phân (Binary Search Tree)
9. 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ố dương?
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. Sắp xếp tô pô (Topological Sort)
10. Kiểu dữ liệu trừu tượng (Abstract Data Type – ADT) nào sau đây tuân theo nguyên tắc ‘First In, First Out’ (FIFO)?
A. Stack
B. Tree
C. Queue
D. Graph
11. Cấu trúc dữ liệu nào sử dụng con trỏ để liên kết các phần tử?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Danh sách liên kết (Linked List)
D. Cây (Tree)
12. Phương pháp nào sau đây thường được sử dụng để tìm kiếm một mẫu (pattern) trong một chuỗi văn bản lớn?
A. Thuật toán sắp xếp nổi bọt (Bubble Sort).
B. Thuật toán tìm kiếm nhị phân (Binary Search).
C. Thuật toán KMP (Knuth-Morris-Pratt).
D. Thuật toán sắp xếp chèn (Insertion Sort).
13. Độ 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(log n)
C. O(n log n)
D. O(n)
14. 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?
A. Stack
B. Queue
C. Priority Queue (Heap)
D. Linked List
15. Sắp xếp tô pô (Topological Sort) được sử dụng cho loại đồ thị nào?
A. Đồ thị có hướng không chu trình (Directed Acyclic Graph – DAG)
B. Đồ thị có hướng có chu trình (Directed Cyclic Graph)
C. Đồ thị vô hướng (Undirected Graph)
D. Đồ thị đầy đủ (Complete Graph)
16. Độ phức tạp thời gian của thao tác tìm kiếm trong một cây tìm kiếm nhị phân cân bằng (balanced binary search tree) là bao nhiêu?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
17. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai chức năng ‘undo’ trong các ứng dụng?
A. Hàng đợi (Queue)
B. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
18. Thuật toán nào sau đây được sử dụng để nén dữ liệu mà không làm mất thông tin?
A. JPEG
B. MP3
C. Huffman Coding
D. MPEG
19. Kỹ thuật nào sau đây được sử dụng để giải quyết xung đột trong bảng băm (hash table)?
A. Sắp xếp (Sorting)
B. Tìm kiếm (Searching)
C. Địa chỉ mở (Open Addressing)
D. Đệ quy (Recursion)
20. Trong một đồ thị, một chu trình Euler là gì?
A. Một đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.
B. Một đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.
C. Một đường đi ngắn nhất giữa hai đỉnh.
D. Một đường đi đi qua tất cả các đỉnh và cạnh của đồ thị nhiều lần.
21. Độ phức tạp thời gian tốt nhất cho tìm kiếm một phần tử trong một mảng đã được sắp xếp bằng thuật toán tìm kiếm nhị phân là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
22. Cấu trúc dữ liệu nào cho phép truy cập ngẫu nhiên (random access) đến các phần tử?
A. Danh sách liên kết (Linked List)
B. Hàng đợi (Queue)
C. Mảng (Array)
D. Ngăn xếp (Stack)
23. Thuật toán tìm kiếm nào 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 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)
24. Thuật toán duyệt đồ thị nào sử dụng hàng đợi (queue) để lưu trữ các đỉnh cần thă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. Tìm kiếm A* (A* Search)
D. Thuật toán Dijkstra
25. Độ 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)
C. O(n log n)
D. O(log n)
26. Trong một cây tìm kiếm nhị phân (Binary Search Tree), thuộc tính nào sau đây luôn đúng?
A. Tất cả các nút bên trái lớn hơn nút gốc.
B. Tất cả các nút bên phải nhỏ hơn nút gốc.
C. Tất cả các nút bên trái nhỏ hơn nút gốc và tất cả các nút bên phải lớn hơn nút gốc.
D. Tất cả các nút đều có giá trị bằng nhau.
27. Trong cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree) như cây AVL hoặc cây đỏ-đen, mục đích của việc cân bằng cây là gì?
A. Để giảm độ phức tạp không gian của cây.
B. Để đảm bảo rằng tất cả các nút đều có cùng số lượng nút con.
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. Để tăng tốc độ duyệt cây theo thứ tự trước (pre-order traversal).
28. Cấu trúc dữ liệu nào sau đây là một dạng của cây, trong đó mỗi nút có thể có nhiều hơn hai nút con?
A. Cây tìm kiếm nhị phân (Binary Search Tree)
B. Cây AVL
C. Cây B
D. Heap
29. Thuật toán sắp xếp nào sau đây có hiệu suất tốt nhất trong trường hợp dữ liệu gần như đã được sắp xếp?
A. Quick Sort
B. Merge Sort
C. Insertion Sort
D. Selection Sort
30. Thuật toán sắp xếp nào 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 trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
31. Giải thuật nào sau đây là một thuật toán chia để trị?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
32. Cấu trúc dữ liệu nào được sử dụng để triển khai thuật toán Breadth-First Search (BFS)?
A. Stack
B. Queue
C. Tree
D. Graph
33. 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 (Tập hợp)
D. Linked List
34. 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. Dijkstra’s Algorithm
B. Bellman-Ford Algorithm
C. Prim’s Algorithm
D. Depth-First Search
35. Ưu điểm chính của việc sử dụng cây tìm kiếm B (B-tree) là gì?
A. Hiệu suất tốt cho dữ liệu lưu trữ trên đĩa
B. Dễ dàng triển khai
C. Tìm kiếm nhanh chóng trong bộ nhớ
D. Sử dụng ít bộ nhớ
36. Khi nào thì nên sử dụng bảng băm (hash table) thay vì cây tìm kiếm?
A. Khi cần duy trì thứ tự các phần tử
B. Khi cần tìm phần tử nhỏ nhất
C. Khi cần tìm kiếm, chèn và xóa nhanh chóng
D. Khi cần duyệt tất cả các phần tử theo thứ tự
37. Trong ngữ cảnh của đồ thị, thuật toán nào được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác?
A. Prim’s Algorithm
B. Kruskal’s Algorithm
C. Dijkstra’s Algorithm
D. Breadth-First Search
38. Độ phức tạp thời gian tốt nhất cho tìm kiếm một phần tử trong một mảng đã sắp xếp sử dụng tìm kiếm nhị phân là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
39. Trong thuật toán Bellman-Ford, mục đích chính của việc thực hiện V-1 lần lặp (V là số đỉnh) là gì?
A. Tìm đường đi ngắn nhất trong đồ thị không có chu trình âm
B. Tìm đường đi ngắn nhất trong đồ thị có chu trình dương
C. Phát hiện chu trình âm
D. Tìm cây khung nhỏ nhất
40. Ưu điểm của việc sử dụng hàng đợi ưu tiên (priority queue) là gì?
A. Truy cập ngẫu nhiên nhanh chóng
B. Loại bỏ phần tử có độ ưu tiên cao nhất một cách hiệu quả
C. Sắp xếp các phần tử theo thứ tự thêm vào
D. Lưu trữ dữ liệu theo nguyên tắc FIFO
41. Trong thuật toán sắp xếp nhanh (Quick Sort), kỹ thuật nào được sử dụng để chọn phần tử chốt?
A. Chọn phần tử đầu tiên
B. Chọn phần tử cuối cùng
C. Chọn phần tử ngẫu nhiên
D. Tất cả các phương án trên
42. Trong thuật toán Kruskal, cấu trúc dữ liệu nào được sử dụng để kiểm tra xem hai đỉnh có thuộc cùng một thành phần liên thông hay không?
A. Stack
B. Queue
C. Union-Find (Disjoint Set)
D. Linked List
43. Độ phức tạp thời gian của thao tác tìm kiếm trong một cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
44. Cấu trúc dữ liệu nào cho phép chèn và xóa các phần tử ở cả đầu và cuối với độ phức tạp thời gian O(1)?
A. Stack
B. Queue
C. Deque (Double-Ended Queue)
D. Linked List
45. Khi nào thì nên sử dụng thuật toán tham lam (Greedy Algorithm)?
A. Khi cần tìm nghiệm tối ưu toàn cục
B. Khi bài toán có cấu trúc con tối ưu
C. Khi cần duyệt tất cả các khả năng
D. Khi không gian tìm kiếm rất lớn
46. Thuật toán sắp xếp nào có độ phức tạp thời gian tồi tệ nhất là O(n^2) nhưng thường hoạt động tốt trong thực tế?
A. Merge Sort
B. Heap Sort
C. Quick Sort
D. Insertion Sort
47. Khi nào thì 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) trong đồ thị?
A. Khi không gian tìm kiếm rất sâu
B. Khi cần tìm đường đi ngắn nhất
C. Khi cần duyệt toàn bộ đồ thị
D. Khi đồ thị có chu trình
48. Độ phức tạp thời gian để chèn một phần tử vào đầu một danh sách liên kết đơn là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
49. Cấu trúc dữ liệu nào thường được sử dụng để triển khai chức năng ‘undo’ trong các ứng dụng?
A. Queue
B. Stack
C. Linked List
D. Tree
50. Thuật toán sắp xếp nào 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
51. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ phân cấp?
A. Linked List
B. Array
C. Tree
D. Queue
52. Trong thuật toán Heap Sort, cấu trúc dữ liệu nào được sử dụng?
A. Queue
B. Stack
C. Heap
D. Linked List
53. 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
54. Khi nào thì nên sử dụng thuật toán tìm kiếm tuyến tính (Linear Search) thay vì tìm kiếm nhị phân (Binary Search)?
A. Khi mảng đã được sắp xếp
B. Khi mảng có kích thước rất lớn
C. Khi mảng chưa được sắp xếp
D. Khi cần tìm phần tử lớn nhất
55. Cấu trúc dữ liệu nào cho phép truy cập phần tử đầu và cuối với độ phức tạp thời gian O(1)?
A. Stack
B. Queue
C. Deque (Double-Ended Queue)
D. Linked List
56. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc ‘First In, First Out’ (FIFO)?
A. Stack
B. Queue
C. Tree
D. Graph
57. Ưu điểm chính của việc sử dụng danh sách liên kết so với mảng 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 biết trước kích thước
C. Dễ dàng chèn và xóa các phần tử
D. Tìm kiếm nhanh hơn
58. Trong một bảng băm (hash table), điều gì xảy ra khi hai khóa khác nhau băm đến cùng một vị trí?
A. Xảy ra lỗi
B. Ghi đè giá trị cũ
C. Xử lý xung đột (collision)
D. Bảng băm tự động tăng kích thước
59. Cấu trúc dữ liệu nào phù hợp nhất để kiểm tra xem một dấu ngoặc có hợp lệ không (ví dụ: ‘(){}[]’)?
A. Queue
B. Stack
C. Linked List
D. Tree
60. Trong lập trình động (Dynamic Programming), kỹ thuật nào được sử dụng để tránh tính toán lại các bài toán con đã giải?
A. Divide and Conquer
B. Greedy Approach
C. Memoization
D. Backtracking
61. 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. Stack
C. Linked List
D. Tree
62. Ư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 ít bộ nhớ hơn
C. Dễ dàng chèn và xóa phần tử
D. Tìm kiếm phần tử nhanh hơn
63. 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. Merge Sort
B. Quick Sort
C. Heap Sort
D. Radix Sort
64. Hàm băm (hash function) tốt cần có thuộc tính nào sau đây?
A. Luôn tạo ra cùng một giá trị băm cho các khóa khác nhau
B. Phân phối đều các khóa vào các ô băm
C. Luôn tạo ra các giá trị băm khác nhau cho cùng một khóa
D. Có độ phức tạp tính toán cao
65. Thuật toán nào sau đây là một thuật toán chia để trị (divide and conquer algorithm)?
A. Insertion Sort
B. Bubble Sort
C. Merge Sort
D. Selection Sort
66. Thuật toán nào sau đây là một thuật toán tham lam (greedy algorithm) đượ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. Kruskal’s Algorithm
C. Depth-First Search (DFS)
D. Breadth-First Search (BFS)
67. Trong cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree), mục đích của việc cân bằng cây là gì?
A. Để giảm độ phức tạp không gian
B. Để đảm bảo độ phức tạp thời gian O(1) cho tất cả các thao tác
C. Để ngăn chặn cây trở thành một danh sách liên kết suy biến, đả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. Để tăng số lượng nút trong cây
68. 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, nhưng lại không ổn định (unstable)?
A. Insertion Sort
B. Merge Sort
C. Quick Sort
D. Bubble Sort
69. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ nhiều-nhiều giữa các thực thể?
A. Stack
B. Queue
C. Graph
D. Tree
70. Độ 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ụ: AVL tree, Red-Black tree) là bao nhiêu?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(1)
71. Thuật toán nào sau đây có thể được sử dụng để tìm chu trình trong một đồ thị có hướng?
A. Dijkstra’s Algorithm
B. Breadth-First Search (BFS)
C. Depth-First Search (DFS)
D. Prim’s Algorithm
72. 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 trong hầu hết các trường hợp?
A. Bubble Sort
B. Insertion Sort
C. Quick Sort
D. Selection Sort
73. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán A* tìm đường đi (A* pathfinding algorithm)?
A. Stack
B. Queue
C. Priority Queue
D. Linked List
74. Trong thuật toán duyệt đồ thị theo chiều sâu (DFS), cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ các đỉnh cần duyệt?
A. Queue
B. Stack
C. Linked List
D. Heap
75. Trong bảng băm (hash table), kỹ thuật nào sau đây được sử dụng để xử lý xung đột khi hai khóa khác nhau được băm vào cùng một vị trí?
A. Sắp xếp (Sorting)
B. Tìm kiếm nhị phân (Binary Search)
C. Liên kết chuỗi (Chaining)
D. Đệ quy (Recursion)
76. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai một bộ nhớ cache (cache memory)?
A. Stack
B. Queue
C. Hash Table
D. Linked List
77. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi ngoặc có hợp lệ hay không (ví dụ: ‘(){}[]’)?
A. Queue
B. Stack
C. Linked List
D. Tree
78. Ưu điểm chính của việc sử dụng hàng đợi ưu tiên (priority queue) là gì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng ít bộ nhớ hơn
C. Cho phép truy cập vào phần tử có độ ưu tiên cao nhất
D. Tìm kiếm phần tử nhanh hơn
79. 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. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
80. 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
B. Tree
C. Queue
D. Linked List
81. Trong cây tìm kiếm nhị phân (binary search tree), thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n)?
A. Duyệt cây theo chiều rộng (Breadth-First Traversal)
B. Duyệt cây theo chiều sâu (Depth-First Traversal)
C. Tìm kiếm một phần tử
D. Sắp xếp các phần tử trong cây
82. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn quan hệ ‘cha-con’ trong một tổ chức?
A. Queue
B. Stack
C. Graph
D. Tree
83. Độ phức tạp thời gian của thao tác xóa một phần tử khỏi một danh sách liên kết đơn (singly linked list) là bao nhiêu, nếu chúng ta đã có con trỏ đến phần tử đó?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
84. Cấu trúc dữ liệu nào sau đây cho phép truy cập các phần tử theo chỉ số (index) với độ phức tạp thời gian O(1)?
A. Linked List
B. Tree
C. Array
D. Graph
85. Độ 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 log n)
B. O(n^2)
C. O(n)
D. O(log n)
86. Cấu trúc dữ liệu nào sau đây sử dụng con trỏ để liên kết các phần tử?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
87. Trong cấu trúc dữ liệu đồ 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 nguồn đến tất cả các đỉnh khác?
A. Breadth-First Search (BFS)
B. Depth-First Search (DFS)
C. Dijkstra’s Algorithm
D. Binary Search
88. Độ phức tạp thời gian của thao tác chèn vào một heap (min-heap hoặc max-heap) là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(log n)
D. O(1)
89. Trong thuật toán tìm kiếm nhị phân (binary search), điều kiện tiên quyết nào sau đây phải được đáp ứng để thuật toán hoạt động chính xác?
A. Dữ liệu phải được sắp xếp
B. Dữ liệu phải là số nguyên
C. Dữ liệu phải là duy nhất
D. Dữ liệu phải có kích thước cố định
90. Khi nào nên sử dụng cấu trúc dữ liệu Trie?
A. Khi cần lưu trữ dữ liệu số nguyên lớn
B. Khi cần tìm kiếm các chuỗi có chung tiền tố một cách hiệu quả
C. Khi cần sắp xếp dữ liệu nhanh chóng
D. Khi cần biểu diễn mối quan hệ giữa các đối tượng
91. Thuật toán sắp xếp nào có hiệu suất tốt nhất trong trường hợp dữ liệu gần như đã được sắp xếp?
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 nổi bọt (Bubble Sort)
92. Cấu trúc dữ liệu nào 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. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
93. Thuật toán nào sau đây là một ví dụ của thuật toán tham lam (greedy algorithm)?
A. Thuật toán Dijkstra
B. Tìm kiếm nhị phân (Binary Search)
C. Sắp xếp trộn (Merge Sort)
D. Lập trình động (Dynamic Programming)
94. Cấu trúc dữ liệu nào 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
D. Cây nhị phân tìm kiếm (Binary Search Tree)
95. Cấu trúc dữ liệu nào được sử dụng để biểu diễn mối quan hệ ‘cha-con’ phân cấp?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Đồ thị (Graph)
96. Trong một đồ thị có hướng (directed graph), điều gì tạo nên một thành phần liên thông mạnh (strongly connected component)?
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ó một đường đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác trong tập hợp.
C. Một tập hợp các đỉnh mà tất cả đều có bậc vào bằng 0.
D. Một tập hợp các đỉnh mà tất cả đều có bậc ra bằng 0.
97. Trong đồ thị, một chu trình (cycle) là gì?
A. Một đường đi không chứa cạnh lặp lại.
B. Một đường đi bắt đầu và kết thúc ở cùng một đỉnh.
C. Một đường đi chứa tất cả các đỉnh của đồ thị.
D. Một đường đi ngắn nhất giữa hai đỉnh.
98. Độ 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)
99. Cây đỏ-đen (red-black tree) là một loại cấu trúc dữ liệu nào?
A. Cây nhị phân tìm kiếm không cân bằng.
B. Cây nhị phân tìm kiếm tự cân bằng.
C. Heap
D. Đồ thị
100. Trong một cây quyết định (decision tree), mục đích của việc cắt tỉa (pruning) là gì?
A. Tăng độ phức tạp của cây.
B. Giảm hiện tượng quá khớp (overfitting).
C. Tăng độ chính xác trên dữ liệu huấn luyện.
D. Làm cho cây dễ diễn giải hơn.
101. Cấu trúc dữ liệu nào tuân theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
102. 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. 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
103. Độ phức tạp thời gian xấu 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)
104. Cấu trúc dữ liệu nào là một tập hợp các nút, mỗi nút trỏ đến các nút khác?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Hàng đợi (Queue)
D. Ngăn xếp (Stack)
105. Mục đích chính của việc sử dụng cấu trúc dữ liệu là gì?
A. Để làm cho code trông phức tạp hơn.
B. Để lưu trữ và tổ chức dữ liệu một cách hiệu quả để sử dụng.
C. Để giảm kích thước của chương trình.
D. Để tăng tốc độ biên dịch.
106. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân là gì?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
107. Trong lập trình động (dynamic programming), kỹ thuật ghi nhớ (memoization) là gì?
A. Tối ưu hóa việc sử dụng bộ nhớ.
B. Lưu trữ kết quả của các tính toán tốn kém và trả về kết quả đã lưu khi đầu vào tương tự xảy ra lại.
C. Chia nhỏ vấn đề thành các bài toán con nhỏ hơn.
D. Sử dụng đệ quy để giải quyết vấn đề.
108. Trong một hàm đệ quy, điều gì xảy ra nếu không có trường hợp cơ bản (base case)?
A. Hàm sẽ trả về một giá trị ngẫu nhiên.
B. Hàm sẽ thực hiện một lần duy nhất.
C. Hàm sẽ gây ra lỗi tràn bộ nhớ ngăn xếp (stack overflow).
D. Hàm sẽ không thực hiện gì cả.
109. Sự khác biệt chính giữa mảng (array) và danh sách liên kết (linked list) là gì?
A. Mảng có kích thước cố định, danh sách liên kết có kích thước động.
B. Mảng lưu trữ các phần tử không liên tục, danh sách liên kết lưu trữ các phần tử liên tục.
C. Mảng chỉ có thể lưu trữ các số nguyên, danh sách liên kết có thể lưu trữ bất kỳ kiểu dữ liệu nào.
D. Mảng nhanh hơn để chèn và xóa các phần tử.
110. 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. Tìm kiếm tuyến tính (Linear Search)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp nổi bọt (Bubble Sort)
D. Sắp xếp nhanh (Quick Sort)
111. Trong ngữ cảnh của bảng băm (hash table), ‘collision’ xảy ra khi nào?
A. Khi bảng băm đầy.
B. Khi hai khóa khác nhau được băm vào cùng một vị trí.
C. Khi một khóa không tìm thấy trong bảng băm.
D. Khi bảng băm cần thay đổi kích thước.
112. Cấu trúc dữ liệu nào cho phép chèn và xóa ở 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)
113. Cây nào sau đây đảm bảo rằng chiều cao của cây luôn là O(log n), trong đó n là số lượng nút?
A. Cây nhị phân tìm kiếm (Binary Search Tree)
B. Cây AVL
C. Cây suy biến (Degenerate Tree)
D. Cây hoàn chỉnh (Complete Binary Tree)
114. Trong cây nhị phân tìm kiếm (BST), nút gốc (root node) có đặc điểm gì?
A. Nó luôn là nút lá.
B. Nó không có nút con.
C. Nó là nút cao nhất trong cây.
D. Nó là nút duy nhất không có nút cha.
115. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa hai nút trong một đồ thị có trọng số dương?
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
116. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm (hash table) là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
117. 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 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. Tìm kiếm tuyến tính (Linear Search)
118. Thuật toán tìm kiếm theo chiều rộng (BFS) thường được sử dụng để giải quyết vấn đề nào?
A. Tìm đường đi ngắn nhất trong đồ thị không trọng số.
B. Tìm đường đi ngắn nhất trong đồ thị có trọng số.
C. Tìm cây khung nhỏ nhất.
D. Tìm tất cả các đường đi có thể giữa hai đỉnh.
119. Thuật toán sắp xếp nào 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 trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
120. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu?
A. Thuật toán Dijkstra
B. Thuật toán Kruskal
C. Thuật toán Huffman
D. Tìm kiếm nhị phân (Binary Search)
121. Thuật toán Prim được sử dụng để giải quyết vấn đề gì?
A. Tìm đường đi ngắn nhất trong đồ thị
B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) trong đồ thị
C. Sắp xếp các đỉnh của đồ thị
D. Tìm kiếm một đỉnh cụ thể trong đồ thị
122. Trong cấu trúc dữ liệu cây (Tree), nút nào không có nút con được gọi là gì?
A. Nút gốc (Root)
B. Nút lá (Leaf)
C. Nút cha (Parent)
D. Nút con (Child)
123. 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
D. Cây nhị phân tìm kiếm (Binary Search Tree)
124. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán duyệt đồ thị theo chiều rộng (Breadth-First Search)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
125. Độ 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à gì?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(n log n)
126. Chức năng của hàm băm (Hash Function) là gì?
A. Sắp xếp dữ liệu
B. Chuyển đổi khóa thành chỉ số trong bảng băm
C. Tìm kiếm dữ liệu
D. Xóa dữ liệu
127. 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 độ phức tạp thời gian O(n log n) trong mọi trường hợp
B. Khi không gian bộ nhớ là một yếu tố quan trọng
C. Khi dữ liệu đã gần như được sắp xếp
D. Khi cần sắp xếp dữ liệu trên đĩa
128. Sự khác biệt chính giữa hàng đợi (Queue) và ngăn xếp (Stack) là gì?
A. Hàng đợi sử dụng bộ nhớ nhiều hơn ngăn xếp
B. Hàng đợi hoạt động theo nguyên tắc FIFO (First In, First Out), trong khi ngăn xếp hoạt động theo nguyên tắc LIFO (Last In, First Out)
C. Ngăn xếp chỉ có thể lưu trữ số nguyên, trong khi hàng đợi có thể lưu trữ bất kỳ loại dữ liệu nào
D. Ngăn xếp nhanh hơn hàng đợi
129. Độ 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 tốt nhất là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
130. Độ 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(1)
B. O(log n)
C. O(n)
D. O(n log n)
131. Thuật toán Kruskal được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho một đồ thị liên thông có trọng số.
C. Sắp xếp các đỉnh của một đồ thị theo thứ tự tăng dần của trọng số.
D. Kiểm tra xem một đồ thị có phải là đồ thị hai phía (bipartite) hay không.
132. 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 B
D. Heap
133. Heap (cấu trúc dữ liệu) là gì?
A. Một mảng đã được sắp xếp.
B. Một cây nhị phân hoàn chỉnh, trong đó giá trị của mỗi nút cha lớn hơn hoặc bằng (hoặc nhỏ hơn hoặc bằng) giá trị của các nút con của nó.
C. Một danh sách liên kết đôi.
D. Một đồ thị không có chu trình.
134. Chức năng nào sau đây KHÔNG phải là một hoạt động cơ bản trên cấu trúc dữ liệu ngăn xếp (Stack)?
A. Push
B. Pop
C. Peek
D. Search
135. 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. 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)
136. Kỹ thuật ‘memoization’ thường được sử dụng để tối ưu hóa thuật toán nào?
A. Thuật toán tham lam (Greedy algorithms).
B. Thuật toán chia để trị (Divide and conquer algorithms).
C. Thuật toán quy hoạch động (Dynamic programming algorithms).
D. Thuật toán duyệt đồ thị (Graph traversal algorithms).
137. Cấu trúc dữ liệu nào sau đây là phi tuyến tính?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Hàng đợi (Queue)
D. Đồ thị (Graph)
138. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
139. Giải thuật Dijkstra được sử dụng để giải quyết vấn đề gì?
A. Tìm kiếm một phần tử trong mảng
B. Tìm đường đi ngắn nhất giữa các đỉnh trong đồ thị
C. Sắp xếp một mảng các số
D. Tìm kiếm một chuỗi con trong một chuỗi
140. Điều gì xảy ra nếu bạn cố gắng ‘pop’ một phần tử từ một ngăn xếp (Stack) trống?
A. Trả về null
B. Gây ra lỗi tràn ngăn xếp (Stack Overflow)
C. Gây ra lỗi tràn bộ nhớ (Memory Overflow)
D. Gây ra lỗi tràn dưới (Stack Underflow)
141. Độ 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)
142. Thuật toán sắp xếp nào 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 trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
143. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân là gì?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
144. Khi nào nên sử dụng danh sách liên kết đơn thay vì danh sách liên kết đôi?
A. Khi cần duyệt danh sách theo cả hai hướng
B. Khi cần chèn hoặc xóa nút ở giữa danh sách thường xuyên
C. Khi không gian bộ nhớ là một yếu tố quan trọng
D. Khi cần tìm kiếm một nút cụ thể nhanh chóng
145. Trong cây nhị phân hoàn chỉnh (Complete Binary Tree), số lượng nút ở mức ‘l’ là bao nhiêu?
A. l
B. 2^l
C. 2^(l-1)
D. l^2
146. Cây tìm kiếm nhị phân (Binary Search Tree) có đặc điểm gì?
A. Tất cả các nút đều có giá trị bằng nhau
B. Giá trị của nút gốc lớn hơn tất cả các nút con
C. Giá trị của tất cả các nút bên trái nhỏ hơn nút gốc, và giá trị của tất cả các nút bên phải lớn hơn nút gốc
D. Tất cả các nút đều là nút lá
147. Ưu điểm chính của việc sử dụng bảng băm (hash table) so với cây tìm kiếm là gì?
A. Bảng băm đảm bảo thời gian truy cập O(log n) trong trường hợp xấu nhất.
B. Bảng băm luôn sử dụng ít bộ nhớ hơn cây tìm kiếm.
C. Bảng băm thường có thời gian truy cập trung bình nhanh hơn, O(1).
D. Bảng băm có thể dễ dàng sắp xếp các phần tử theo thứ tự.
148. Thuật toán tìm kiếm nào 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 (Depth-First Search)
D. Tìm kiếm theo chiều rộng (Breadth-First Search)
149. 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 (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. Duyệt theo chiều rộng (Breadth-First Search)
150. Ưu điểm chính của việc sử dụng danh sách liên kết so với mảng 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 dễ dàng hơn
