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

Các bộ trắc nghiệm theo chương:

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

Ngày cập nhật: 01/03/2026

Lưu ý và Miễn trừ trách nhiệm:Các câu hỏi và đáp án trong các bộ trắc nghiệm này được biên soạn nhằm phục vụ mục đích tham khảo và ôn luyện kiến thức. Chúng không đại diện cho bất kỳ tài liệu, đề thi chính thức hay đề thi chứng chỉ nào từ các tổ chức giáo dục hoặc cơ quan cấp chứng chỉ chuyên môn. Admin không chịu trách nhiệm về tính chính xác tuyệt đối của nội dung hoặc bất kỳ quyết định nào của bạn được đưa ra dựa trên kết quả của các bài trắc nghiệm.

Xin chào bạn! Rất vui được gặp bạn tại bộ 150+ câu trắc nghiệm Cấu trúc dữ liệu và giải thuật chương 4. Bạn sẽ tìm thấy nhiều nội dung trắc nghiệm thú vị để thử sức. Mời bạn chọn một trong các bộ câu hỏi bên dưới để tiến hành làm bài. Chúc bạn ôn tập hiệu quả và có những trải nghiệm học tập bổ ích!

★★★★★

4.7/5 (187 đánh giá)

1. Trong thuật toán sắp xếp trộn (Merge Sort), kỹ thuật nào được sử dụng?

A. Chia để trị (Divide and Conquer)

B. Tham lam (Greedy)

C. Quy hoạch động (Dynamic Programming)

D. Nhánh cận (Branch and Bound)

2. Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép hoán đổi (swap) tối đa cần thực hiện để sắp xếp một mảng có n phần tử là bao nhiêu?

A. n

B. n log n

C. n^2

D. n-1

3. Cấu trúc dữ liệu nào sau đây được sử dụng để cài đặt thuật toán tìm kiếm theo chiều sâu (Depth-First Search)?

A. Hàng đợi

B. Ngăn xếp

C. Mảng

D. Danh sách liên kết

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

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Danh sách liên kết (Linked List)

D. Cây (Tree)

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

A. Truy cập phần tử với độ phức tạp thời gian O(1) trung bình

B. Duyệt các phần tử theo thứ tự đã được sắp xếp

C. Cài đặt đơn giản và dễ hiểu

D. Sử dụng ít bộ nhớ hơn so với các cấu trúc dữ liệu khác

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

A. Linear Search

B. Binary Search

C. Bubble Sort

D. Insertion Sort

7. Trong thuật toán Dijkstra, mục đích chính là gì?

A. Tìm đường đi ngắn nhất giữa hai nút trên đồ thị có trọng số

B. Tìm cây khung nhỏ nhất của đồ thị

C. Sắp xếp các nút của đồ thị theo thứ tự topological

D. Tìm tất cả các thành phần liên thông của đồ thị

8. Trong thuật toán Bubble Sort, số lượng phép so sánh tối đa cần thực hiện để sắp xếp một mảng có n phần tử là bao nhiêu?

A. n

B. n log n

C. n^2

D. n(n-1)/2

9. Thuật toán nào sau đây sử dụng kỹ thuật quay lui (backtracking)?

A. Dijkstra’s Algorithm

B. Merge Sort

C. Quick Sort

D. N-Queens Problem

10. Trong đồ thị, một thành phần liên thông (connected component) là gì?

A. Một tập hợp các đỉnh không có cạnh nối giữa chúng

B. Một tập hợp các đỉnh mà có đường đi giữa bất kỳ hai đỉnh nào trong tập hợp

C. Một đường đi ngắn nhất giữa hai đỉnh

D. Một chu trình đi qua tất cả các đỉnh

11. Thuật toán nào sau đây thường được sử dụng để duyệt đồ thị theo chiều rộng?

A. Depth-First Search (DFS)

B. Breadth-First Search (BFS)

C. Dijkstra’s Algorithm

D. Prim’s Algorithm

12. Cấu trúc dữ liệu nào sau đây phù hợp nhất để cài đặt hàng đợi ưu tiên?

A. Mảng

B. Danh sách liên kết

C. Cây nhị phân tìm kiếm

D. Heap

13. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất là O(1) để tìm phần tử nhỏ nhất trong một cấu trúc dữ liệu?

A. Linear Search

B. Binary Search

C. Heap (min-heap)

D. Mảng đã sắp xếp

14. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn quan hệ ‘nhiều-nhiều’ trong cơ sở dữ liệu?

