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

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

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

3. Trong cấu trúc dữ liệu đồ thị, điều gì phân biệt giữa đồ thị có hướng (directed graph) và đồ thị vô hướng (undirected graph)?

4. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai một hàng đợi ưu tiên (priority queue)?

5. Cấu trúc dữ liệu nào sau đây sử dụng con trỏ (pointer) để liên kết các phần tử?

6. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai một hệ thống quản lý bộ nhớ?

7. Ưu điểm chính của việc sử dụng hàng đợi (queue) trong lập trình là gì?

8. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (binary search tree), đặc điểm nào sau đây là đúng?

9. Khi nào nên sử dụng thuật toán tìm kiếm nhị phân (binary search)?

10. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để tìm tất cả các thành phần liên thông (connected components)?

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

12. Trong cấu trúc dữ liệu ngăn xếp (stack), thao tác nào dùng để loại bỏ một phần tử khỏi đỉnh ngăn xếp?

13. Độ phức tạp thời gian để truy cập một phần tử trong mảng (array) là bao nhiêu?

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

15. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp (hierarchical relationship)?

16. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh?

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

18. Trong cấu trúc dữ liệu ngăn xếp (stack), thao tác nào cho phép xem phần tử ở đỉnh ngăn xếp mà không loại bỏ nó?

19. Thuật toán sắp xếp nào sau đây hoạt động bằng cách chia danh sách thành các danh sách con nhỏ hơn, sắp xếp chúng, và sau đó hợp nhất chúng lại?

20. Trong cấu trúc dữ liệu đồ thị (graph), một chu trình (cycle) là gì?

21. Độ phức tạp thời gian tốt nhất của thuật toán Bubble Sort là bao nhiêu?

22. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai bộ nhớ cache?

23. Độ phức tạp thời gian tốt nhất của thuật toán Insertion Sort là bao nhiêu?

24. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong một mảng chưa được sắp xếp là bao nhiêu?

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

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

27. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree)?

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

29. Khi nào nên sử dụng thuật toán Quick Sort thay vì Merge Sort?

30. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán Huffman coding?

31. Ưu điểm 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 (binary search tree) là gì?

32. Khi nào nên sử dụng cấu trúc dữ liệu bảng băm (hash table)?

33. Trong cấu trúc dữ liệu đồ thị (graph), một chu trình (cycle) là gì?

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

35. Ứng dụng thực tế của cấu trúc dữ liệu ngăn xếp (stack) trong trình biên dịch là gì?

36. Trong cấu trúc dữ liệu hàng đợi (queue), thao tác nào loại bỏ một phần tử khỏi đầu hàng đợi?

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

38. Khi nào nên sử dụng thuật toán sắp xếp chèn (insertion sort)?

39. Cấu trúc dữ liệu nào 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?

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

41. Cấu trúc dữ liệu nào 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)?

42. Trong cấu trúc dữ liệu đồ thị, một cây bao trùm tối thiểu (minimum spanning tree) là gì?

43. Trong cấu trúc dữ liệu cây tìm kiếm nhị phân, thao tác nào dùng để duy trì tính chất của cây sau khi chèn hoặc xóa một nút?

44. Trong cấu trúc dữ liệu đồ thị, một đồ thị vô hướng (undirected graph) khác với đồ thị có hướng (directed graph) như thế nào?

45. Cấu trúc dữ liệu nào thường được sử dụng để triển khai bộ nhớ cache?

46. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (depth-first search)?

47. Thuật toán sắp xếp nào có độ phức tạp thời gian xấu nhất là O(n^2)?

48. Trong cấu trúc dữ liệu cây, một nút lá (leaf node) là gì?

49. Trong cấu trúc dữ liệu cây, chiều cao của cây là gì?

50. Cấu trúc dữ liệu nào phù hợp để biểu diễn mối quan hệ cha-con trong một gia đình?

51. Trong thuật toán sắp xếp trộn (merge sort), giai đoạn nào thực hiện việc kết hợp hai mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp?

52. Khi nào nên sử dụng danh sách liên kết đôi (doubly linked list) thay vì danh sách liên kết đơn (singly linked list)?

53. Trong cấu trúc dữ liệu đồ thị, thuật toán Dijkstra được sử dụng để làm gì?

54. Thuật toán sắp xếp nào hoạt động bằng cách liên tục hoán đổi các cặp phần tử liền kề nếu chúng không đúng thứ tự?

55. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong một cây tìm kiếm nhị phân (binary search tree) cân bằng là bao nhiêu?

56. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân (binary search) là bao nhiêu?

57. Trong cấu trúc dữ liệu ngăn xếp (stack), thao tác nào thêm một phần tử vào đỉnh ngăn xếp?

