150+ câu trắc nghiệm Cấu trúc dữ liệu và giải thuật chương 7

1. Heap (đống) thường được sử dụng để triển khai cấu trúc dữ liệu nào sau đây?

2. Thuật toán Kruskal được sử dụng để giải quyết vấn đề nào sau đây?

3. Cây nào sau đây đảm bảo rằng khoảng cách từ gốc đến bất kỳ nút lá nào là như nhau?

4. Ưu điểm chính của cây tìm kiếm nhị phân (binary search tree) so với mảng là gì?

5. Độ 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?

6. Khi nào thì việc sử dụng bảng băm (hash table) không phù hợp?

7. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử đầu và cuối với độ phức tạp thời gian O(1)?

8. 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 sẽ được duyệt?

9. 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ì?

10. Thuật toán Prim được sử dụng để giải quyết vấn đề nào sau đây?

11. Độ phức tạp thời gian trung bình của thuật toán quicksort là bao nhiêu?

12. Cấu trúc dữ liệu nào sau đây là phù hợp nhất để biểu diễn mối quan hệ ‘cha-con’ trong một tổ chức?

13. Trong cây tìm kiếm nhị phân, thứ tự duyệt nào sau đây sẽ cho ra các nút theo thứ tự tăng dần?

14. Khi nào thì nên sử dụng danh sách liên kết thay vì mảng?

15. Ưu điểm chính của 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ì?

16. Cấu trúc dữ liệu nào sau đây tuân theo nguyên tắc LIFO (Last In, First Out)?

17. Khi nào thì nên sử dụng thuật toán sắp xếp trộn (merge sort) thay vì quicksort?

18. Cây nào sau đây đả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 trong trường hợp xấu nhất?

19. Thuật toán Dijkstra được sử dụng để giải quyết vấn đề nào sau đây?

20. Phương pháp nào sau đây được sử dụng để chuyển đổi một khóa thành một chỉ số trong bảng băm?

21. Trong thuật toán sắp xếp trộn (merge sort), giai đoạn nào chiếm phần lớn thời gian thực hiện?

22. Trong thuật toán tìm kiếm theo chiều rộng (breadth-first search), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ các đỉnh sẽ được duyệt?

23. Trong cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree), thao tác nào sau đây được sử dụng để duy trì tính cân bằng sau khi chèn hoặc xóa một nút?

24. Trong cây, nút nào không có nút con được gọi là gì?

25. 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(h), với h là chiều cao của cây?

26. Độ phức tạp thời gian của thao tác tìm kiếm trong danh sách liên kết đơn (singly linked list) là bao nhiêu trong trường hợp xấu nhất?

27. Trong thuật toán sắp xếp, thuật toán nào có độ phức tạp thời gian trung bình tốt nhất nhưng lại có độ phức tạp thời gian xấu nhất là O(n^2)?

28. 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)?

29. Trong bảng băm, điều gì xảy ra khi có hai khóa khác nhau băm đến cùng một vị trí?

30. Độ 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) sử dụng phương pháp xích (chaining) là bao nhiêu, giả sử hàm băm phân phối đều?

31. Để biểu diễn mối quan hệ bạn bè trong một mạng xã hội, loại đồ thị nào phù hợp nhất?

32. Điều kiện cần và đủ để một đồ thị có chu trình Euler là gì?

33. Bài toán ‘luồng cực đại’ (max flow) và ‘lát cắt nhỏ nhất’ (min cut) có mối quan hệ như thế nào?

34. Trong chương 7 về cấu trúc dữ liệu và giải thuật, thuật ngữ ‘đồ thị’ (graph) thường được dùng để biểu diễn điều gì?

35. Khi nào thì thuật toán Bellman-Ford được ưu tiên hơn thuật toán Dijkstra?

36. Cho một đồ thị vô hướng liên thông có 5 đỉnh. Số cạnh tối thiểu để đồ thị đó liên thông là bao nhiêu?

37. Trong thuật toán Ford-Fulkerson, mục tiêu chính là gì?

38. Độ phức tạp thời gian của thuật toán Floyd-Warshall là bao nhiêu, với V là số đỉnh?

39. Điều gì xảy ra nếu bạn chạy thuật toán Dijkstra trên một đồ thị có cạnh trọng số âm?

40. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng (BFS) trên một đồ thị được biểu diễn bằng danh sách kề là bao nhiêu, với V là số đỉnh và E là số cạnh?

41. Khi nào nên sử dụng biểu diễn đồ thị bằng danh sách kề thay vì ma trận kề?