A. Mảng

B. Danh sách liên kết

C. Bảng băm

D. Đồ thị

15. 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 với độ phức tạp O(1)?

A. Mảng

B. Danh sách liên kết đơn

C. Danh sách liên kết đôi

D. Hàng đợi

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

A. Mảng

B. Danh sách liên kết

C. Cây

D. Bảng băm

17. Trong đồ thị, một chu trình Euler là gì?

A. Một đường đi qua tất cả các đỉnh của đồ thị đúng một lần

B. Một đường đ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 dài nhất trong đồ thị

18. Trong thuật toán Quick Sort, phần tử nào được sử dụng để phân chia mảng thành hai phần?

A. Phần tử đầu tiên

B. Phần tử cuối cùng

C. Phần tử giữa

D. Pivot

19. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) là gì?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

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

A. Duyệt cây theo thứ tự trước

B. Duyệt cây theo thứ tự sau

C. Tìm kiếm một nút

D. Tìm nút có giá trị lớn nhất

21. 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) của một đồ thị?

A. Dijkstra’s Algorithm

B. Breadth-First Search (BFS)

C. Prim’s Algorithm

D. Depth-First Search (DFS)

22. Trong cây quyết định (Decision Tree), mục đích của việc tỉa cây (pruning) là gì?

A. Tăng độ chính xác trên tập huấn luyện

B. Giảm độ phức tạp và tránh overfitting

C. Tăng số lượng nút lá

D. Tăng chiều cao của cây

23. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên (random access) đến các phần tử?

A. Mảng

B. Hàng đợi

C. Ngăn xếp

D. Danh sách liên kết

24. Cấu trúc dữ liệu nào sau đây thường được sử dụng để kiểm tra xem một biểu thức ngoặc có hợp lệ hay không?

A. Hàng đợi

B. Ngăn xếp

C. Mảng

D. Danh sách liên kết

25. Độ 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à gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

26. Trong cây nhị phân, chiều cao của cây được định nghĩa là gì?

A. Số lượng nút trên đường đi dài nhất từ gốc đến một nút lá

B. Số lượng cạnh trên đường đi dài nhất từ gốc đến một nút lá

C. Số lượng nút trong cây

D. Số lượng lá trong cây

27. Độ phức tạp thời gian của thao tác chèn một phần tử vào đầu danh sách liên kết đơn là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

28. Trong cây nhị phân tìm kiếm, thao tác nào sau đây luôn có độ phức tạp thời gian là O(h), với h là chiều cao của cây?

A. Duyệt cây theo thứ tự trước

B. Duyệt cây theo thứ tự sau

C. Tìm kiếm một nút

D. Tìm nút có giá trị lớn nhất

29. Thuật toán nào sau đây có độ phức tạp thời gian trung bình là O(n log n) để sắp xếp?

A. Bubble Sort

B. Insertion Sort

C. Quick Sort

D. Selection Sort

30. Cấu trúc dữ liệu nào sau đây thường được sử dụng để quản lý các tiến trình trong hệ điều hành?

A. Hàng đợi

B. Ngăn xếp

C. Mảng

D. Danh sách liên kết

31. Trong cây, thao tác duyệt theo chiều rộng (breadth-first traversal) còn được gọi là gì?

A. Duyệt theo thứ tự trước

B. Duyệt theo thứ tự sau

C. Duyệt theo thứ tự giữa

D. Duyệt theo mức

32. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong cây nhị phân tìm kiếm cân bằng là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

33. Trong cây nhị phân tìm kiếm, thao tác nào sau đây có độ phức tạp trung bình là O(log n), với n là số lượng nút trong 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 có giá trị cụ thể

D. Tìm nút có giá trị lớn nhất

34. Trong cây, nút nào sau đây là nút gốc?

A. Nút không có nút cha

B. Nút không có nút con

C. Nút có nhiều nút con nhất

D. Nút có chiều cao lớn nhất

35. Cây nào sau đây thường được sử dụng để biểu diễn cấu trúc thư mục trong hệ điều hành?

A. Cây nhị phân tìm kiếm

B. Cây B

C. Cây Trie

D. Cây tổng quát

36. Cây nào sau đây được sử dụng để lưu trữ dữ liệu theo thứ tự từ điển?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây Trie

D. Cây B

37. Thao tác nào sau đây không được hỗ trợ trực tiếp bởi cấu trúc dữ liệu cây?

A. Tìm kiếm

B. Chèn

C. Xóa

D. Sắp xếp