58. Trong cấu trúc dữ liệu cây (tree), nút gốc (root) là gì?

59. Ứng dụng thực tế của cấu trúc dữ liệu hàng đợi (queue) trong hệ thống máy tính là gì?

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

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

62. Thuật toán nào sau đây 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 trong một đồ thị có trọng số không âm?

63. Trong cây đỏ-đen (red-black tree), mỗi nút được gán một màu là đỏ hoặc đen, quy tắc nào sau đây luôn được tuân thủ?

64. Khi nào nên sử dụng danh sách liên kết vòng (circular linked list)?

65. Trong cấu trúc dữ liệu hàng đợi (queue), thao tác nào loại bỏ một phần tử khỏi đầu hàng đợi?

66. Ứng dụng nào sau đây phù hợp nhất với cấu trúc dữ liệu đồ thị (graph)?

67. Trong một cây nhị phân tìm kiếm (binary search tree), thuộc tính nào sau đây luôn đúng?

68. Thứ tự duyệt cây nào sau đây thăm nút gốc trước?

69. Trong một cây AVL, yếu tố cân bằng (balance factor) của một nút là gì?

70. Nhược đ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ì?

71. Sự khác biệt chính giữa thuật toán Prim và thuật toán Kruskal là gì?

72. Trong cấu trúc dữ liệu Heap, phần tử nào luôn nằm ở gốc?

73. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi ký tự có phải là palindrome hay không?

74. Độ phức tạp thời gian tốt nhất để 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 (binary search) là gì?

75. 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 (Depth-First Search)?

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

77. Khi nào nên sử dụng bảng băm (hash table) thay vì mảng (array)?

78. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc FIFO (First In, First Out)?

79. Tại sao cần cây cân bằng (balanced tree) như cây AVL hoặc cây đỏ-đen (red-black tree)?

80. Trong cấu trúc dữ liệu ngăn xếp (stack), thao tác nào thêm một phần tử vào đỉnh ngăn xếp?

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

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

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

84. Thứ tự duyệt cây nào sau đây thăm nút gốc sau cùng?

85. Trong danh sách liên kết kép (doubly linked list), mỗi nút chứa bao nhiêu con trỏ?

86. Thuật toán nào sau đây tìm cây khung nhỏ nhất (minimum spanning tree) trong một đồ thị?

87. Điều gì xảy ra khi có sự xung đột (collision) trong bảng băm (hash table)?

88. Để biểu diễn một hàng đợi (queue) bằng một mảng, điều gì xảy ra khi đạt đến cuối mảng?

89. Độ phức tạp thời gian trung bình của thuật toán tìm kiếm tuyến tính (linear search) trong một mảng chưa được sắp xếp là gì?

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

91. Cho một biểu thức hậu tố (postfix) ‘2 3 + 5 *’. Giá trị của biểu thức này là bao nhiêu?

92. Khi nào nên sử dụng hàng đợi hai đầu (deque) thay vì hàng đợi thông thường?

93. Độ phức tạp thời gian trung bình để thêm một phần tử vào hàng đợi (queue) sử dụng mảng vòng (circular array) là bao nhiêu?

94. Ưu điểm chính của việc sử dụng hàng đợi (queue) so với mảng (array) trong một số ứng dụng là gì?

95. Trong cấu trúc dữ liệu ngăn xếp (stack), thao tác nào sau đây không được phép?

96. Trong việc lập lịch CPU, thuật toán nào sau đây có thể được mô phỏng bằng hàng đợi (queue)?

97. Ưu điểm của việc sử dụng danh sách liên kết (linked list) để cài đặt hàng đợi (queue) so với mảng (array) là gì?

98. Cho một ngăn xếp (stack) đã đầy. Thao tác nào sau đây sẽ gây ra lỗi tràn ngăn xếp (stack overflow)?

99. Trong thuật toán duyệt đồ thị theo chiều rộng (BFS), cấu trúc dữ liệu nào sau đây được sử dụng?

100. Cho một hàng đợi (queue) chứa các số [1, 2, 3] (1 là phần tử đầu hàng). Sau khi thực hiện một thao tác dequeue và thêm số 4 vào hàng đợi, hàng đợi sẽ chứa những phần tử nào (từ đầu đến cuối)?

101. Trong việc quản lý bộ nhớ, kỹ thuật nào sau đây sử dụng hàng đợi (queue) để xử lý các yêu cầu cấp phát bộ nhớ?

102. Khi nào nên sử dụng ngăn xếp (stack) thay vì hàng đợi (queue)?

103. Ứng dụng nào sau đây phù hợp nhất với cấu trúc dữ liệu hàng đợi (queue)?