42. Ứng dụng nào sau đây sử dụng đồ thị có hướng không chu trình (DAG)?

43. Nếu bạn cần tìm tất cả các đường đi ngắn nhất giữa mọi cặp đỉnh trong một đồ thị, thuật toán nào sẽ phù hợp nhất?

44. Trong lý thuyết đồ thị, một ‘đồ thị hai phía’ (bipartite graph) là gì?

45. Trong biểu diễn đồ thị bằng ma trận kề, giá trị tại vị trí (i, j) của ma trận biểu thị điều gì?

46. Trong một đồ thị có trọng số âm, thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình âm?

47. Thuật toán Prim và Kruskal được sử dụng để giải quyết bài toán nào trên đồ thị?

48. Thuật toán tìm kiếm theo chiều sâu (DFS) thường được triển khai bằng cấu trúc dữ liệu nào?

49. 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?

50. Cho một đồ thị có hướng, thuật toán nào sau đây có thể được sử dụng để tìm các thành phần liên thông mạnh (strongly connected components)?

51. Ứng dụng nào sau đây KHÔNG phải là ứng dụng phổ biến của thuật toán đồ thị?

52. Đồ thị nào sau đây KHÔNG thể có chu trình Hamilton?

53. Trong một đồ thị vô hướng liên thông, một ‘cây bao trùm’ (spanning tree) là gì?

54. Sắp xếp topo (topological sort) là gì và nó chỉ áp dụng cho loại đồ thị nào?

55. Trong một mạng luồng, ‘đường tăng luồng’ (augmenting path) là gì?

56. Trong thuật toán Kruskal, cấu trúc dữ liệu nào thường đượ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?

57. Độ phức tạp không gian của biểu diễn đồ thị bằng ma trận kề là bao nhiêu, với V là số đỉnh?

58. Điểm khác biệt chính giữa thuật toán BFS và DFS là gì?

59. 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ố dương?

60. Chu trình Euler trong một đồ thị là gì?

61. 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)?

62. Trong cấu trúc dữ liệu cây, mức (level) của một nút được định nghĩa như thế nào?

63. 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 giúp duy trì tính cân bằng của cây?

64. 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?

65. 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 sâu (Depth-First Search)?

66. Trong cây, đỉnh nào không có đỉnh cha được gọi là gì?

67. Độ phức tạp thời gian của thao tác xóa một phần tử khỏi hàng đợi ưu tiên (priority queue) được triển khai bằng heap là bao nhiêu?

68. 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?

69. Ư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 nhị phân là gì?

70. Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình trong một đồ thị có hướng?

71. Thuật toán nào sau đây được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị?

72. 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?

73. Thuật toán 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?

74. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong một mảng đã được sắp xếp?

75. Thuật toán nào sau đây thường được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị?

76. Thuật toán nào sau đây là một ví dụ về thuật toán chia để trị (divide and conquer)?

77. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu?

78. Trong cấu trúc dữ liệu đồ thị, danh sách kề (adjacency list) được sử dụng để biểu diễn điều gì?

79. Trong cây tìm kiếm nhị phân, duyệt theo thứ tự giữa (inorder traversal) có nghĩa là gì?

80. 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 xấu nhất là O(n)?

81. Ư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ì?

82. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?

83. Trong cây tìm kiếm nhị phân, thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n), với n là số lượng nút?

84. 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?

85. Độ 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à bao nhiêu?

86. 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ì?

87. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?

88. Trong đồ thị, 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?

89. Cấu trúc dữ liệu nào sau đây cho phép truy cập các phần tử theo thứ tự FIFO (First In, First Out)?

90. Độ phức tạp thời gian của thao tác chèn (insertion) trong danh sách liên kết đơn (singly linked list) ở đầu danh sách là bao nhiêu?

91. 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ử?

92. Trong chương 7 về cấu trúc dữ liệu và giải thuật, phương pháp nào thường được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất trong một đồ thị có trọng số không âm?

93. Độ 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?

94. Thuật toán nào sau đây thường được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree) trong một đồ thị?

95. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là bao nhiêu?

96. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong một mảng đã được sắp xếp?

97. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?

98. 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 là O(log n) trong trường hợp tốt nhất và trung bình?

99. Cấu trúc dữ liệu nào sau đây phù 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?

100. Trong đồ thị, một đường đi Euler là gì?

101. 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ố?

102. Thuật toán nào sau đây có thể phát hiện chu trình âm trong một đồ thị có trọng số?

103. Độ phức tạp thời gian của thao tác chèn (insertion) vào một danh sách liên kết đơn (singly linked list) ở đầu danh sách là bao nhiêu?