38. Cây nào sau đây đảm bảo thời gian tìm kiếm, chèn và xóa là O(log n) trong trường hợp xấu nhất, với n là số lượng nút?

A. Cây nhị phân tìm kiếm không cân bằng

B. Cây AVL

C. Cây B

D. Cây tìm kiếm Ternary

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

A. Cây nhị phân hoàn chỉnh

B. Cây nhị phân đầy đủ

C. Cây AVL

D. Cây đỏ đen

40. Cấu trúc dữ liệu cây nào sau đây thường được sử dụng trong các ứng dụng tìm kiếm văn bản, chẳng hạn như tìm kiếm từ khóa trong một tài liệu lớn?

A. Cây AVL

B. Cây B

C. Cây Trie

D. Cây đỏ đen

41. 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ệ gia phả?

A. Mảng

B. Danh sách liên kết

C. Cây

D. Đồ thị

42. Trong cây nhị phân, một cây nhị phân đầy đủ có chiều cao h thì có bao nhiêu nút?

A. 2^(h+1) – 1

B. 2^h – 1

C. h+1

D. h

43. Thứ tự duyệt cây nào sau đây in ra các nút theo thứ tự tăng dần trong cây nhị phân tìm kiếm?

A. Preorder

B. Postorder

C. Inorder

D. Level order

44. Cây nào sau đây đảm bảo rằng chiều cao của cây luôn là O(log n), bất kể thứ tự chèn các nút?

A. Cây nhị phân tìm kiếm

B. Cây B

C. Cây AVL

D. Cây tổng quát

45. Trong cây B, bậc của cây (order) thường được định nghĩa là gì?

A. Số lượng tối đa các nút con mà một nút có thể có

B. Số lượng tối thiểu các nút con mà một nút có thể có

C. Chiều cao của cây

D. Số lượng nút trong cây

46. Độ phức tạp không gian của cây nhị phân tìm kiếm là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

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

A. Tìm kiếm một nút

B. Tìm nút nhỏ nhất

C. Tìm nút lớn nhất

D. Duyệt cây theo thứ tự inorder

48. Trong cây, nút nào sau đây không có nút con?

A. Nút gốc

B. Nút lá

C. Nút trung gian

D. Nút cha

49. Loại cây nào sau đây được sử dụng để lưu trữ dữ liệu trên đĩa để truy cập hiệu quả?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây B

D. Cây đỏ đen

50. Cây nào sau đây tự cân bằng bằng cách xoay các nút?

A. Cây nhị phân tìm kiếm

B. Cây B

C. Cây Trie

D. Cây AVL

51. Trong cấu trúc dữ liệu cây, thuật ngữ ‘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 nút gốc

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 cạnh trên đường đi dài nhất từ nút đó đến một nút lá

D. Số lượng cạnh trên đường đi ngắn nhất từ nút đó đến một nút lá

52. Thuật toán nào sau đây thường được sử dụng để xây dựng cây Huffman?

A. Thuật toán Prim

B. Thuật toán Kruskal

C. Thuật toán tham lam

D. Thuật toán quay lui

53. Trong cây, nút nào sau đây có đúng một nút cha?

A. Nút gốc

B. Nút lá

C. Nút trung gian

D. Tất cả các nút

54. Độ phức tạp thời gian của thao tác chèn trong cây AVL là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

55. Cây nào sau đây thường được sử dụng để biểu diễn các biểu thức số học?

A. Cây nhị phân tìm kiếm

B. Cây quyết định

C. Cây biểu thức

D. Cây Huffman

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

A. Tìm kiếm một nút

B. Tìm nút nhỏ nhất

C. Tìm nút lớn nhất

D. Xóa nút gốc

57. Trong cây nhị phân, nút nào được gọi là ‘tổ tiên’ của một nút khác?

A. Nút nằm trên đường đi từ nút gốc đến nút đó

B. Nút con trực tiếp của nút đó

C. Nút lá gần nhất với nút đó

D. Nút có cùng chiều cao với nút đó

58. Trong cây đỏ đen, thuộc tính nào sau đây không đúng?

A. Mỗi nút là màu đỏ hoặc đen

B. Gốc là màu đen

C. Tất cả các đường đi từ một nút đến các nút lá chứa cùng số lượng nút đen

D. Nút đỏ có thể có nút con màu đỏ

59. Cây nào sau đây được sử dụng để tạo mã tiền tố tối ưu?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây Huffman

D. Cây B