104. Trong bài toán ‘Tháp Hà Nội’, cấu trúc dữ liệu nào được sử dụng một cách hiệu quả để mô phỏng các cột?

105. Khi nào nên sử dụng hàng đợi vòng (circular queue) thay vì hàng đợi tuyến tính (linear queue)?

106. Thuật toán nào sau đây thường được sử dụng để chuyển đổi một biểu thức trung tố (infix) thành biểu thức hậu tố (postfix)?

107. Trong một hàng đợi ưu tiên (priority queue) được cài đặt bằng heap, thao tác nào sau đây có độ phức tạp thời gian tốt nhất để tìm phần tử có độ ưu tiên cao nhất?

108. Ứng dụng nào sau đây không phù hợp với cấu trúc dữ liệu ngăn xếp (stack)?

109. Đâu là nhược điểm chính của việc sử dụng mảng (array) để cài đặt ngăn xếp (stack) so với danh sách liên kết (linked list)?

110. Cho một biểu thức trung tố (infix): `(2 + 3) * 4`. Biểu thức hậu tố (postfix) tương ứng là gì?

111. Trong một hệ thống phục vụ nhiều yêu cầu đồng thời, cấu trúc dữ liệu nào được sử dụng để đảm bảo các yêu cầu được xử lý theo thứ tự đến?

112. Trong cài đặt hàng đợi (queue) bằng mảng vòng (circular array), điều gì xảy ra khi `rear` vượt quá kích thước của mảng?

113. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi ký tự có phải là palindrome (đọc xuôi ngược như nhau) hay không?

114. Cho một ngăn xếp (stack) chứa các số nguyên [1, 2, 3, 4, 5] (5 là phần tử trên cùng). Sau khi thực hiện hai thao tác pop, ngăn xếp sẽ chứa những phần tử nào (từ đáy lên)?

115. Đâu là ứng dụng thực tế của hàng đợi ưu tiên (priority queue)?

116. Một hệ thống quản lý tác vụ sử dụng hàng đợi ưu tiên (priority queue) để xác định thứ tự thực hiện các tác vụ. Tác vụ nào sẽ được thực hiện tiếp theo?

117. Trong một ứng dụng quản lý bộ nhớ, kỹ thuật nào sử dụng ngăn xếp để theo dõi các khối bộ nhớ đã được giải phóng?

118. Trong một hệ thống quản lý bộ nhớ sử dụng kỹ thuật phân trang (paging), cấu trúc dữ liệu nào có thể được sử dụng để theo dõi các trang đã được sử dụng gần đây nhất?

119. Trong thuật toán tìm kiếm theo chiều sâu (DFS) của đồ thị, cấu trúc dữ liệu nào thường được sử dụng?

120. Trong việc xử lý прерывания (interrupts) trong hệ điều hành, cấu trúc dữ liệu nào thường được sử dụng để quản lý các прерывания chờ xử lý?

121. 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) trong trường hợp tốt nhất?

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

123. Khi nào nên sử dụng thuật toán sắp xếp đếm (Counting Sort)?

124. Khi nào nên sử dụng thuật toán sắp xếp chèn (Insertion Sort) thay vì các thuật toán sắp xếp phức tạp hơn như Merge Sort hoặc Quick Sort?

125. 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 trung bình là O(log n)?

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

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

128. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị?

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

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

131. Trong thuật toán tìm kiếm theo chiều rộng (Breadth-First Search – BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các nút cần được thăm?

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

133. Thuật toán sắp xếp nào sau đây là ổn định (stable)?

134. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai bộ nhớ cache?

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

136. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi ký tự có phải là palindrome hay không?

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

138. 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) và làm lại (redo) trong một trình soạn thảo văn bản?

139. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp, chẳng hạn như cấu trúc thư mục trong hệ điều hành?

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

141. Cây nào sau đây đảm bảo rằng độ cao của cây luôn được giữ ở mức tối thiểu, giúp cho các thao tác tìm kiếm, chèn và xóa có độ phức tạp O(log n)?

142. Trong thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các nút cần được thăm?

143. Độ phức tạp thời gian của thao tác xóa một phần tử khỏi cuối một danh sách liên kết đơn (Singly Linked List) là bao nhiêu?

144. Độ phức tạp thời gian của thao tác tìm kiếm 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?

145. Ưu điểm chính của việc sử dụng bảng băm (Hash Table) là gì?

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

147. Trong bảng băm (Hash Table), hiện tượng gì xảy ra khi hai khóa khác nhau được băm (hash) vào cùng một vị trí?

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

149. Thuật toán sắp xếp nào sau đây hoạt động bằng cách chia mảng thành các mảng con nhỏ hơn, sắp xếp chúng riêng lẻ, sau đó hợp nhất lại?

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