1. 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?
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)
2. Thuật toán nào sau đây có độ phức tạp thời gian trung bình tốt nhất để sắp xếp một mảng lớn?
A. Bubble Sort
B. Insertion Sort
C. Selection Sort
D. Merge Sort
3. Thuật toán nào sau đây KHÔNG đảm bảo tính ổn định (stability) khi sắp xếp?
A. Insertion Sort
B. Merge Sort
C. Quick Sort
D. Bubble Sort
4. 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(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)
5. Cho một danh sách liên kết đơn (singly linked list), thao tác nào sau đây có độ phức tạp thời gian là O(1)?
A. Tìm kiếm một phần tử
B. Chèn một phần tử vào đầu danh sách
C. Xóa một phần tử ở cuối danh sách
D. Tìm độ dài của danh sách
6. Trong biểu đồ hàm băm (hash table), điều gì xảy ra khi hai khóa khác nhau băm (hash) đến cùng một chỉ mục?
A. Xảy ra lỗi và chương trình dừng lại.
B. Khóa mới sẽ ghi đè lên khóa cũ.
C. Xảy ra va chạm (collision) và cần một cơ chế xử lý va chạm.
D. Khóa mới không được chèn vào bảng băm.
7. Trong bảng băm (hash table), điều gì xảy ra khi hệ số tải (load factor) vượt quá một ngưỡng nhất định?
A. Bảng băm tự động giảm kích thước.
B. Bảng băm tự động tăng kích thước (rehashing).
C. Xảy ra lỗi tràn bộ nhớ.
D. Các phần tử mới không thể được chèn vào.
8. Đ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. Một ngoại lệ ‘StackOverflow’ sẽ được ném ra.
B. Một ngoại lệ ‘EmptyStackException’ sẽ được ném ra.
C. Giá trị null sẽ được trả về.
D. Chương trình sẽ bị treo.
9. Trong cây nhị phân tìm kiếm cân bằng (ví dụ: AVL tree, Red-Black tree), chiều cao của cây được giới hạn bởi:
A. O(n)
B. O(log n)
C. O(n^2)
D. O(sqrt(n))
10. Trong đồ thị, thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (minimum spanning tree)?
A. Tìm kiếm theo chiều rộng (Breadth-First Search)
B. Tìm kiếm theo chiều sâu (Depth-First Search)
C. Thuật toán Dijkstra
D. Thuật toán Prim
11. Trong cây quyết định (Decision Tree), thuộc tính nào được chọn làm nút gốc?
A. Thuộc tính có nhiều giá trị nhất
B. Thuộc tính có ít giá trị nhất
C. Thuộc tính có thông tin thu được (information gain) cao nhất
D. Thuộc tính được liệt kê đầu tiên trong tập dữ liệu
12. Thuật toán nào sau đây sử dụng kỹ thuật chia để trị (divide and conquer)?
A. Insertion Sort
B. Bubble Sort
C. Merge Sort
D. Selection Sort
13. Trong đồ 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)?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Tìm kiếm theo chiều rộng (Breadth-First Search) hoặc Tìm kiếm theo chiều sâu (Depth-First Search)
D. Thuật toán Kruskal
14. 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ế?
A. Bubble Sort
B. Selection Sort
C. Quick Sort
D. Insertion Sort
15. Trong đồ thị, điều gì xảy ra nếu một thuật toán tìm kiếm theo chiều sâu (DFS) thăm một đỉnh đã được thăm trước đó?
A. Thuật toán dừng lại.
B. Thuật toán tiếp tục duyệt từ đỉnh đó.
C. Thuật toán bỏ qua đỉnh đó.
D. Thuật toán xóa đỉnh đó khỏi đồ thị.
16. 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. Cây nhị phân tìm kiếm (Binary Search Tree)
D. Heap
17. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất là O(n) khi sắp xếp một mảng các số nguyên có giá trị trong một phạm vi nhỏ?
A. Quick Sort
B. Merge Sort
C. Counting Sort
D. Insertion Sort
18. Trong đồ 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?
A. Tìm kiếm theo chiều rộng (Breadth-First Search)
B. Tìm kiếm theo chiều sâu (Depth-First Search)
C. Thuật toán Dijkstra
D. Thuật toán Prim
19. Trong cây nhị phân, số lượng nút tối đa ở cấp độ ‘k’ là bao nhiêu (gốc cây ở cấp độ 0)?
20. 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 giống nhau) hay không?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
21. Thuật toán nào sau đây KHÔNG phải là một thuật toán sắp xếp dựa trên so sánh?
A. Merge Sort
B. Quick Sort
C. Counting Sort
D. Insertion Sort
22. Trong cấu trúc dữ liệu đồ thị, điều gì xảy ra khi bạn cố gắng thêm một cạnh giữa hai đỉnh đã được kết nối?
A. Một ngoại lệ sẽ được ném ra.
B. Đồ thị trở thành đồ thị vô hướng.
C. Cạnh mới sẽ được bỏ qua.
D. Đồ thị trở thành đồ thị đa (multigraph).
23. 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ố nút trong cây?
A. Duyệt cây theo thứ tự trước (preorder traversal)
B. Tìm kiếm một nút
C. Tìm nút có giá trị lớn nhất
D. Tìm nút có giá trị nhỏ nhất
24. 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. Danh sách liên kết (Linked List)
B. Hàng đợi (Queue)
C. Mảng (Array)
D. Ngăn xếp (Stack)
25. 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)
26. Cho một mảng đã được sắp xếp, thuật toán tìm kiếm nào hiệu quả nhất về mặt thời gian để tìm một phần tử?
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)
27. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ đỉnh nguồn đến các đỉnh khác?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Mảng (Array)
D. Hàng đợi ưu tiên (Priority Queue)
28. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai chức năng ‘undo’ trong các ứng dụng?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Danh sách liên kết (Linked List)
D. Mảng (Array)
29. 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. Đồ thị (Graph)
30. Độ 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(n log n)
C. O(n^2)
D. O(log n)
31. Trong cấu trúc dữ liệu đồ thị, phát biểu nào sau đây là đúng về biểu diễn bằng ma trận kề?
A. Ma trận kề sử dụng ít bộ nhớ hơn so với danh sách kề khi đồ thị có số lượng cạnh ít so với số lượng đỉnh.
B. Ma trận kề chỉ có thể biểu diễn được đồ thị vô hướng.
C. Ma trận kề sử dụng bộ nhớ tỉ lệ với số lượng đỉnh và cạnh của đồ thị.
D. Ma trận kề sử dụng bộ nhớ tỉ lệ với bình phương số lượng đỉnh của đồ thị.
32. Trong một đồ thị đầy đủ (complete graph) với n đỉnh, số lượng cạnh là bao nhiêu?
A. n – 1.
B. n.
C. n * (n – 1).
D. n * (n – 1) / 2.
33. Thành phần liên thông mạnh là gì trong một đồ thị có hướng?
A. Một tập hợp các đỉnh mà từ đó có thể đi đến mọi đỉnh khác trong đồ thị.
B. Một tập hợp các đỉnh mà giữa chúng có đường đi hai chiều.
C. Một tập hợp các đỉnh có bậc vào và bậc ra bằng nhau.
D. Một tập hợp các đỉnh mà không có đường đi giữa chúng.
34. Trong một đồ thị không trọng số, 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. Thuật toán Dijkstra.
B. Tìm kiếm theo chiều sâu (DFS).
C. Tìm kiếm theo chiều rộng (BFS).
D. Thuật toán Floyd-Warshall.
35. Phương pháp nào sau đây thường được sử dụng để phát hiện chu trình trong một đồ thị có hướng?
A. Tìm kiếm theo chiều rộng (BFS).
B. Tìm kiếm theo chiều sâu (DFS).
C. Thuật toán Dijkstra.
D. Thuật toán Prim.
36. Đồ thị nào sau đây chắc chắn có chu trình Hamilton?
A. Đồ thị có bậc của mọi đỉnh đều lớn hơn hoặc bằng một nửa số đỉnh.
B. Đồ thị có bậc của mọi đỉnh đều bằng 2.
C. Đồ thị có một đỉnh bậc lẻ.
D. Đồ thị không có cạnh.
37. Trong một đồ thị có hướng, điều kiện nào sau đây là cần và đủ để đồ thị có chu trình Euler?
A. Mọi đỉnh đều có bậc vào bằng bậc ra.
B. Đồ thị liên thông yếu.
C. Có một đỉnh có bậc vào lớn hơn bậc ra.
D. Có một đỉnh có bậc ra lớn hơn bậc vào.
38. Trong cấu trúc dữ liệu đồ thị, 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 và kết thúc ở đỉnh xuất phát.
C. Một đường đi ngắn nhất giữa hai đỉnh bất kỳ trong đồ thị.
D. Một đường đi qua tất cả các đỉnh và cạnh của đồ thị nhiều hơn một lần.
39. 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ố không âm?
A. Tìm kiếm theo chiều sâu (DFS).
B. Tìm kiếm theo chiều rộng (BFS).
C. Thuật toán Dijkstra.
D. Thuật toán sắp xếp nổi bọt (Bubble Sort).
40. Độ phức tạp thời gian tốt nhất của thuật toán Bellman-Ford là bao nhiêu?
A. O(1).
B. O(V).
C. O(E).
D. O(V*E).
41. Độ 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 đồ 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?
A. O(V).
B. O(E).
C. O(V + E).
D. O(V * E).
42. Cho đồ thị có 5 đỉnh và các cạnh như sau: (A, B), (A, C), (B, C), (B, D), (C, E). Nếu bắt đầu duyệt đồ thị bằng thuật toán DFS từ đỉnh A, thứ tự duyệt nào sau đây là hợp lệ?
A. A, B, C, D, E.
B. A, C, B, E, D.
C. A, B, D, C, E.
D. A, E, C, B, D.
43. Trong thuật toán Bellman-Ford, điều gì xảy ra nếu sau V-1 lần lặp, khoảng cách từ đỉnh nguồn đến một đỉnh nào đó vẫn còn thay đổi (V là số đỉnh)?
A. Thuật toán đã hoàn thành và cho ra kết quả đúng.
B. Đồ thị chứa chu trình âm.
C. Đỉnh đó không thể đạt được từ đỉnh nguồn.
D. Thuật toán cần thêm một lần lặp nữa.
44. Cho một đồ thị có hướng không chu trình (DAG), thuật toán nào sau đây có thể được sử dụng để sắp xếp các đỉnh theo thứ tự tô pô?
A. Tìm kiếm theo chiều rộng (BFS).
B. Tìm kiếm theo chiều sâu (DFS).
C. Thuật toán Dijkstra.
D. Thuật toán Prim.
45. Cho một mạng lưới giao thông được biểu diễn bằng đồ thị có hướng, trong đó các cạnh biểu diễn đường đi một chiều và trọng số biểu diễn thời gian di chuyển. Thuật toán nào sau đây phù hợp nhất để tìm tuyến đường nhanh nhất từ một điểm đến tất cả các điểm khác trong mạng lưới?
A. Thuật toán Prim.
B. Thuật toán Kruskal.
C. Thuật toán Dijkstra.
D. Tìm kiếm theo chiều sâu (DFS).
46. Thuật toán Prim và Kruskal được sử dụng để giải quyết bài toán nào trên đồ thị?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm chu trình Euler.
C. Tìm cây khung nhỏ nhất (Minimum Spanning Tree).
D. Tìm luồng cực đại trong mạng.
47. Trong thuật toán Ford-Fulkerson, mục tiêu chính là gì?
A. Tìm đường đi ngắn nhất từ đỉnh nguồn đến đỉnh đích.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Tìm luồng cực đại từ đỉnh nguồn đến đỉnh đích trong một mạng.
D. Tìm tất cả các thành phần liên thông mạnh trong đồ thị.
48. Cho đồ thị G = (V, E) với V là tập hợp các đỉnh và E là tập hợp các cạnh. Nếu |V| = 5 và |E| = 6, đồ thị này có thể là loại đồ thị nào sau đây?
A. Đồ thị cây (tree).
B. Đồ thị đầy đủ (complete graph).
C. Đồ thị liên thông.
D. Đồ thị không liên thông.
49. Trong biểu diễn đồ thị bằng danh sách kề, mỗi phần tử trong danh sách kề của một đỉnh đại diện cho điều gì?
A. Trọng số của các cạnh kề với đỉnh đó.
B. Các đỉnh kề với đỉnh đó.
C. Số lượng cạnh kề với đỉnh đó.
D. Màu của đỉnh đó trong quá trình duyệt đồ thị.
50. Thuật toán Tarjan được sử dụng để làm gì trong đồ thị?
A. Tìm đường đi ngắn nhất.
B. Tìm cây khung nhỏ nhất.
C. Tìm các thành phần liên thông mạnh.
D. Sắp xếp các đỉnh theo thứ tự tô pô.
51. Trong thuật toán Ford-Fulkerson, khái niệm ‘đường tăng’ (augmenting path) là gì?
A. Đường đi ngắn nhất từ đỉnh nguồn đến đỉnh đích.
B. Đường đi từ đỉnh nguồn đến đỉnh đích mà dọc theo đó có thể tăng luồng.
C. Đường đi có tổng trọng số các cạnh nhỏ nhất.
D. Đường đi không chứa chu trình.
52. Trong một đồ thị vô hướng liên thông, số lượng cạnh tối thiểu cần thiết để đảm bảo đồ thị vẫn liên thông sau khi loại bỏ một cạnh bất kỳ là bao nhiêu, nếu đồ thị có V đỉnh?
A. V – 1.
B. V.
C. V + 1.
D. V * (V – 1) / 2.
53. Khi nào nên sử dụng ma trận kề thay vì danh sách kề để biểu diễn đồ thị?
A. Khi đồ thị có số lượng cạnh ít hơn nhiều so với số lượng đỉnh.
B. Khi đồ thị có số lượng cạnh nhiều gần bằng số lượng đỉnh.
C. Khi cần kiểm tra nhanh sự tồn tại của một cạnh giữa hai đỉnh.
D. Khi cần duyệt qua tất cả các đỉnh kề của một đỉnh.
54. Ứng dụng nào sau đây sử dụng đồ thị để mô hình hóa và giải quyết vấn đề?
A. Quản lý bộ nhớ trong hệ điều hành.
B. Lập kế hoạch dự án (ví dụ: PERT/CPM).
C. Sắp xếp dữ liệu trong cơ sở dữ liệu.
D. Nén dữ liệu.
55. Cho một đồ thị có trọng số, thuật toán Floyd-Warshall được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa một đỉnh và tất cả các đỉnh còn lại.
B. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.
C. Tìm cây khung nhỏ nhất.
D. Tìm luồng cực đại trong mạng.
56. Trong bài toán tô màu đồ thị, mục tiêu là gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm chu trình Hamilton.
C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau có cùng màu và sử dụng số lượng màu ít nhất.
D. Tìm cây khung nhỏ nhất.
57. 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?
A. Mảng.
B. Hàng đợi.
C. Cấu trúc Disjoint Set (Union-Find).
D. Cây nhị phân tìm kiếm.
58. Ứng dụng nào sau đây liên quan đến việc tìm đường đi ngắn nhất trong thực tế?
A. Phân tích mạng xã hội.
B. Định tuyến giao thông (ví dụ: Google Maps).
C. Xử lý ảnh.
D. Dự báo thời tiết.
59. Ứng dụng nào sau đây không phải là ứng dụng phổ biến của thuật toán duyệt đồ thị?
A. Tìm đường đi trong trò chơi điện tử.
B. Kiểm tra tính liên thông của mạng xã hội.
C. Sắp xếp dữ liệu trong cơ sở dữ liệu.
D. Tìm kiếm các thành phần liên thông trong một mạng lưới.
60. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ đỉnh nguồn đến các đỉnh khác?
A. Mảng.
B. Hàng đợi.
C. Cây nhị phân tìm kiếm.
D. Hàng đợi ưu tiên (Priority Queue).
61. Cây nào sau đây đảm bảo độ phức tạp O(log n) cho tất cả cá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 tìm kiếm nhị phân (binary search tree)
B. Cây B (B-tree)
C. Cây AVL (AVL tree)
D. Cây khung (spanning tree)
62. Trong một cây quyết định (decision tree), điều gì đại diện cho một nút lá?
A. Một thuộc tính (attribute) được sử dụng để đưa ra quyết định.
B. Một quyết định hoặc kết quả cuối cùng.
C. Một nhánh (branch) của cây.
D. Một tập hợp các thuộc tính.
63. Trong cây quyết định, kỹ thuật nào sau đây được sử dụng để tránh overfitting (quá khớp) dữ liệu huấn luyện?
A. Tăng chiều cao của cây.
B. Giảm số lượng thuộc tính sử dụng.
C. Pruning (cắt tỉa) cây.
D. Sử dụng nhiều dữ liệu huấn luyện hơn.
64. Khi nào việc sử dụng cây B+ thay vì cây B là phù hợp hơn?
A. Khi cần tìm kiếm một khóa cụ thể một cách nhanh chóng.
B. Khi cần thực hiện các truy vấn phạm vi (range queries) một cách hiệu quả.
C. Khi cần chèn và xóa các khóa một cách nhanh chóng.
D. Khi dữ liệu nhỏ và vừa với bộ nhớ chính.
65. Ưu điểm chính của việc sử dụng cây B thay vì cây tìm kiếm nhị phân thông thường để lưu trữ dữ liệu trên đĩa là gì?
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 cần thiết để tìm kiếm dữ liệu.
D. Cây B có thể lưu trữ nhiều dữ liệu hơn trong cùng một không gian đĩa.
66. Trong cây tìm kiếm nhị phân, việc duyệt cây theo thứ tự giữa (inorder traversal) sẽ cho kết quả gì?
A. Các nút được sắp xếp theo thứ tự tăng dần.
B. Các nút được sắp xếp theo thứ tự giảm dần.
C. Các nút được duyệt theo thứ tự mức.
D. Thứ tự duyệt phụ thuộc vào cấu trúc cây.
67. Một công ty muốn lưu trữ thông tin về nhân viên của mình trong một cấu trúc dữ liệu cho phép tìm kiếm nhân viên theo ID một cách nhanh chóng. Cấu trúc dữ liệu nào sau đây phù hợp nhất?
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 không cân bằng
68. Một ứng dụng cần lưu trữ dữ liệu theo thứ tự ưu tiên, trong đó phần tử có độ ưu tiên cao nhất luôn được truy xuất đầu tiên. Cấu trúc dữ liệu nào sau đây phù hợp nhất?
A. Cây tìm kiếm nhị phân (binary search tree)
B. Hàng đợi ưu tiên (priority queue)
C. Danh sách liên kết (linked list)
D. Mảng (array)
69. Một hệ thống quản lý tệp sử dụng cấu trúc cây để tổ chức các thư mục và tệp. Cấu trúc cây này được gọi là gì?
A. Cây tìm kiếm nhị phân (binary search tree)
B. Cây thư mục (directory tree)
C. Cây quyết định (decision tree)
D. Cây Huffman (Huffman tree)
70. 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 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. Duyệt cây theo thứ tự giữa (inorder traversal)
71. Trong cây AVL, thao tác nào sau đây được sử dụng để duy trì tính cân bằng của cây sau khi chèn hoặc xóa một nút?
A. Tìm kiếm nhị phân
B. Xoay cây (tree rotation)
C. Băm (hashing)
D. Sắp xếp (sorting)
72. Khi nào nên sử dụng bảng băm thay vì cây tìm kiếm nhị phân?
A. Khi cần duyệt các phần tử theo thứ tự đã sắp xếp.
B. Khi số lượng phần tử cần lưu trữ rất nhỏ.
C. Khi cần thực hiện các thao tác tìm kiếm, chèn và xóa với độ phức tạp thời gian trung bình là O(1).
D. Khi cần đảm bảo rằng tất cả các thao tác đều có độ phức tạp thời gian O(log n).
73. Một ứng dụng cần lưu trữ dữ liệu địa lý (ví dụ: tọa độ các thành phố) và thực hiện các truy vấn tìm kiếm các thành phố gần một vị trí nhất định. Cấu trúc dữ liệu nào sau đây phù hợp nhất?
A. Cây tìm kiếm nhị phân (binary search tree)
B. Cây B (B-tree)
C. Cây R (R-tree)
D. Bảng băm (hash table)
74. 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. Ngăn xếp (stack)
C. Hàng đợi (queue)
D. Bảng băm (hash table)
75. Trong thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ nút nguồn đến các nút khác?
A. Hàng đợi (queue)
B. Ngăn xếp (stack)
C. Hàng đợi ưu tiên (priority queue)
D. Mảng (array)
76. Ứng dụng nào sau đây KHÔNG phải là ứng dụng phổ biến của cây?
A. Biên dịch mã nguồn
B. Lập chỉ mục cơ sở dữ liệu
C. Định tuyến mạng
D. Sắp xếp một mảng các số nguyên
77. Trong cây khung nhỏ nhất (minimum spanning tree), thuật toán nào sau đây được sử dụng phổ biến nhất?
A. Thuật toán Dijkstra
B. Thuật toán Floyd-Warshall
C. Thuật toán Prim
D. Thuật toán sắp xếp nổi bọt (bubble sort)
78. 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ư sơ đồ tổ chức của một công ty?
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)
79. Khi nào nên sử dụng cây Trie (tiền tố) thay vì bảng băm để lưu trữ một tập hợp các chuỗi?
A. Khi cần tìm kiếm một chuỗi cụ thể một cách nhanh chóng.
B. Khi cần thực hiện các truy vấn tiền tố (prefix queries) một cách hiệu quả.
C. Khi cần lưu trữ các chuỗi có độ dài khác nhau.
D. Khi cần lưu trữ các chuỗi có tần suất xuất hiện khác nhau.
80. Trong cây tìm kiếm nhị phân cân bằng, chiều cao của cây có liên quan như thế nào đến 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 không liên quan đến n.
81. Điều gì xảy ra nếu bạn cố gắng chèn một khóa đã tồn tại vào cây tìm kiếm nhị phân?
A. Một ngoại lệ sẽ được ném ra.
B. Khóa mới sẽ thay thế khóa cũ.
C. Khóa mới sẽ được bỏ qua.
D. Hành vi phụ thuộc vào việc triển khai cây tìm kiếm nhị phân.
82. Độ phức tạp thời gian tốt nhất của thao tác tìm kiếm trong một cây tìm kiếm nhị phân cân bằng là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
83. Ứng dụng nào sau đây sử dụng cây để biểu diễn cú pháp của một chương trình?
A. Trình biên dịch (compiler)
B. Hệ điều hành (operating system)
C. Cơ sở dữ liệu (database)
D. Trình soạn thảo văn bản (text editor)
84. Khi xây dựng một cây Huffman để nén dữ liệu, tiêu chí nào được sử dụng để xác định thứ tự hợp nhất các nút?
A. Tần suất xuất hiện của các ký tự.
B. Thứ tự bảng chữ cái của các ký tự.
C. Độ dài mã của các ký tự.
D. Kích thước của các ký tự.
85. Cho một cây biểu thức (expression tree) đại diện cho biểu thức số học. Thuật toán nào sau đây được sử dụng để tính giá trị của biểu thức?
A. Duyệt theo thứ tự trước (preorder traversal)
B. Duyệt theo thứ tự giữa (inorder traversal)
C. Duyệt theo thứ tự sau (postorder traversal)
D. Duyệt theo chiều rộng (breadth-first traversal)
86. Trong cây đỏ-đen, điều gì xảy ra khi chèn một nút mới và vi phạm các thuộc tính của cây?
A. Nút mới sẽ bị xóa.
B. Cây sẽ được xây dựng lại hoàn toàn.
C. Các phép xoay và đổi màu nút sẽ được thực hiện để khôi phục các thuộc tính.
D. Cây sẽ trở thành cây tìm kiếm nhị phân không cân bằng.
87. 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 khóa tối thiểu trong cây.
88. Cho một cây tìm kiếm nhị phân chứa các số nguyên. Nếu bạn muốn tìm số lớn thứ hai trong cây, bạn nên sử dụng thuật toán duyệt cây nào?
A. Duyệt theo thứ tự trước (preorder traversal)
B. Duyệt theo thứ tự giữa (inorder traversal)
C. Duyệt theo thứ tự sau (postorder traversal)
D. Duyệt theo thứ tự giữa đảo ngược (reverse inorder traversal)
89. Trong cây đỏ-đen, thuộc tính 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 số lượng nút đen.
D. Một nút đỏ có thể có một nút con đỏ.
90. Cho một cây tìm kiếm nhị phân không cân bằng. Thao tác nào sau đây có thể cải thiện hiệu suất tìm kiếm của cây?
A. Chèn thêm các nút mới.
B. Xóa các nút hiện có.
C. Cân bằng lại cây (tree balancing).
D. Thay đổi thứ tự duyệt cây.
91. Ứng dụng thực tế nào sau đây sử dụng cấu trúc dữ liệu bảng băm (hash table)?
A. Quản lý bộ nhớ trong hệ điều hành.
B. Tìm kiếm từ trong từ điển.
C. Định tuyến gói tin trên internet.
D. Tất cả các đáp án trên.
92. Trong thuật toán Kruskal, điều gì xảy ra nếu việc thêm một cạnh vào cây khung hiện tại tạo thành một chu trình?
A. Cạnh đó được giữ lại và chu trình được xóa.
B. Cạnh đó bị loại bỏ.
C. Thuật toán dừng lại và trả về cây khung hiện tại.
D. Một cạnh khác được chọn ngẫu nhiên để thay thế.
93. 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ừ nút nguồn đến các nút khác?
A. Hàng đợi (Queue).
B. Ngăn xếp (Stack).
C. Mảng (Array).
D. Cây nhị phân tìm kiếm (Binary Search Tree).
94. Trong thuật toán Kruskal, mục đích chính của việc sử dụng cấu trúc dữ liệu Union-Find là gì?
A. Sắp xếp các cạnh theo trọng số.
B. Kiểm tra xem hai đỉnh có thuộc cùng một thành phần liên thông hay không.
C. Tìm đường đi ngắn nhất giữa hai đỉnh.
D. Duyệt tất cả các đỉnh của đồ thị.
95. Trong cây quyết định, thuộc tính nào được chọn làm nút gốc?
A. Thuộc tính có ít giá trị nhất.
B. Thuộc tính được chọn ngẫu nhiên.
C. Thuộc tính có độ lợi thông tin cao nhất.
D. Thuộc tính có độ lợi thông tin thấp nhất.
96. Trong cây đỏ đen (red-black tree), thuộc tính nào sau đây luôn đúng?
A. Tất cả các nút đều có màu đỏ.
B. Tất cả các đường đi từ một nút đến các nút lá của nó đều có số lượng nút đen như nhau.
C. Tất cả các nút đều có màu đen.
D. Nút gốc luôn có màu đỏ.
97. Trong cây B, bậc của cây (order) ảnh hưởng đến yếu tố nào sau đây?
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. Tất cả các đáp án trên.
98. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong cây nhị phân tìm kiếm (BST) là bao nhiêu?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
99. Thuật toán nào sau đây có thể đượ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.
100. Ư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. Tiết kiệm 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. Dễ dàng sắp xếp hơn.
101. Trong cấu trúc dữ liệu heap, thao tác nào sau đây có độ phức tạp thời gian là O(1)?
A. Tìm phần tử lớn nhất (trong max-heap).
B. Chèn một phần tử mới.
C. Xóa phần tử lớn nhất (trong max-heap).
D. Tìm kiếm một phần tử cụ thể.
102. Thuật toán nào sau đây sử dụng 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 trộn (Merge Sort).
D. Sắp xếp chọn (Selection Sort).
103. Độ 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?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
104. 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?
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).
105. Trong cây AVL, thao tác nào sau đây được sử dụng để duy trì tính cân bằng?
A. Sắp xếp (Sorting).
B. Xoay (Rotation).
C. Tìm kiếm (Searching).
D. Chèn (Insertion).
106. Trong cấu trúc dữ liệu đồ thị, sự khác biệt chính giữa đồ thị có hướng (directed graph) và đồ thị vô hướng (undirected graph) là gì?
A. Đồ thị có hướng có trọng số, đồ thị vô hướng không có trọng số.
B. Đồ thị có hướng có chu trình, đồ thị vô hướng không có chu trình.
C. Trong đồ thị có hướng, các cạnh có hướng, trong khi đồ thị vô hướng các cạnh không có hướng.
D. Đồ thị có hướng có ít đỉnh hơn đồ thị vô hướng.
107. Trong thuật toán Floyd-Warshall, mục đích chính là gì?
A. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác.
B. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.
C. Tìm cây khung nhỏ nhất của đồ thị.
D. Tìm chu trình Euler trong đồ thị.
108. Trong cây quyết định, kỹ thuật nào được sử dụng để tránh overfitting?
A. Tăng chiều sâu của cây.
B. Pruning (cắt tỉa cây).
C. Sử dụng nhiều thuộc tính hơn.
D. Giảm số lượng mẫu huấn luyện.
109. Ứng dụng nào sau đây phù hợp nhất với cấu trúc dữ liệu đồ thị?
A. Quản lý danh sách sinh viên.
B. Biểu diễn mạng xã hội.
C. Lưu trữ lịch sử duyệt web.
D. Sắp xếp danh sách các số.
110. Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (DFS) thay vì tìm kiếm theo chiều rộng (BFS)?
A. Khi cần tìm đường đi ngắn nhất.
B. Khi cần duyệt tất cả các đỉnh của đồ thị.
C. Khi không gian tìm kiếm rất lớn và có thể có đường đi dài.
D. Khi cần tìm tất cả các thành phần liên thông.
111. Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (bubble sort) trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(n log n)
112. 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. Hàng đợi (Queue).
B. Ngăn xếp (Stack).
C. Heap (Min-Heap).
D. Mảng (Array).
113. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các nút sẽ được duyệt?
A. Ngăn xếp (Stack).
B. Hàng đợi (Queue).
C. Cây nhị phân tìm kiếm (Binary Search Tree).
D. Đồ thị (Graph).
114. 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 (priority queue)?
A. Mảng (Array).
B. Danh sách liên kết (Linked List).
C. Heap (Min-Heap hoặc Max-Heap).
D. Cây nhị phân tìm kiếm (Binary Search Tree).
115. Ưu điểm chính của việc sử dụng bảng băm (hash table) là gì?
A. Duy trì thứ tự các phần tử.
B. Truy cập ngẫu nhiên các phần tử trong thời gian O(1) trung bình.
C. Tìm kiếm phần tử nhỏ nhất trong thời gian O(1).
D. Sắp xếp các phần tử trong thời gian O(log n).
116. Trong thuật toán Dijkstra, nếu đồ thị chứa cạnh có trọng số âm, điều gì sẽ xảy ra?
A. Thuật toán vẫn hoạt động bình thường.
B. Thuật toán có thể không tìm được đường đi ngắn nhất chính xác.
C. Thuật toán sẽ báo lỗi và dừng lại.
D. Thuật toán sẽ bỏ qua các cạnh có trọng số âm.
117. Khi nào thì thuật toán sắp xếp chèn (insertion sort) hoạt động hiệu quả nhất?
A. Khi dữ liệu đã được sắp xếp hoàn toàn.
B. Khi dữ liệu được sắp xếp ngược.
C. Khi dữ liệu gần như đã được sắp xếp.
D. Khi dữ liệu có số lượng phần tử lớn.
118. Khi nào nên sử dụng thuật toán sắp xếp trộn (merge sort) thay vì sắp xếp nhanh (quick sort)?
A. Khi cần sắp xếp tại chỗ (in-place).
B. Khi cần độ phức tạp thời gian trung bình tốt hơn.
C. Khi cần độ ổn định (stability) trong quá trình sắp xếp.
D. Khi dữ liệu gần như đã được sắp xếp.
119. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue).
B. Danh sách liên kết (Linked List).
C. Ngăn xếp (Stack).
D. Cây (Tree).
120. Phương pháp nào sau đây được sử dụng để giải quyết xung đột trong bảng băm?
A. Sắp xếp nổi bọt (Bubble Sort).
B. Địa chỉ mở (Open Addressing).
C. Tìm kiếm nhị phân (Binary Search).
D. Duyệt theo chiều sâu (Depth-First Search).
121. 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. Hiệu của chiều cao cây con trái và chiều cao cây con phải.
B. Tổng của chiều cao cây con trái và chiều cao cây con phải.
C. Số lượng nút trong cây con trái.
D. Số lượng nút trong cây con phải.
122. Phương pháp duyệt cây nào sau đây sử dụng stack một cách tường minh (explicitly)?
A. Duyệt theo chiều rộng (Breadth-First Traversal)
B. Duyệt theo thứ tự trước (Preorder Traversal) không đệ quy
C. Duyệt theo thứ tự giữa (Inorder Traversal) đệ quy
D. Duyệt theo thứ tự sau (Postorder Traversal) đệ quy
123. Cho một cây nhị phân tìm kiếm, làm thế nào để tìm nút có giá trị nhỏ nhất?
A. Duyệt theo thứ tự trước (preorder) và trả về nút đầu tiên.
B. Duyệt theo thứ tự sau (postorder) và trả về nút cuối cùng.
C. Đi xuống cây con trái cho đến khi không còn cây con trái nào.
D. Đi xuống cây con phải cho đến khi không còn cây con phải nào.
124. Trong cây nhị phân, nút gốc (root) là nút như thế nào?
A. Nút có giá trị lớn nhất.
B. Nút không có nút cha.
C. Nút có cả nút con trái và nút con phải.
D. Nút có giá trị nhỏ nhất.
125. Điều gì xảy ra nếu bạn chèn các giá trị đã được sắp xếp theo thứ tự tăng dần vào một cây nhị phân tìm kiếm?
A. Cây trở nên cân bằng.
B. Cây trở thành cây suy biến (dạng danh sách liên kết).
C. Cây trở thành cây AVL.
D. Cây trở thành cây đỏ đen.
126. 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 tổng quát (General tree).
D. Heap.
127. Ứng dụng nào sau đây KHÔNG phù hợp với cấu trúc dữ liệu cây?
A. Lưu trữ dữ liệu phân cấp (ví dụ: cấu trúc thư mục).
B. Biểu diễn biểu thức toán học.
C. Quản lý danh sách các công việc cần thực hiện theo thứ tự ưu tiên.
D. Tìm kiếm và sắp xếp dữ liệu.
128. Độ phức tạp thời gian của thao tác chèn một nút vào cây AVL là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
129. Trong cây B, bậc của cây (order) thường được định nghĩa là gì?
A. Số lượng nút tối đa trong cây.
B. Số lượng con tối đa mà một nút có thể có.
C. Chiều cao của cây.
D. Số lượng lá trong cây.
130. 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. Tìm kiếm một nút.
C. Duyệt theo thứ tự sau (postorder traversal).
D. Duyệt theo thứ tự giữa (inorder traversal).
131. Cây nào sau đây thường được sử dụng trong các thuật toán nén dữ liệu như Huffman coding?
A. Cây nhị phân tìm kiếm.
B. Cây B.
C. Cây Huffman.
D. Cây AVL.
132. Điều gì xảy ra với độ phức tạp của thao tác tìm kiếm trong cây nhị phân tìm kiếm khi cây trở nên mất cân bằng?
A. Độ phức tạp giảm xuống O(1).
B. Độ phức tạp không đổi.
C. Độ phức tạp tăng lên O(n).
D. Độ phức tạp tăng lên O(n log n).
133. Trong cây nhị phân tìm kiếm, thứ tự duyệt nào sau đây sẽ cho ra các nút theo thứ tự tăng dần?
A. Preorder (NLR)
B. Postorder (LRN)
C. Inorder (LNR)
D. Level order
134. Trong cây, nút nào được gọi là lá (leaf)?
A. Nút gốc.
B. Nút không có con.
C. Nút có một con.
D. Nút có hai con.
135. Cây nào sau đây KHÔNG phải là một loại cây tự cân bằng?
A. Cây AVL
B. Cây Red-Black
C. Cây B
D. Cây Heap
136. 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 một nút.
B. Chèn một nút.
C. Sắp xếp các nút.
D. Xóa một nút.
137. Trong cây, 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ừ nút gốc đến nút lá.
B. Số lượng cạnh trên đường đi dài nhất từ nút gốc đến nút lá.
C. Số lượng nút trong cây.
D. Số lượng lá trong cây.
138. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn một cây gia phả?
A. Mảng.
B. Danh sách liên kết.
C. Cây tổng quát (General tree).
D. Đồ thị.
139. Cây nào sau đây đảm bảo độ phức tạp 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?
A. Cây nhị phân tìm kiếm thông thường.
B. Cây AVL.
C. Cây tìm kiếm B.
D. Heap.
140. Độ 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à bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
141. Trong cây, độ sâu của một nút được định nghĩa là gì?
A. Số lượng nút trên đường đi từ nút đó đến nút gốc.
B. Số lượng cạnh trên đường đi từ nút gốc đến nút đó.
C. Số lượng nút con của nút đó.
D. Giá trị của nút đó.
142. Ư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 hiệu quả hơn khi dữ liệu được lưu trữ trên đĩa.
C. Cây B luôn có độ cao nhỏ hơn cây nhị phân.
D. Cây B hỗ trợ tìm kiếm nhanh hơn trong bộ nhớ.
143. Ứng dụng thực tế nào sau đây sử dụng cấu trúc dữ liệu cây?
A. Quản lý bộ nhớ.
B. Lập lịch CPU.
C. Hệ thống quản lý cơ sở dữ liệu.
D. Mô phỏng mạng.
144. Trong cây nhị phân hoàn chỉnh (complete binary tree), các nút được đánh số từ 1 trở đi. Cho nút có chỉ số `i`, chỉ số của nút cha của nó là gì?
A. i * 2
B. i / 2
C. i – 1
D. i + 1
145. Cây đỏ đen (Red-Black tree) là một loại cây gì?
A. Cây tìm kiếm nhị phân không cân bằng.
B. Cây tìm kiếm nhị phân tự cân bằng.
C. Cây mà tất cả các nút đều có màu đỏ.
D. Cây mà tất cả các nút đều có màu đen.
146. 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 tìm kiếm.
B. Cây AVL.
C. Cây hoàn chỉnh (Complete tree).
D. Cây đầy đủ (Perfect tree).
147. Trong cây, bậc của một nút được định nghĩa là gì?
A. Số lượng nút trên đường đi từ nút đó đến nút gốc.
B. Số lượng cạnh trên đường đi từ nút gốc đến nút đó.
C. Số lượng nút con của nút đó.
D. Giá trị của nút đó.
148. 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. Stack
B. Hàng đợi (Queue)
C. Đệ quy
D. Cây nhị phân
149. Trong cây nhị phân đầy đủ (full binary tree), nếu số nút là 15, thì số nút lá là bao nhiêu?
150. Khi nào thì cây nhị phân tìm kiếm trở thành cây suy biến (degenerate tree)?
A. Khi cây có quá nhiều nút.
B. Khi tất cả các nút chỉ có một con.
C. Khi cây hoàn toàn cân bằng.
D. Khi cây không có nút gốc.