60. Cây nào sau đây được sử dụng để thực hiện các phép toán tìm kiếm, chèn và xóa trong thời gian O(1) trung bình?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Bảng băm

D. Cây B

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

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

62. Trong cấu trúc dữ liệu đồ thị (graph), điều gì biểu thị một cạnh (edge)?

A. Một nút (node) trong đồ thị.

B. Một kết nối giữa hai nút.

C. Một tập hợp các nút.

D. Một đường dẫn duy nhất trong đồ thị.

63. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt hàng đợi (queue)?

A. Mảng (array)

B. Cây (tree)

C. Đồ thị (graph)

D. Ngăn xếp (stack)

64. Trong thuật toán sắp xếp trộn (merge sort), quá trình chia để trị (divide and conquer) được thực hiện như thế nào?

A. Chia mảng thành các phần tử đơn lẻ, sau đó trộn chúng lại.

B. Chọn một phần tử làm trục (pivot) và chia mảng thành hai phần.

C. So sánh các cặp phần tử liền kề và hoán đổi nếu chúng không đúng thứ tự.

D. Tìm phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên.

65. Trong một đồ thị có trọng số (weighted graph), thuật toán nào sau đây được sử dụng để 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?

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)

66. Ư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 đổi.

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.

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

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)

68. Hàng đợi ưu tiên (priority queue) thường được cài đặt 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 tìm kiếm nhị phân (binary search tree)

69. Thuật toán nào sau đây được sử dụng để tìm kiếm một chuỗi con trong một chuỗi lớn hơn?

A. Sắp xếp trộn (merge sort)

B. Tìm kiếm nhị phân (binary search)

C. Thuật toán Knuth-Morris-Pratt (KMP)

D. Tìm kiếm theo chiều sâu (depth-first search)

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

A. Khi cần tiết kiệm bộ nhớ.

B. Khi cần truy cập ngẫu nhiên đến các phần tử.

C. Khi cần duyệt danh sách theo cả hai hướng.

D. Khi cần chèn và xóa các phần tử ở đầu danh sách.

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

A. Nút gốc (root)

B. Nút lá (leaf)

C. Nút cha (parent)

D. Nút con (child)

72. 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 con bên trái lớn hơn nút gốc.

B. Tất cả các nút con bên phải nhỏ hơn nút gốc.

C. Nút gốc luôn là giá trị lớn nhất trong cây.

D. Tất cả các nút con bên trái nhỏ hơn nút gốc và tất cả các nút con bên phải lớn hơn nút gốc.

73. Thuật toán nào sau đây sử dụng kỹ thuật ‘chia để trị’?

A. Sắp xếp chèn (insertion sort)

B. Sắp xếp chọn (selection sort)

C. Sắp xếp nổi bọt (bubble sort)

D. Sắp xếp trộn (merge sort)

74. 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)

75. 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 đếm (counting sort)

D. Sắp xếp nhanh (quick sort)

76. Trong cấu trúc dữ liệu đồ thị, BFS là viết tắt của?

A. Breadth First Search

B. Best First Search

C. Breath First Sort

D. Block First Search

77. 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)

78. Kiểu dữ liệu trừu tượng (ADT) nào sau đây thường được sử dụng để triển khai tính năng hoàn tác (undo)?

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)

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

A. Hàng đợi (queue)

B. Danh sách liên kết (linked list)

C. Ngăn xếp (stack)

D. Cây (tree)

80. Trong cấu trúc dữ liệu đồ thị, một chu trình Euler là gì?

A. Một đường đi đi qua tất cả các nút một lần.

B. Một đường đi đi qua tất cả các cạnh một lần.

C. Một đường đi ngắn nhất giữa hai nút.

D. Một đường đi dài nhất trong đồ thị.

81. Trong cấu trúc dữ liệu đồ thị, DFS là viết tắt của?

A. Deep First Search

B. Depth First Sort

C. Data First Search

D. Dynamic First Search

82. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử 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(log n)

C. O(n^2)

D. O(1)

83. 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 chọn (selection sort)

D. Sắp xếp nhanh (quick sort)

84. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trường hợp 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 heap (heap sort)

D. Sắp xếp đếm (counting sort)

85. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian ổn định (stable)?

A. Sắp xếp nhanh (quick sort)

B. Sắp xếp heap (heap sort)

C. Sắp xếp chọn (selection sort)

D. Sắp xếp chèn (insertion sort)

86. Ư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 các phần tử với độ phức tạp thời gian trung bình là O(1).

