1. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n^2)
2. 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 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 phần tử
D. Duyệt cây theo thứ tự giữa (inorder traversal)
3. Trong cấu trúc dữ liệu đồ thị (graph), ma trận kề (adjacency matrix) được sử dụng để biểu diễn điều gì?
A. Danh sách các đỉnh
B. Danh sách các cạnh
C. Mối quan hệ kề giữa các đỉnh
D. Trọng số của các cạnh
4. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Ngăn xếp (Stack)
5. Thuật toán sắp xếp nào sau đây hoạt động tốt nhất trên các tậ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 vun đống (Heap Sort)
6. 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 nguồn đến tất cả các đỉnh khác?
A. Tìm kiếm theo chiều sâu (Depth-First Search – DFS)
B. Tìm kiếm theo chiều rộng (Breadth-First Search – BFS)
C. Thuật toán Dijkstra
D. Thuật toán Prim
7. 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)
8. Trong cấu trúc dữ liệu cây, chiều cao của cây được định nghĩa là gì?
A. Số lượng nút trong cây
B. Số lượng lá trong cây
C. Độ dài đường đi dài nhất từ nút gốc đến một nút lá
D. Số lượng nút trên mức cao nhất
9. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n)?
A. Sắp xếp chèn (Insertion Sort)
B. Sắp xếp nổi bọt (Bubble Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
10. Trong một cây nhị phân tìm kiếm cân bằng (balanced binary search tree), sự cân bằng có nghĩa là gì?
A. Tất cả các nút đều có hai con
B. Số lượng nút bên trái và bên phải của mỗi nút là bằng nhau
C. Chiều cao của các cây con trái và phải của mỗi nút không khác nhau quá một
D. Tất cả các nút lá đều ở cùng một mức
11. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để phát hiện chu trình (cycle)?
A. Thuật toán Dijkstra
B. Tìm kiếm theo chiều rộng (BFS)
C. Tìm kiếm theo chiều sâu (DFS)
D. Thuật toán Prim
12. Ứng dụng nào sau đây là phù hợp nhất cho cấu trúc dữ liệu hàng đợi (queue)?
A. Quản lý lịch sử duyệt web
B. Đánh giá biểu thức số học
C. In tài liệu theo thứ tự gửi
D. Tìm kiếm đường đi trong mê cung
13. Ư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 dữ liệu không xác định trước
C. Tìm kiếm phần tử nhanh hơn
D. Sắp xếp dữ liệu nhanh hơn
14. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp nổi bọt (bubble sort) là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
15. Thuật toán 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. Tìm kiếm nhị phân (Binary Search)
16. Khi nào nên sử dụng bảng băm (hash table) thay vì cây tìm kiếm?
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 các phần tử được sắp xếp
17. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong danh sách liên kết (linked list) là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
18. Trong một 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 thành 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 một phần tử bị xóa khỏi bảng băm
19. 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 node)
B. Nút lá (leaf node)
C. Nút cha (parent node)
D. Nút trung gian (internal node)
20. 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 Floyd-Warshall
C. Thuật toán Prim
D. Thuật toán tìm kiếm nhị phân
21. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS) thay vì tìm kiếm theo chiều rộng (Breadth-First Search – BFS)?
A. Khi cần tìm đường đi ngắn nhất
B. Khi không gian tìm kiếm rất lớn và có thể có các nhánh vô hạn
C. Khi cần tìm tất cả các đỉnh có thể truy cập được từ một đỉnh nguồn
D. Khi cần duyệt tất cả các đỉnh của đồ thị
22. Cấu trúc dữ liệu nào sau đây được sử dụng để triển khai thuật toán tìm kiếm theo chiều rộng (Breadth-First Search – BFS)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
23. Ưu điểm của việc sử dụng danh sách liên kết đôi (doubly linked list) so với danh sách liên kết đơn (singly linked list) là gì?
A. Sử dụng ít bộ nhớ hơn
B. Duyệt danh sách theo cả hai hướng
C. Chèn phần tử nhanh hơn
D. Xóa phần tử nhanh hơn
24. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn hàng đợi ưu tiên (priority queue)?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây nhị phân tìm kiếm (Binary Search Tree)
D. Heap
25. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai bộ nhớ cache?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Bảng băm (Hash Table)
D. Cây nhị phân tìm kiếm (Binary Search Tree)
26. Điều gì xảy ra nếu bạn chèn một phần tử vào một hàng đợi (queue) đã đầy?
A. Phần tử mới sẽ thay thế phần tử đầu tiên trong hàng đợi
B. Phần tử mới sẽ bị bỏ qua
C. Gây ra lỗi tràn hàng đợi (queue overflow)
D. Hàng đợi sẽ tự động tăng kích thước
27. Thuật toán nào sau đây là một ví dụ về kỹ thuật ‘chia để trị’ (divide and conquer)?
A. Sắp xếp chèn (Insertion Sort)
B. Sắp xếp nổi bọt (Bubble Sort)
C. Sắp xếp nhanh (Quick Sort)
D. Sắp xếp chọn (Selection Sort)
28. Độ 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)
29. Điều gì xảy ra khi bạn cố gắng lấy một phần tử từ một ngăn xếp (stack) trống?
A. Trả về giá trị null
B. Trả về phần tử cuối cùng đã được thêm vào
C. Gây ra lỗi tràn ngăn xếp (stack overflow)
D. Gây ra lỗi tràn bộ nhớ (out of memory)
30. Trong cây nhị phân (binary tree), duyệt cây theo thứ tự giữa (inorder traversal) thường được sử dụng để làm gì?
A. Sao chép cây
B. Xóa cây
C. In các nút theo thứ tự tăng dần (trong cây nhị phân tìm kiếm)
D. Tìm chiều cao của cây
31. Trong cây B, bậc của cây (order) xác định điều gì?
A. Chiều cao của 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. Số lượng lá tối thiểu trong cây
32. Trong cấu trúc dữ liệu heap, phần tử nào luôn nằm ở gốc?
A. Phần tử nhỏ nhất (min heap) hoặc lớn nhất (max heap)
B. Phần tử trung vị
C. Phần tử đầu tiên được chèn vào
D. Phần tử cuối cùng được chèn vào
33. Cấu trúc dữ liệu nào sau đây đượ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. Cây nhị phân tìm kiếm (Binary Search Tree)
D. Heap
34. Ưu điểm 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ử với độ phức tạp trung bình O(1)
C. Sử dụng bộ nhớ hiệu quả hơn so với mảng
D. Triển khai đơn giản hơn so với cây nhị phân tìm kiếm
35. Trong cây AVL, thao tác nào được sử dụng để duy trì tính cân bằng?
A. Tìm kiếm (Search)
B. Xoay (Rotation)
C. Chèn (Insert)
D. Xóa (Delete)
36. 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 rộng (Breadth-First Search)
D. Tìm kiếm theo chiều sâu (Depth-First Search)
37. Trong một đồ 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. Tìm kiếm theo chiều sâu (Depth-First Search)
B. Tìm kiếm theo chiều rộng (Breadth-First Search)
C. Thuật toán Dijkstra
D. Thuật toán sắp xếp tô pô (Topological Sort)
38. Trong cấu trúc dữ liệu đồ thị, ma trận kề (adjacency matrix) được sử dụng để biểu diễn điều gì?
A. Danh sách các đỉnh của đồ thị
B. Danh sách các cạnh của đồ thị
C. Mối quan hệ kề giữa các đỉnh
D. Trọng số của các cạnh
39. 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. Cây Heap
40. Cấu trúc dữ liệu nào sau đây thích hợp nhất để kiểm tra xem một biểu thức toán học có cân bằng dấu ngoặc hay không?
A. Hàng đợi (Queue)
B. Mảng (Array)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
41. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai chức năng ‘hoàn tác’ (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)
42. Thuật toán Prim được sử dụng để giải quyết bài toán nào?
A. Tìm đường đi ngắn nhất giữa hai đỉnh
B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)
C. Sắp xếp các đỉnh của đồ thị
D. Tìm chu trình Euler
43. Trong thuật toán tìm kiếm theo chiều sâu (Depth-First Search), cấu trúc dữ liệu nào được sử dụng để theo dõi các đỉnh đã được thăm?
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)
44. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào sau đây có độ phức tạp thời gian 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ự sau (Postorder Traversal)
C. Tìm kiếm một nút (Search a node)
D. Duyệt cây theo thứ tự giữa (Inorder Traversal)
45. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Ngăn xếp (Stack)
46. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều rộng (Breadth-First Search)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
47. Độ 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)
B. O(n^2)
C. O(n log n)
D. O(log n)
48. Thuật toán Floyd-Warshall được sử dụng để giải quyết bài toán nào?
A. Tìm đường đi ngắn nhất giữa hai đỉnh
B. Tìm cây khung nhỏ nhất
C. Tìm tất cả các cặp đường đi ngắn nhất (All-Pairs Shortest Paths)
D. Sắp xếp các đỉnh của đồ thị
49. Ư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
C. Dễ dàng chèn và xóa phần tử
D. Tìm kiếm phần tử nhanh hơn
50. Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
51. Thuật toán nào sau đây là một ví dụ về kỹ thuật ‘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 trộn (Merge Sort)
52. Trong bảng băm, ‘hàm băm’ (hash function) có vai trò gì?
A. Sắp xếp các phần tử trong bảng
B. Tìm kiếm một phần tử cụ thể
C. Ánh xạ khóa (key) đến một chỉ số trong bảng
D. Giải quyết xung đột
53. Ưu điểm chính của việc sử dụng danh sách liên kết đôi (doubly linked list) so với danh sách liên kết đơn (singly linked list) là gì?
A. Sử dụng ít bộ nhớ hơn
B. Truy cập phần tử nhanh hơn
C. Dễ dàng duyệt theo cả hai hướng
D. Chèn và xóa phần tử nhanh hơn
54. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
55. Trong thuật toán Kruskal, cấu trúc dữ liệu nào được sử dụng để kiểm tra xem việc thêm một cạnh có tạo thành chu trình hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Union-Find (Disjoint Set)
D. Cây nhị phân tìm kiếm (Binary Search Tree)
56. 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 trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
57. Trong cây nhị phân đầy đủ (Full Binary Tree), nếu số nút là N, thì số lá (leaf nodes) là bao nhiêu?
A. N/2
B. (N + 1) / 2
C. N – 1
D. log2(N)
58. Sắp xếp tô pô (Topological Sort) được áp dụng cho loại đồ thị nào?
A. Đồ thị vô hướng (Undirected Graph)
B. Đồ thị có hướng không chu trình (Directed Acyclic Graph – DAG)
C. Đồ thị có trọng số âm (Graph with negative weights)
D. Đồ thị đầy đủ (Complete Graph)
59. Độ 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(log n)
C. O(n^2)
D. O(n log n)
60. Phương pháp 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 nổi bọt (Bubble Sort)
B. Tìm kiếm nhị phân (Binary Search)
C. Địa chỉ mở (Open Addressing) và Liên kết riêng (Separate Chaining)
D. Duyệt cây theo thứ tự trước (Preorder Traversal)
61. Trong cấu trúc dữ liệu đồ thị, chu trình (cycle) là gì?
A. Một đường đi không chứa đỉnh lặp lại
B. Một đường đi bắt đầu và kết thúc tại cùng một đỉnh
C. Một đường đi ngắn nhất giữa hai đỉnh
D. Một đường đi chứa tất cả các đỉnh của đồ thị
62. Trong cây, nút nào không có nút con được gọi là gì?
A. Nút gốc
B. Nút lá
C. Nút trung gian
D. Nút cha
63. Ưu điểm của việc sử dụng bảng băm (hash table) là gì?
A. Truy cập phần tử với độ phức tạp O(n)
B. Duy trì thứ tự của các phần tử
C. Tìm kiếm, chèn, và xóa phần tử với độ phức tạp trung bình O(1)
D. Sử dụng bộ nhớ hiệu quả hơn so với mảng
64. Cấu trúc dữ liệu nào sau đây thích hợp nhất để biểu diễn mối quan hệ phân cấp?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Hàng đợi (Queue)
65. Độ phức tạp thời gian để truy cập một phần tử trong mảng (array) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
66. 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. Đệ quy (Recursion)
B. Tham lam (Greedy)
C. Ghi nhớ (Memoization) và Bảng phương án (Tabulation)
D. Chia để trị (Divide and Conquer)
67. Khi nào 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 dữ liệu đã được sắp xếp
B. Khi dữ liệu chưa được sắp xếp và số lượng phần tử nhỏ
C. Khi cần tìm kiếm phần tử lớn nhất
D. Khi cần tìm kiếm phần tử nhỏ nhất
68. Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search – BFS) thường sử dụng cấu trúc dữ liệu nào để lưu trữ các đỉnh cần duyệt?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
69. Cấu trúc dữ liệu Trie (còn gọi là cây tiền tố) được sử dụng hiệu quả nhất cho loại bài toán nào?
A. Sắp xếp các số nguyên
B. Tìm kiếm đường đi ngắn nhất
C. Tìm kiếm và gợi ý từ dựa trên tiền tố
D. Biểu diễn đồ thị
70. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
71. 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)
72. Trong cây nhị phân cân bằng (Balanced Binary Tree), chiều cao của cây có mối quan hệ như thế nào với số lượng nút (n)?
A. Chiều cao tỉ lệ thuận với n
B. Chiều cao tỉ lệ nghịch với n
C. Chiều cao tỉ lệ thuận với log(n)
D. Chiều cao tỉ lệ thuận với n^2
73. Độ phức tạp thời gian của thuật toán sắp xếp Heap Sort là bao nhiêu?
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(log n)
74. Trong thuật toán Prim, cấu trúc dữ liệu nào thường được sử dụng để chọn cạnh có trọng số nhỏ nhất?
A. Stack
B. Queue
C. Heap (Priority Queue)
D. Linked List
75. Phương pháp nào sau đây được sử dụng để giải quyết các xung đột (collisions) trong bảng băm (hash table)?
A. Sắp xếp (Sorting)
B. Tìm kiếm nhị phân (Binary Search)
C. Địa chỉ mở (Open Addressing) và tách chuỗi (Separate Chaining)
D. Đệ quy (Recursion)
76. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?
A. O(n^2)
B. O(log n)
C. O(n log n)
D. O(n)
77. Trong cấu trúc dữ liệu đồ thị (graph), điều gì thể hiện mối quan hệ giữa hai đỉnh?
A. Nút (Node)
B. Cạnh (Edge)
C. Đường dẫn (Path)
D. Chu trình (Cycle)
78. Điểm 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 đôi (doubly linked list) là gì?
A. Danh sách liên kết đơn có thể duyệt theo cả hai hướng, còn danh sách liên kết đôi chỉ duyệt được một hướng
B. Danh sách liên kết đôi có thể duyệt theo cả hai hướng, còn danh sách liên kết đơn chỉ duyệt được một hướng
C. Danh sách liên kết đơn sử dụng ít bộ nhớ hơn danh sách liên kết đôi
D. Danh sách liên kết đôi không hỗ trợ chèn và xóa phần tử
79. Thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS) thường được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh
B. Duyệt tất cả các đỉnh của đồ thị
C. Tìm kiếm một đỉnh cụ thể trong đồ thị
D. Kiểm tra tính liên thông của đồ thị
80. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tệ nhất là O(n^2)?
A. Merge Sort
B. Quick Sort
C. Heap Sort
D. Insertion Sort
81. Thao tác nào sau đây không phải là thao tác cơ bản trên ngăn xếp (stack)?
A. Push
B. Pop
C. Peek
D. Sort
82. Thuật toán Floyd-Warshall được sử dụng để giải quyết bài toán nào?
A. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)
B. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị
C. Tìm luồng cực đại trong mạng
D. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô
83. Khi nào thì cây quyết định (Decision Tree) được coi là một cấu trúc dữ liệu hữu ích?
A. Khi cần lưu trữ dữ liệu có thứ tự
B. Khi cần thực hiện tìm kiếm nhanh chóng
C. Khi cần biểu diễn các quy tắc và quyết định dựa trên thuộc tính của dữ liệu
D. Khi cần quản lý dữ liệu theo kiểu hàng đợi
84. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n)?
A. Sắp xếp chèn (Insertion Sort)
B. Sắp xếp nổi bọt (Bubble Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
85. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Ngăn xếp (Stack)
86. Cây khung nhỏ nhất (Minimum Spanning Tree – MST) của một đồ thị 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ác 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ác cạnh nhỏ nhất
C. Một cây chứa một phần các đỉnh của đồ thị và có tổng trọng số các cạnh nhỏ nhất
D. Một cây chứa một phần các đỉnh của đồ thị và có tổng trọng số các cạnh lớn nhất
87. Cây nhị phân tìm kiếm (Binary Search Tree – BST) có đặc điểm nào sau đây?
A. Tất cả các nút con trái đều lớn hơn nút gốc
B. Tất cả các nút con phải đều nhỏ hơn nút gốc
C. Giá trị của nút gốc luôn lớn hơn giá trị của nút con trái và nhỏ hơn giá trị của nút con phải
D. Cây luôn cân bằng
88. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán Dijkstra tìm đường đi ngắn nhất?
A. Stack
B. Queue
C. Priority Queue (Heap)
D. Linked List
89. Thuật toán nào sau đây là một ví dụ của kỹ thuật ‘chia để trị’ (divide and conquer)?
A. Sắp xếp chèn (Insertion Sort)
B. Sắp xếp nổi bọt (Bubble Sort)
C. Sắp xếp chọn (Selection Sort)
D. Sắp xếp nhanh (Quick Sort)
90. Ưu điểm chính của việc sử dụng danh sách liên kết (linked list) so với mảng (array) là gì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước đã biết trước
C. Dễ dàng chèn và xóa các phần tử
D. Tìm kiếm phần tử nhanh hơn
91. Kỹ thuật ‘chia để trị’ (divide and conquer) thường được sử dụng trong thuật toán nào sau đây?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Tìm kiếm tuyến tính (Linear Search)
C. Sắp xếp trộn (Merge Sort)
D. Duyệt theo chiều sâu (Depth-First Search)
92. 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 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)
93. Trong bảng băm (hash table), ‘xung đột’ (collision) xảy ra khi nào?
A. Khi hai khóa có cùng giá trị
B. Khi hai khóa khác nhau được băm vào cùng một ô nhớ
C. Khi bảng băm đầy
D. Khi một khóa không thể tìm thấy trong bảng băm
94. Để kiểm tra xem một biểu thức toán học có cân bằng dấu ngoặc hay không, cấu trúc dữ liệu nào là phù hợp nhất?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Đồ thị (Graph)
95. Thuật toán sắp xếp nào sau đây hoạt động dựa trên việc chia mảng thành các mảng con nhỏ hơn, sắp xếp chúng và sau đó trộn chúng lại?
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 nhanh (Quick Sort)
96. Khi nào nên sử dụng danh sách liên kết kép (doubly linked list) thay vì danh sách liên kết đơn (singly linked list)?
A. Khi cần duyệt danh sách theo cả hai chiều
B. Khi cần tiết kiệm bộ nhớ
C. Khi cần chèn phần tử vào đầu danh sách
D. Khi cần tìm kiếm phần tử nhanh chóng
97. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
98. Trong cấu trúc dữ liệu cây, nút gốc (root) là nút như thế nào?
A. Nút có bậc lớn nhất
B. Nút không có nút cha
C. Nút có ít nút con nhất
D. Nút nằm ở mức sâu nhất của cây
99. Trong thuật toán tìm kiếm theo chiều sâu (depth-first search), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ các đỉnh cần duyệt?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Mảng (Array)
D. Danh sách liên kết (Linked List)
100. Trong cấu trúc dữ liệu hàng đợi ưu tiên (priority queue), phần tử nào sẽ được lấy ra đầu tiên?
A. Phần tử được thêm vào đầu tiên
B. Phần tử được thêm vào cuối cùng
C. Phần tử có độ ưu tiên cao nhất
D. Phần tử có độ ưu tiên thấp nhất
101. Thuật toán nào sau đây có thể được sử dụng để tìm kiếm một phần tử trong một mảng đã được sắp xếp với độ phức tạp O(log n)?
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)
102. Ưu điểm của việc sử dụng cây AVL so với cây nhị phân tìm kiếm thông thường là gì?
A. Cây AVL luôn có chiều cao nhỏ hơn
B. Cây AVL tự cân bằng, đảm bảo độ phức tạp tìm kiếm O(log n)
C. Cây AVL dễ cài đặt hơn
D. Cây AVL sử dụng ít bộ nhớ hơn
103. Trong cấu trúc dữ liệu đồ thị (graph), một chu trình (cycle) là gì?
A. Một đường đi không chứa đỉnh lặp lại
B. Một đường đi bắt đầu và kết thúc tại cùng một đỉnh
C. Một đường đi đi qua tất cả các đỉnh của đồ thị
D. Một đường đi ngắn nhất giữa hai đỉnh
104. Độ 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 trung bình là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
105. Ưu điểm của việc sử dụng 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 luôn tốt hơn
B. Sử dụng ít bộ nhớ hơn
C. Dễ cài đặt hơn
D. Ổn định hơn
106. Độ phức tạp thời gian để chèn một phần tử vào đầu danh sách liên kết đơn (singly linked list) là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
107. Để tìm kiếm một chuỗi con (substring) trong một chuỗi lớn hơn, thuật toán nào sau đây thường được sử dụng?
A. Thuật toán Dijkstra
B. Thuật toán tìm kiếm nhị phân (Binary Search)
C. Thuật toán Knuth-Morris-Pratt (KMP)
D. Thuật toán sắp xếp trộn (Merge Sort)
108. 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)
109. 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 đỉnh trong một đồ thị có trọng số?
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 Dijkstra
D. Thuật toán sắp xếp chèn (Insertion Sort)
110. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp đã gần được sắp xếp?
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 nhanh (Quick Sort)
111. Trong cấu trúc dữ liệu cây, chiều cao của một nút được định nghĩa như thế nào?
A. Số lượng nút trên đường đi dài nhất từ nút đó đến một nút lá
B. Số lượng nút trên đường đi ngắn nhất từ nút đó đến nút gốc
C. Số lượng nút con của nút đó
D. Số lượng nút cha của nút đó
112. Ư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
113. Hàm băm (hash function) tốt cần đáp ứng yêu cầu nào sau đây?
A. Tính toán nhanh chóng
B. Phân phối đều các khóa vào các ô nhớ
C. Dễ dàng đảo ngược để tìm lại khóa ban đầu
D. Luôn tạo ra các giá trị băm khác nhau cho các khóa khác nhau
114. Khi nào nên sử dụng cấu trúc dữ liệu đồ thị (graph) thay vì cây (tree)?
A. Khi cần biểu diễn mối quan hệ phân cấp
B. Khi cần tìm kiếm nhanh chóng
C. Khi mối quan hệ giữa các phần tử phức tạp hơn và có thể có chu trình
D. Khi cần sắp xếp dữ liệu
115. Cây khung nhỏ nhất (minimum spanning tree) của một đồ thị là gì?
A. Một cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh nhỏ nhất
B. Một cây bao gồm tất cả các đỉnh của đồ thị và có số lượng cạnh ít nhất
C. Một cây bao gồm một phần các đỉnh của đồ thị và có tổng trọng số các cạnh nhỏ nhất
D. Một cây bao gồm một phần các đỉnh của đồ thị và có số lượng cạnh ít nhất
116. Trong cây nhị phân tìm kiếm (binary search tree), tính chất 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 tất cả các nút con trái nhỏ hơn giá trị của nút cha
D. Chiều cao của cây luôn cân bằng
117. Thuật toán sắp xếp nào sau đây có độ phức tạp 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)
118. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai một bộ nhớ cache?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Bảng băm (Hash Table)
D. Cây (Tree)
119. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ ‘cha-con’ trong một tổ chức?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Bảng băm (Hash Table)
120. Trong thuật toán duyệt đồ thị, sự khác biệt chính giữa duyệt theo chiều rộng (BFS) và duyệt theo chiều sâu (DFS) là gì?
A. BFS sử dụng hàng đợi, DFS sử dụng ngăn xếp
B. BFS tìm đường đi ngắn nhất, DFS tìm tất cả các đường đi
C. BFS luôn nhanh hơn DFS
D. BFS chỉ hoạt động trên đồ thị có hướng, DFS chỉ hoạt động trên đồ thị vô hướng
121. 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(log n)
B. O(n^2)
C. O(n log n)
D. O(n)
122. Trong cấu trúc dữ liệu cây, chiều cao của một nút được định nghĩa là gì?
A. Số lượng nút trên đường đi dài nhất từ nút đó đến một nút lá
B. Số lượng cạnh trên đường đi dài nhất từ nút đó đến một nút lá
C. Số lượng nút trên đường đi ngắn nhất từ nút đó đến nút gốc
D. Số lượng cạnh trên đường đi ngắn nhất từ nút đó đến nút gốc
123. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp xấu nhất để sắp xếp một mảng?
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 trộn (Merge Sort)
124. Trong cấu trúc dữ liệu đồ thị, ma trận kề (adjacency matrix) được sử dụng để biểu diễn mối quan hệ giữa các đỉnh. Nếu đồ thị có V đỉnh, kích thước của ma trận kề là bao nhiêu?
A. V
B. V + 1
C. V x V
D. V x E (E là số cạnh)
125. Cây nhị phân tìm kiếm (binary search tree) có đặc điểm nào sau đây?
A. Tất cả các nút con bên trái đều lớn hơn nút gốc
B. Tất cả các nút con bên phải đều nhỏ hơn nút gốc
C. Giá trị của nút gốc lớn hơn hoặc bằng giá trị của tất cả các nút con của nó
D. Tất cả các nút con bên trái đều nhỏ hơn nút gốc và tất cả các nút con bên phải đều lớn hơn nút gốc
126. Thuật toán nào sau đây được sử dụng để tìm chu trình Euler trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Floyd-Warshall
C. Thuật toán Fleury
D. Thuật toán Kruskal
127. Trong cây tìm kiếm nhị phân cân bằng (balanced binary search tree), chiều cao của cây được giới hạn bởi yếu tố nào?
A. Số lượng nút
B. Số lượng lá
C. Số lượng cạnh
D. Số lượng nút con
128. Thuật toán tìm kiếm theo chiều sâu (DFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần duyệt?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Đồ thị (Graph)
129. 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 Floyd-Warshall
C. Thuật toán Prim
D. Thuật toán tìm kiếm nhị phân
130. 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 (chuỗi đối xứng) hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Mảng (Array)
131. 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. Cây (Tree)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
132. Thuật toán nào sau đây là một ví dụ về thuật toán chia để trị (divide and conquer)?
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 trộn (Merge Sort)
133. Phương pháp nào sau đây đượ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 nhỏ hơn và giải chúng một cách tối ưu?
A. Chia để trị (Divide and Conquer)
B. Quy hoạch động (Dynamic Programming)
C. Thuật toán tham lam (Greedy Algorithm)
D. Tìm kiếm vét cạn (Brute Force)
134. Trong cây AVL, thao tác cân bằng nào được thực hiện khi một nút được chèn vào cây con bên trái của cây con bên trái của một nút?
A. Xoay trái
B. Xoay phải
C. Xoay trái phải
D. Xoay phải trái
135. Trong thuật toán sắp xếp nổi bọt (bubble sort), sau mỗi lần lặp qua mảng, điều gì xảy ra?
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. Phần tử lớn nhất được đặt vào vị trí cuối cùng
D. Mảng được sắp xếp hoàn toàn
136. Kỹ thuật lập trình nào sau đây giúp giảm độ phức tạp thời gian bằng cách lưu trữ kết quả của các bài toán con và sử dụng lại chúng khi cần thiết?
A. Đệ quy (Recursion)
B. Chia để trị (Divide and Conquer)
C. Ghi nhớ (Memoization)
D. Thuật toán tham lam (Greedy Algorithm)
137. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất trong một đồ thị có trọng số không âm?
A. Thuật toán Prim
B. Thuật toán Kruskal
C. Thuật toán Dijkstra
D. Thuật toán Ford-Fulkerson
138. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
139. Cấu trúc dữ liệu nào sau đây là một ví dụ về cấu trúc dữ liệu tuyến tính?
A. Cây (Tree)
B. Đồ thị (Graph)
C. Hàng đợi (Queue)
D. Heap
140. Độ 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 trung bình là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
141. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (quicksort) là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
142. Ư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 biết trước kích thước
C. Dễ dàng chèn và xóa các phần tử ở giữa danh sách
D. Tìm kiếm phần tử nhanh hơn
143. Hàng đợi ưu tiên (priority queue) thường được hiện thực bằng cấu trúc dữ liệu nào?
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)
144. Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (linear search) trong trường hợp xấu nhất là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
145. 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) trong thời gian O(1)?
A. Danh sách liên kết (Linked List)
B. Cây (Tree)
C. Mảng (Array)
D. Đồ thị (Graph)
146. Trong thuật toán sắp xếp vun đống (heap sort), độ phức tạp thời gian để xây dựng heap từ một mảng chưa sắp xếp là bao nhiêu?
A. O(n^2)
B. O(log n)
C. O(n)
D. O(n log n)
147. Độ phức tạp thời gian để chèn một phần tử vào đầu 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 log n)
148. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử đầu và cuối trong thời gian O(1)?
A. Mảng (Array)
B. Danh sách liên kết đơn (Singly Linked List)
C. Danh sách liên kết đôi (Doubly Linked List)
D. Hàng đợi (Queue)
149. Thuật toán tìm kiếm theo chiều rộng (BFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần duyệt?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
150. Phương pháp nào sau đây được sử dụng để xử lý các xung đột (collisions) trong bảng băm (hash table)?
A. Sắp xếp (Sorting)
B. Tìm kiếm (Searching)
C. Liên kết riêng (Separate Chaining)
D. Đệ quy (Recursion)