104. 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 (BFS)?

105. 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)?

106. Độ phức tạp không gian của thuật toán Merge Sort là bao nhiêu?

107. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai bảng băm (hash table)?

108. Trong đồ thị, một chu trình (cycle) là gì?

109. Độ phức tạp thời gian của thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị là bao nhiêu?

110. Thuật toán nào sau đây là một ví dụ của kỹ thuật ‘chia để trị’ (divide and conquer)?

111. Trong cây, một cây nhị phân hoàn chỉnh (complete binary tree) là gì?

112. 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 sâu (DFS)?

113. Trong cấu trúc dữ liệu cây, nút nào không có nút con được gọi là gì?

114. Thuật toán nào sau đây là một thuật toán tham lam (greedy algorithm)?

115. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán LFU (Least Frequently Used) trong bộ nhớ cache?

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à bao nhiêu, giả sử hàm băm phân phối đều?

117. Trong cấu trúc dữ liệu đồ thị, một đỉnh được gọi là ‘cô lập’ nếu nó có đặc điểm gì?

118. Trong thuật toán sắp xếp, thuật toán nào có độ phức tạp thời gian luôn là O(n log n) bất kể dữ liệu đầu vào?

119. Trong cây nhị phân tìm kiếm, thao tác nào sau đây có độ phức tạp thời gian là O(n) trong trường hợp xấu nhất?

120. Độ phức tạp thời gian tốt nhất của thuật toán Insertion Sort là gì?

121. Cấu trúc dữ liệu nào sau đây tuân theo nguyên tắc LIFO (Last In First Out)?

122. 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?

123. Thuật toán 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?

124. 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?

125. Trong cây tìm kiếm nhị phân, thao tác nào sau đây có độ phức tạp thời gian là O(n) trong trường hợp xấu nhất, trong đó n là số lượng nút trong cây?

126. Độ phức tạp thời gian của thao tác tìm kiếm trong một danh sách liên kết đơn (singly linked list) trong trường hợp xấu nhất là bao nhiêu?

127. Trong bảng băm, điều gì xảy ra khi hai khóa khác nhau băm đến cùng một vị trí?

128. Trong cây tìm kiếm nhị phân, thao tác nào sau đây đòi hỏi phải duyệt qua toàn bộ cây trong trường hợp xấu nhất?

129. Thuật toán sắp xếp nào sau đây hoạt động bằng cách liên tục tìm phần tử nhỏ nhất từ phần chưa được sắp xếp và đặt nó vào đầu phần đã được sắp xếp?

130. Trong cây tìm kiếm nhị phân, thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n)?

131. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu?

132. 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 trong cây?

133. Trong thuật toán Dijkstra để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm, cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ khoảng cách ước tính từ đỉnh nguồn đến mỗi đỉnh?

134. Trong thuật toán tô màu đồ thị (graph coloring), mục tiêu là gì?

135. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một biểu thức toán học có chứa các dấu ngoặc hợp lệ hay không?

136. 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 – BFS)?

137. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất là O(n)?

138. Trong thuật toán Kruskal để tìm cây khung nhỏ nhất (minimum spanning tree), tiêu chí nào sau đây được sử dụng để chọn cạnh tiếp theo để thêm vào cây khung?

139. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n) và thường được sử dụng trong thực tế?

140. Độ phức tạp thời gian của thao tác chèn vào một bảng băm (hash table) trong trường hợp trung bình là bao nhiêu?

141. Phương pháp nào sau đây thường được sử dụng để biểu diễn các mối quan hệ ‘nhiều-nhiều’ trong cơ sở dữ liệu?

142. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai chức năng hoàn tác (undo) trong các ứng dụng phần mềm?

143. Kỹ thuật nào sau đây được sử dụng để giảm thiểu số lượng truy cập đĩa trong các ứng dụng cơ sở dữ liệu?

144. Trong thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị, độ phức tạp thời gian là bao nhiêu?

145. Trong kỹ thuật lập trình động, phương pháp nào sau đây được sử dụng để lưu trữ kết quả của các bài toán con để tránh tính toán lại chúng?

146. Trong thuật toán Prim để tìm cây khung nhỏ nhất (minimum spanning tree) của một đồ thị, cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ các cạnh có thể thêm vào cây khung?

147. Cấu trúc dữ liệu nào sau đây cho phép chèn và xóa phần tử ở cả hai đầu một cách hiệu quả?

148. 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)?

149. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất là O(n log n) trong trường hợp xấu nhất?

150. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong một mảng đã được sắp xếp?