C. Sử dụng bộ nhớ hiệu quả hơn so với mảng.

D. Dễ dàng mở rộng kích thước khi cần thiết.

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

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 duyệt tất cả các nút ở cùng một mức trước khi xuống mức sâu hơn.

D. Khi biết rằng giải pháp nằm gần nút gốc.

88. Thuật toán nào sau đây thường được sử dụng để duyệt cây theo chiều rộng (breadth-first traversal)?

A. Đệ quy (recursion)

B. Hàng đợi (queue)

C. Ngăn xếp (stack)

D. Sắp xếp (sorting)

89. Trong cấu trúc dữ liệu cây, chiều cao của một nút 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 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 đó.

90. Thuật toán nào sau đây được sử dụng để tìm kiếm đường đi ngắn nhất trong một đồ thị có trọng số âm?

A. Thuật toán Dijkstra

B. Tìm kiếm theo chiều rộng (breadth-first search)

C. Thuật toán Bellman-Ford

D. Tìm kiếm theo chiều sâu (depth-first search)

91. Trong cây AVL, sau khi chèn một nút, nếu cây trở nên mất cân bằng, thao tác nào sau đây được sử dụng để khôi phục tính cân bằng?

A. Sắp xếp

B. Tìm kiếm

C. Xoay (rotation)

D. Duyệt

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

A. Quản lý bộ nhớ

B. Cơ sở dữ liệu

C. Đồ họa máy tính

D. Mô phỏng vật lý

93. Đâu là ưu điểm của cây tìm kiếm nhị phân tự cân bằng (ví dụ: cây AVL, cây đỏ-đen) so với cây tìm kiếm nhị phân thông thường?

A. Dễ cài đặt hơn

B. Sử dụng ít bộ nhớ hơn

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, xóa trong trường hợp xấu nhất

D. Duyệt nhanh hơn

94. Cho một cây nhị phân tìm kiếm chứa các số nguyên, nếu bạn muốn tìm tất cả các số trong một khoảng [a, b], thuật toán nào là hiệu quả nhất?

A. Duyệt toàn bộ cây và kiểm tra từng nút

B. Tìm a, tìm b và duyệt tất cả các nút giữa a và b

C. Tìm a và duyệt theo inorder cho đến khi gặp b

D. Tìm a và duyệt theo preorder cho đến khi gặp b

95. Trong cây AVL, hệ số cân bằng (balance factor) của một nút được định nghĩa như thế nào?

A. Chiều cao của cây con trái trừ đi chiều cao của cây con phải

B. Chiều cao của cây con phải trừ đi chiều cao của cây con trái

C. Tổng chiều cao của cây con trái và cây con phải

D. Hiệu giữa số lượng nút trong cây con trái và cây con phải

96. Trong cây AVL, điều gì xảy ra nếu sau khi xóa một nút, cây trở nên mất cân bằng?

A. Cây tự động cân bằng lại mà không cần thao tác nào

B. Thao tác xoay được thực hiện để khôi phục lại sự cân bằng

C. Nút gốc được thay đổi

D. Cây bị xóa và tạo lại từ đầu

97. Thuật toán nào sau đây có thể được sử dụng để kiểm tra xem một cây nhị phân có phải là cây nhị phân tìm kiếm hợp lệ hay không?

A. Duyệt theo chiều rộng (BFS)

B. Duyệt theo chiều sâu (DFS)

C. Duyệt inorder và kiểm tra tính tăng dần

D. Duyệt preorder và kiểm tra tính giảm dần

98. Ứng dụng nào sau đây không phù hợp với cấu trúc dữ liệu cây?

A. Biểu diễn cấu trúc thư mục trong hệ điều hành

B. Lưu trữ thông tin về các mối quan hệ gia đình

C. Sắp xếp một danh sách các số nguyên

D. Xây dựng cây cú pháp trong trình biên dịch

99. Loại xoay nào được sử dụng trong cây AVL khi một nút được chèn vào cây con trái của cây con 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

100. Trong các thao tác sau trên cây nhị phân tìm kiếm, thao tác nào có độ phức tạp thời gian trung bình là 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

D. Duyệt cây theo thứ tự giữa (inorder traversal)

101. Điều gì xảy ra khi bạn cố gắng xóa một nút khỏi cây nhị phân tìm kiếm và nút đó có hai con?

A. Nút đó được thay thế bằng con trái của nó

B. Nút đó được thay thế bằng con phải của nó

C. Nút đó được thay thế bằng nút kế cận trước (inorder predecessor) hoặc nút kế cận sau (inorder successor) của nó

D. Nút đó đơn giản bị xóa và các con của nó trở thành nút gốc

102. Trong cây AVL, hệ số cân bằng của một nút có thể nhận những giá trị nào để cây được coi là cân bằng?

A. Chỉ 0

B. 0 hoặc 1

C. -1, 0 hoặc 1

D. Bất kỳ giá trị nào

103. Cho một cây nhị phân, thuật toán nào sau đây có thể được sử dụng để in ra tất cả các nút ở một mức độ cụ thể?

A. Duyệt theo chiều sâu (DFS)

B. Duyệt theo chiều rộng (BFS)

C. Duyệt inorder

D. Duyệt postorder

104. Khi nào thì việc sử dụng cây B+ (một biến thể của cây B) được ưu tiên hơn cây B?

A. Khi cần tìm kiếm các phần tử cụ thể

B. Khi cần chèn và xóa thường xuyên

C. Khi cần duyệt tất cả các phần tử theo thứ tự

D. Khi cần lưu trữ dữ liệu trong bộ nhớ

105. Trong cây B, bậc của cây (order) xác định điều gì?

A. Số lượng nút tối đa trong cây

B. Chiều cao tối đa của cây

C. Số lượng con tối đa mà một nút có thể có

D. Số lượng nút lá tối đa trong cây

106. Trong các cấu trúc dữ liệu cây sau đây, cấu trúc nào thường được sử dụng để biểu diễn các biểu thức số học?

A. Cây nhị phân tìm kiếm

B. Cây biểu thức (expression tree)

C. Cây AVL

D. Heap

107. Trong cây AVL, thao tác xoay nào được sử dụng khi mất cân bằng xảy ra ở cây con phải của cây con phải?

A. Xoay trái

B. Xoay phải

C. Xoay trái-phải

D. Xoay phải-trái

108. Cây nào sau đây đảm bảo rằng tất cả các nút lá đều ở cùng một mức hoặc mức gần cuối và các nút không phải lá có số lượng con tối thiểu?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây B

D. Heap

109. Ưu điểm chính của việc sử dụng cây B so với cây nhị phân tìm kiếm là gì?

A. Cây B dễ cài đặt hơn

B. Cây B có độ phức tạp thời gian tốt hơn cho tất cả các thao tác

C. Cây B hiệu quả hơn cho việc lưu trữ dữ liệu trên đĩa

D. Cây B sử dụng ít bộ nhớ hơn

110. Cho một cây nhị phân tìm kiếm, thứ tự duyệt nào sau đây sẽ cho ra một dãy các nút được sắp xếp tăng dần?

A. Preorder

B. Postorder

C. Inorder

D. Level order

111. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai một từ điển, nơi các thao tác tìm kiếm, chèn và xóa cần phải hiệu quả?

A. Mảng

B. Danh sách liên kết

C. Bảng băm

D. Hàng đợi

112. Khi nào thì cây nhị phân tìm kiếm suy biến thành một danh sách liên kết?

A. Khi tất cả các nút có giá trị bằng nhau

B. Khi các nút được chèn theo thứ tự ngẫu nhiên

C. Khi các nút được chèn theo thứ tự tăng dần hoặc giảm dần

D. Khi cây có số lượng nút chẵn

113. Độ phức tạp thời gian để tìm kiếm phần tử nhỏ nhất trong cây tìm kiếm nhị phân là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

114. Thao tác nào sau đây không được hỗ trợ trực tiếp bởi cấu trúc dữ liệu heap?

A. Tìm phần tử lớn nhất (hoặc nhỏ nhất)

B. Chèn một phần tử

C. Xóa phần tử lớn nhất (hoặc nhỏ nhất)

D. Tìm kiếm một phần tử bất kỳ

115. Cây nào sau đây đảm bảo rằng độ phức tạp thời gian cho các thao tác tìm kiếm, chèn và xóa là O(log n) trong trường hợp xấu nhất, với n là số nút?

A. Cây nhị phân tìm kiếm (Binary Search Tree)

B. Cây AVL

C. Cây heap

D. Cây B

116. Trong cây B, tại sao các nút thường chứa nhiều khóa thay vì chỉ một?

A. Để giảm chiều cao của cây

B. Để tăng tốc độ tìm kiếm

C. Để đơn giản hóa việc cài đặt

D. Để tiết kiệm bộ nhớ

117. Điểm khác biệt chính giữa cây nhị phân tìm kiếm và cây nhị phân đầy đủ là gì?

A. Cây nhị phân đầy đủ luôn cân bằng, còn cây nhị phân tìm kiếm thì không

B. Cây nhị phân tìm kiếm có tối đa hai con, còn cây nhị phân đầy đủ thì không

C. Cây nhị phân tìm kiếm tuân theo một thứ tự nhất định giữa các nút, còn cây nhị phân đầy đủ thì không

D. Cây nhị phân đầy đủ được sử dụng để tìm kiếm, còn cây nhị phân tìm kiếm thì không

118. Trong ngữ cảnh của cây B, thuật ngữ ‘độ đầy tối thiểu’ (minimum degree) đề cập đến điều gì?

A. Số lượng nút tối thiểu trong cây

B. Chiều cao tối thiểu của cây

C. Số lượng khóa tối thiểu mà một nút có thể chứa (trừ nút gốc)

D. Số lượng con tối thiểu mà một nút có thể có (trừ nút lá)

119. Trong cây B, mục đích của việc duy trì một số lượng khóa tối thiểu trong mỗi nút là gì?

A. Để giảm chiều cao của cây

B. Để đảm bảo rằng cây luôn cân bằng

C. Để tối ưu hóa việc sử dụng không gian đĩa

D. Để đơn giản hóa việc tìm kiếm

120. Cây nào sau đây thường được sử dụng để biểu diễn hàng đợi ưu tiên?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây B

D. Heap

121. Thuật toán nào sau đây được sử dụng để duyệt cây theo chiều rộng (breadth-first traversal)?

A. Đệ quy

B. Stack

C. Hàng đợi (Queue)

D. Heap

122. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong một cây nhị phân tìm kiếm cân bằng là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

123. Cây tìm kiếm nhị phân nào sau đây cho hiệu suất tìm kiếm tốt nhất trong trường hợp xấu nhất?

A. Cây suy biến

B. Cây hoàn chỉnh

C. Cây cân bằng (ví dụ: AVL, Red-Black)

D. Cây gần hoàn chỉnh

124. Cây nào sau đây đảm bảo rằng tất cả các nút lá đều ở cùng một độ sâu?

A. Cây nhị phân tìm kiếm

B. Cây AVL

C. Cây B+

D. Cây đỏ-đen

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

A. Mảng

B. Danh sách liên kết

C. Cây

D. Đồ thị

126. Cây nào sau đây thường được sử dụng để triển khai các bộ từ điển (dictionaries) và tập hợp (sets) trong các ngôn ngữ lập trình?

A. Cây nhị phân tìm kiếm

B. Cây B

C. Cây AVL

D. Cây đỏ-đen

127. Độ phức tạp thời gian để chèn một nút vào heap là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

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

A. Preorder

B. Inorder

C. Postorder

D. Level order

129. Khi nào thì cây nhị phân tìm kiếm (BST) trở thành cây suy biến (skewed tree)?

A. Khi tất cả các nút có giá trị bằng nhau

B. Khi các nút được chèn theo thứ tự ngẫu nhiên

C. Khi các nút được chèn theo thứ tự tăng dần hoặc giảm dần

D. Khi cây hoàn toàn cân bằng

130. Trong cây đỏ-đen, nếu một nút là đen, thì các nút con của nó phải như thế nào?

A. Cả hai phải là đỏ

B. Cả hai phải là đen

C. Một đỏ và một đen

D. Có thể là đỏ hoặc đen

131. 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

132. Trong cây AVL, yếu tố cân bằng (balance factor) của một nút được định nghĩa là gì?

A. Chiều cao của cây

B. Hiệu giữa chiều cao của cây con trái và cây con phải

C. Số lượng nút trong cây

D. Tổng giá trị của tất cả các nút trong cây

133. Trong cây B, tại sao các nút lá được liên kết với nhau?

A. Để tăng tốc độ tìm kiếm

B. Để cho phép duyệt tuần tự hiệu quả

C. Để giảm thiểu không gian lưu trữ

D. Để đơn giản hóa việc chèn và xóa

134. Trong cây B, bậc của cây (order) xác định điều gì?

A. Chiều cao tối đa 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ỗi nút có thể có

D. Số lượng khóa tối thiểu trong mỗi nút

135. Cho một cây nhị phân hoàn chỉnh với chiều cao h, số lượng nút tối đa có thể có trong cây là bao nhiêu?

A. h

B. 2h

C. 2^(h+1) – 1

D. 2^h – 1

136. Ứng dụng nào sau đây KHÔNG phải là ứng dụng phổ biến của cây?

A. Biểu diễn cấu trúc thư mục

B. Lưu trữ và truy xuất dữ liệu trong cơ sở dữ liệu

C. Quản lý bộ nhớ

D. Triển khai hàng đợi

137. Thao tác nào sau đây không được hỗ trợ trực tiếp bởi cấu trúc dữ liệu heap?

A. Tìm phần tử nhỏ nhất (hoặc lớn nhất)

B. Chèn một phần tử

C. Xóa phần tử nhỏ nhất (hoặc lớn nhất)

D. Tìm kiếm một phần tử cụ thể

138. Trong cây đỏ-đen, tính chất nào sau đây KHÔNG đúng?

A. Mỗi nút là đỏ hoặc đen

B. Gốc cây là đen

C. Tất cả các đường đi từ một nút đến các nút lá của nó chứa cùng một số lượng nút đen

D. Một nút đỏ có thể có một nút con đỏ

139. 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), với n là số lượng nút?

A. Duyệt theo thứ tự trước (preorder traversal)

B. Duyệt theo thứ tự sau (postorder traversal)

C. Tìm kiếm một nút

D. Duyệt theo chiều rộng (breadth-first traversal)

140. Cây nào sau đây đảm bảo độ phức tạp thời gian O(log n) cho cả thao tác tìm kiếm, chèn và xóa trong trường hợp xấu nhất?

A. Cây nhị phân tìm kiếm thông thường

B. Cây AVL

C. Cây B

D. Cây tìm kiếm B+.

141. Trong cây nhị phân, nếu một nút có một cây con trái và không có cây con phải, thì nút đó được gọi là gì?

A. Nút hoàn chỉnh

B. Nút đầy đủ

C. Nút nửa lá

D. Không có tên gọi cụ thể

142. Ứng dụng nào sau đây KHÔNG phải là ứng dụng của cây heap?

A. Sắp xếp heap (heapsort)

B. Hàng đợi ưu tiên

C. Nén dữ liệu

D. Tìm phần tử lớn thứ k

143. 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 tổ tiên

144. Thao tác nào sau đây thường được sử dụng để duy trì tính chất heap sau khi một phần tử được chèn hoặc xóa?

A. Tìm kiếm nhị phân

B. Sift-up (hoặc heapify up) và sift-down (hoặc heapify down)

C. Duyệt cây

D. Sắp xếp

145. Thuật toán nào sau đây sử dụng cây để biểu diễn dữ liệu và tìm đường đi ngắn nhất giữa hai nút?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Kruskal

D. Thuật toán Prim

146. Trong cây AVL, sau khi chèn một nút, nếu yếu tố cân bằng của một nút là -2, thao tác cân bằng nào cần được thực hiện?

A. Xoay trái

B. Xoay phải

C. Xoay trái-phải

D. Xoay phải-trái

147. Ưu điểm chính của việc sử dụng cây tìm kiếm B+ so với cây tìm kiếm B là gì?

A. Cây B+ có độ cao thấp hơn

B. Cây B+ cho phép tìm kiếm nhanh hơn các khóa cụ thể

C. Cây B+ hỗ trợ duyệt tuần tự dữ liệu hiệu quả hơn

D. Cây B+ dễ cài đặt hơn

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

A. Mảng

B. Danh sách liên kết

C. Cây nhị phân tìm kiếm

D. Heap

149. Ưu điểm của cây B+ so với cây nhị phân tìm kiếm là gì khi lưu trữ dữ liệu trên đĩa?

A. Cây B+ dễ cài đặt hơn

B. Cây B+ sử dụng ít bộ nhớ hơn

C. Cây B+ giảm thiểu số lượng truy cập đĩa

D. Cây B+ cho phép tìm kiếm nhanh hơn trong bộ nhớ

150. Trong cây nhị phân, một cây được coi là ‘hoàn chỉnh’ nếu điều gì sau đây đúng?

A. Tất cả các nút đều có hai con

B. Tất cả các mức đều được điền đầy đủ, ngoại trừ có thể mức cuối cùng được điền từ trái sang phải

C. Tất cả các nút lá đều ở cùng một mức

D. Cây là một cây tìm kiếm nhị phân

Or check our Popular Categories...

Or check our Popular Categories...

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

Or check our Popular Categories...

Or check our Popular Categories...

HƯỚNG DẪN TÌM MẬT KHẨU