1. Trong biểu đồ (graph), thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại?
A. Tìm kiếm theo chiều sâu (Depth-First Search – DFS)
B. Tìm kiếm theo chiều rộng (Breadth-First Search – BFS)
C. Thuật toán Dijkstra
D. Thuật toán Prim
2. 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 truy cập phần tử cuối cùng nhanh chóng
B. Khi cần duyệt danh sách theo cả hai chiều
C. Khi cần tiết kiệm bộ nhớ
D. Khi cần chèn phần tử vào đầu danh sách nhanh chóng
3. Khi nào nên sử dụng cấu trúc dữ liệu ‘heap’?
A. Khi cần tìm kiếm một phần tử cụ thể
B. Khi cần sắp xếp một mảng
C. Khi cần truy xuất phần tử lớn nhất hoặc nhỏ nhất một cách nhanh chóng
D. Khi cần duyệt tất cả các phần tử theo thứ tự
4. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là bao nhiêu?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
5. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu?
A. Thuật toán Dijkstra
B. Thuật toán Huffman
C. Thuật toán Prim
D. Thuật toán Kruskal
6. Ư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ì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước không xác định trước
C. Tìm kiếm phần tử nhanh hơn
D. Sắp xếp phần tử nhanh hơn
7. Trong thuật toán sắp xếp trộn (Merge Sort), quá trình ‘trộn’ (merge) hai mảng đã sắp xếp có độ phức tạp thời gian là bao nhiêu?
A. O(log n)
B. O(1)
C. O(n)
D. O(n log n)
8. 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 (preorder)
B. Duyệt cây theo thứ tự sau (postorder)
C. Tìm kiếm một phần tử
D. Duyệt cây theo thứ tự giữa (inorder)
9. Trong lập trình, kỹ thuật ‘memoization’ thường được sử dụng để làm gì?
A. Giảm độ phức tạp không gian của thuật toán
B. Tăng tốc độ thực thi bằng cách lưu trữ kết quả của các hàm đã được gọi trước đó
C. Đảm bảo tính bảo mật của dữ liệu
D. Đơn giản hóa mã nguồn
10. Khi nào nên sử dụng ‘lập trình động’ (dynamic programming)?
A. Khi cần giải quyết các bài toán có cấu trúc con chồng chéo
B. Khi cần tìm kiếm một phần tử cụ thể
C. Khi cần sắp xếp một mảng
D. Khi cần duyệt tất cả các phần tử theo thứ tự
11. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Cây (Tree)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
12. Khi nào nên sử dụng bảng băm (hash table) thay vì cây tìm kiếm nhị phân?
A. Khi cần duy trì thứ tự các phần tử
B. Khi cần tìm kiếm phần tử nhỏ nhất hoặc lớn nhất
C. Khi cần tìm kiếm, chèn, xóa phần tử với độ phức tạp trung bình O(1)
D. Khi cần duyệt tất cả các phần tử theo thứ tự
13. Thuật toán nào sau đây là một ví dụ của kỹ thuật ‘chia để trị’ (divide and conquer)?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Tìm kiếm tuyến tính (Linear Search)
D. Sắp xếp nhanh (Quick Sort)
14. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt bộ nhớ cache?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Bảng băm (Hash table)
D. Cây (Tree)
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ệ ‘cha-con’ trong một tổ chức?
A. Hàng đợi (Queue)
B. Đồ thị (Graph)
C. Cây (Tree)
D. Ngăn xếp (Stack)
16. 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)?
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 chọn (Selection Sort)
17. Trong cây nhị phân, nút gốc (root) là gì?
A. Nút không có con
B. Nút có nhiều con nhất
C. Nút không có cha
D. Nút nằm ở mức sâu nhất
18. Trong một đồ thị vô hướng, bậc của một đỉnh là gì?
A. Số lượng đỉnh kề với đỉnh đó
B. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác
C. Số lượng cạnh nối với đỉnh đó
D. Tổng trọng số của các cạnh nối với đỉnh đó
19. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào sau đây được sử dụng?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
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 có phải là palindrome hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
21. Điểm khác biệt chính giữa cây nhị phân tìm kiếm (BST) và cây AVL là gì?
A. Cây AVL luôn cân bằng, đảm bảo độ phức tạp O(log n) cho các thao tác tìm kiếm, chèn, xóa
B. Cây BST có thể chứa các giá trị trùng lặp
C. Cây AVL dễ cài đặt hơn cây BST
D. Cây BST luôn có chiều cao nhỏ hơn cây AVL
22. Ưu điểm của việc sử dụng cây khung nhỏ nhất (Minimum Spanning Tree) trong mạng máy tính là gì?
A. Tăng cường bảo mật mạng
B. Giảm chi phí xây dựng mạng bằng cách sử dụng số lượng kết nối tối thiểu
C. Tăng tốc độ truyền dữ liệu
D. Đảm bảo tất cả các máy tính đều được kết nối trực tiếp với nhau
23. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu đồ thị (graph)?
A. Quản lý danh sách liên hệ
B. Tìm đường đi trên bản đồ
C. Quản lý các tác vụ trong hệ điều hành
D. Lưu trữ lịch sử duyệt web
24. Ưu điểm của việc sử dụng ‘đệ quy’ trong lập trình là gì?
A. Luôn nhanh hơn so với vòng lặp
B. Giúp giải quyết các bài toán phức tạp một cách ngắn gọn và dễ hiểu
C. Tiết kiệm bộ nhớ
D. Dễ dàng gỡ lỗi hơn
25. Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n log n)
D. O(1)
26. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu hàng đợi (queue)?
A. Quản lý các cuộc gọi đến trong tổng đài
B. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức
C. Duyệt cây theo chiều sâu (DFS)
D. Tìm đường đi ngắn nhất trong đồ thị sử dụng thuật toán Dijkstra
27. Thuật toán nào sau đây được sử dụng để tìm chu trình Euler trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Fleury
D. Thuật toán Kruskal
28. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở giữa một cách hiệu quả?
A. Danh sách liên kết đơn (Singly Linked List)
B. Mảng (Array)
C. Hàng đợi (Queue)
D. Ngăn xếp (Stack)
29. Trong thuật toán tìm kiếm theo chiều sâu (DFS), cấu trúc dữ liệu nào sau đây được sử dụng?
A. Hàng đợi (Queue)
B. Cây (Tree)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
30. 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 trộn (Merge Sort)
31. Thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree) trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Ford-Fulkerson
C. Thuật toán Prim
D. Tìm kiếm theo chiều sâu (DFS)
32. Sắp xếp nhanh (Quick Sort) hoạt động tốt nhất trong trường hợp nào?
A. Khi dữ liệu đã được sắp xếp
B. Khi dữ liệu có nhiều phần tử trùng lặp
C. Khi dữ liệu được phân bố ngẫu nhiên
D. Khi dữ liệu có kích thước nhỏ
33. Trong cây đỏ-đen (red-black tree), tính chất nào sau đây luôn được duy trì?
A. Tất cả các nút đều có màu đỏ
B. Tất cả các đường đi từ gốc đến lá đều có số lượng nút đen như nhau
C. Tất cả các nút đen đều có hai nút con đỏ
D. Chiều cao của cây luôn là log n
34. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n)?
A. Duyệt cây theo thứ tự trước (Preorder Traversal)
B. Duyệt cây theo thứ tự sau (Postorder Traversal)
C. Tìm kiếm một phần tử (Search)
D. Duyệt cây theo thứ tự giữa (Inorder Traversal)
35. Ứng dụng thực tế của thuật toán sắp xếp topo (topological sort) là gì?
A. Tìm đường đi ngắn nhất
B. Lập lịch công việc với các phụ thuộc
C. Tìm cây khung nhỏ nhất
D. Sắp xếp dữ liệu số
36. Trong cấu trúc dữ liệu đồ thị (graph), một chu trình Euler là gì?
A. Đường đi ngắn nhất giữa hai đỉnh
B. Chu trình đi qua tất cả các đỉnh
C. Chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần
D. Cây khung của đồ thị
37. 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 không gian nhớ là yếu tố quan trọng
C. Khi cần duyệt tất cả các đỉnh
D. Khi biết trước độ sâu của giải pháp
38. Trong cây AVL, yếu tố cân bằng (balance factor) của một nút là gì?
A. Số lượng nút con của nút đó
B. Hiệu số giữa chiều cao của cây con trái và cây con phải
C. Tổng số nút trong cây con của nút đó
D. Giá trị của nút đó
39. Ứng dụng thực tế của cấu trúc dữ liệu Trie là gì?
A. Sắp xếp dữ liệu
B. Tìm kiếm đường đi ngắn nhất
C. Tự động hoàn thành (autocomplete) và kiểm tra chính tả
D. Nén dữ liệu
40. Ưu điểm chính của việc sử dụng bảng băm (hash table) là gì?
A. Duyệt theo thứ tự
B. Tìm kiếm, chèn và xóa phần tử nhanh chóng
C. Sắp xếp dữ liệu
D. Sử dụng bộ nhớ hiệu quả
41. Trong cây B, bậc của một nút là gì?
A. Số lượng nút con tối đa mà nút đó có thể có
B. Chiều cao của cây
C. Số lượng nút trong cây
D. Độ sâu của nút
42. Trong lập trình động (Dynamic Programming), kỹ thuật ghi nhớ (memoization) được sử dụng để làm gì?
A. Tối ưu hóa không gian nhớ
B. Lưu trữ kết quả của các bài toán con đã giải để tránh tính toán lại
C. Tăng độ phức tạp của thuật toán
D. Chia bài toán thành các bài toán con nhỏ hơn
43. Trong cấu trúc dữ liệu hàng đợi (queue), thao tác nào dùng để loại bỏ một phần tử khỏi hàng đợi?
A. Push
B. Pop
C. Enqueue
D. Dequeue
44. 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 gia đình?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Hàng đợi (Queue)
45. 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 cây khung nhỏ nhất
C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị
D. Sắp xếp các đỉnh của đồ thị
46. 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 đỉnh sẽ được duyệt?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
47. Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
48. Độ 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 xấu nhất là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
49. Trong cây nhị phân (Binary Tree), một nút có tối đa bao nhiêu nút con?
A. Không giới hạn
B. 1
C. 2
D. 3
50. Khi nào nên sử dụng danh sách liên kết đơn (singly linked list) thay vì danh sách liên kết đôi (doubly linked list)?
A. Khi cần duyệt danh sách theo cả hai chiều
B. Khi cần xóa một nút mà không cần biết nút trước đó
C. Khi không gian nhớ là yếu tố quan trọng
D. Khi cần chèn một nút vào giữa danh sách
51. Trong đồ thị, một thành phần liên thông mạnh (strongly connected component) là gì?
A. Một tập hợp các đỉnh mà giữa hai đỉnh bất kỳ đều có đường đi đến nhau
B. Một tập hợp các đỉnh có bậc cao nhất
C. Một tập hợp các đỉnh không có cạnh nối
D. Một tập hợp các đỉnh tạo thành một cây
52. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Ngăn xếp (Stack)
53. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
54. Kiểu dữ liệu trừu tượng (Abstract Data Type – ADT) là gì?
A. Một cách triển khai cụ thể của cấu trúc dữ liệu
B. Một giao diện định nghĩa các thao tác có thể thực hiện trên dữ liệu, không quan tâm đến việc triển khai
C. Một ngôn ngữ lập trình cụ thể
D. Một cấu trúc dữ liệu vật lý
55. Ưu điểm chính của việc sử dụng danh sách liên kết (linked list) so với mảng (array) là gì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi biết trước kích thước
C. Dễ dàng chèn và xóa phần tử
D. Tìm kiếm phần tử nhanh hơn
56. Cấu trúc dữ liệu nào sau đây có thể được sử dụng để triển khai hàng đợi ưu tiên (priority queue)?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Heap
D. Cây nhị phân tìm kiếm (Binary Search Tree)
57. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n)?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
58. Thuật toán nào sau đây được sử dụng để nén dữ liệu không mất mát (lossless data compression)?
A. JPEG
B. MPEG
C. Huffman coding
D. MP3
59. Giải thuật 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. 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)
60. Khi nào nên sử dụng sắp xếp chèn (Insertion Sort) thay vì sắp xếp trộn (Merge Sort)?
A. Khi cần sắp xếp một lượng lớn dữ liệu
B. Khi dữ liệu gần như đã được sắp xếp
C. Khi cần độ ổn định cao
D. Khi không gian nhớ là yếu tố quan trọng
61. Cấu trúc dữ liệu nào sau đây được sử dụng để triển khai thuật toán BFS (Breadth-First Search)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
62. Trong cây nhị phân tìm kiếm, thao tác nào sau đây có độ phức tạp 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)
63. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một từ có nằm trong từ điển hay không?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Bảng băm (Hash Table)
D. Ngăn xếp (Stack)
64. Khi nào nên sử dụng bảng băm (hash table) 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ự
B. Khi cần tìm kiếm phần tử nhanh chóng (trung bình O(1))
C. Khi cần duy trì các phần tử đã được sắp xếp
D. Khi số lượng phần tử rất nhỏ
65. 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 không gian tìm kiếm rất lớn và chiều sâu không giới hạn
C. Khi biết trước đích đến gần gốc
D. Khi đồ thị có trọng số âm
66. Phương pháp nào sau đây được sử dụng để chuyển đổi một cây tổng quát thành cây nhị phân?
A. Sử dụng danh sách liên kết
B. Sử dụng ma trận kề
C. Chuyển đổi ‘con trái, anh em ruột’ (left-child, right-sibling)
D. Sử dụng ngăn xếp
67. Trong một cây quyết định, mỗi nút lá đại diện cho điều gì?
A. Một thuộc tính để kiểm tra
B. Một quyết định hoặc kết quả
C. Một nút trung gian
D. Một đường đi
68. Ư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ì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước không xác định trước
C. Tìm kiếm phần tử nhanh hơn
D. Sắp xếp các phần tử nhanh hơn
69. 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ệ ‘cha-con’ trong một tổ chức?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Ngăn xếp (Stack)
70. Trong một đồ thị, chu trình Euler là gì?
A. Đường đi ngắn nhất giữa hai đỉnh
B. Đường đi thăm tất cả các đỉnh đúng một lần
C. Đường đi thăm tất cả các cạnh đúng một lần và quay lại đỉnh bắt đầu
D. Đường đi thăm tất cả các đỉnh và cạnh
71. Trong cây nhị phân, nút nào được gọi là ‘gốc’?
A. Nút có bậc cao nhất
B. Nút không có con
C. Nút không có cha
D. Nút có giá trị lớn nhất
72. Độ phức tạp thời gian để chèn một phần tử vào danh sách liên kết đơn (singly linked list) ở đầu danh sách là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
73. Ứng dụng nào sau đây không phù hợp với cấu trúc dữ liệu hàng đợi ưu tiên (priority queue)?
A. Lập lịch cho các tiến trình trong hệ điều hành
B. Tìm đường đi ngắn nhất trong đồ thị
C. Sắp xếp dữ liệu
D. Duyệt cây theo chiều rộng (BFS)
74. 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)?
A. Merge Sort
B. Heap Sort
C. Quick Sort
D. Insertion Sort
75. Độ phức tạp thời gian của thao tác ‘push’ trong ngăn xếp (stack) sử dụng mảng là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
76. Khi nào nên sử dụng lập trình động (dynamic programming)?
A. Khi bài toán có thể chia thành các bài toán con độc lập
B. Khi bài toán có cấu trúc con tối ưu và các bài toán con chồng chéo
C. Khi cần tìm tất cả các nghiệm của bài toán
D. Khi bài toán có thể giải quyết bằng thuật toán tham lam
77. 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, sắp xếp chúng và sau đó hợp nhất chúng lại?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
78. Thuật toán sắp xếp nào sau đây có độ phức tạp trung bình là O(n log n)?
A. Bubble Sort
B. Insertion Sort
C. Merge Sort
D. Selection Sort
79. Khi nào nên sử dụng thuật toán tham lam (greedy algorithm)?
A. Khi cần tìm nghiệm tối ưu toàn cục
B. Khi có thể chứng minh rằng lựa chọn cục bộ tối ưu dẫn đến nghiệm tối ưu toàn cục
C. Khi không gian tìm kiếm nhỏ
D. Khi cần tìm tất cả các nghiệm
80. Phương pháp nào sau đây được sử dụng để giải quyết xung đột trong bảng băm (hash table)?
A. Sắp xếp chèn (Insertion Sort)
B. Địa chỉ mở (Open addressing)
C. Tìm kiếm nhị phân (Binary Search)
D. Duyệt theo chiều rộng (Breadth-first search)
81. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là gì?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
82. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn đồ thị?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Ma trận kề (Adjacency matrix) hoặc danh sách kề (Adjacency list)
D. Ngăn xếp (Stack)
83. Trong thuật toán KMP (Knuth-Morris-Pratt), bảng tiền tố (prefix table) được sử dụng để làm gì?
A. Lưu trữ tất cả các tiền tố của mẫu
B. Lưu trữ độ dài của tiền tố dài nhất cũng là hậu tố của một tiền tố khác của mẫu
C. Lưu trữ tất cả các hậu tố của mẫu
D. Lưu trữ tần số xuất hiện của các ký tự trong mẫu
84. 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)?
A. Quick Sort
B. Counting Sort
C. Merge Sort
D. Insertion Sort
85. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở cả hai đầu một cách hiệu quả?
A. Hàng đợi ưu tiên (Priority queue)
B. Deque (Double-ended queue)
C. Ngăn xếp (Stack)
D. Danh sách liên kết đơn (Singly linked list)
86. Ứng dụng nào sau đây phù hợp nhất với hàng đợi (Queue)?
A. Quản lý các lệnh gọi hàm trong chương trình
B. In các tài liệu theo thứ tự gửi
C. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức
D. Lưu trữ lịch sử các trang web đã truy cập
87. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Cây (Tree)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
88. Trong một cây tìm kiếm nhị phân cân bằng, chiều cao của cây có mối quan hệ như thế nào với số lượng nút (n)?
A. Chiều cao tỉ lệ thuận với n
B. Chiều cao tỉ lệ thuận với log n
C. Chiều cao tỉ lệ thuận với n^2
D. Chiều cao không phụ thuộc vào n
89. Ưu điểm của việc sử dụng cây B so với cây nhị phân tìm kiếm thông thường là gì?
A. Thao tác tìm kiếm đơn giản hơn
B. Cây B luôn cân bằng hơn, giảm thiểu số lượng truy cập đĩa
C. Cây B sử dụng ít bộ nhớ hơn
D. Cây B dễ cài đặt hơn
90. 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?
A. Bubble Sort
B. Dijkstra
C. Binary Search
D. Insertion Sort
91. Độ phức tạp không gian của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
92. Hash table (bảng băm) giải quyết vấn đề xung đột bằng cách nào?
A. Loại bỏ các phần tử trùng lặp
B. Sử dụng hàm băm hoàn hảo
C. Sử dụng các kỹ thuật như chaining hoặc open addressing
D. Sắp xếp các phần tử trước khi băm
93. Trong bảng băm, kỹ thuật nào sau đây giúp giảm thiểu số lượng xung đột?
A. Sử dụng hàm băm đơn giản
B. Tăng kích thước của bảng băm
C. Giảm kích thước của bảng băm
D. Sử dụng một danh sách liên kết duy nhất cho tất cả các phần tử
94. Trong biểu đồ, 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 Prim
B. Thuật toán Kruskal
C. Thuật toán Dijkstra
D. Tìm kiếm theo chiều sâu (DFS)
95. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Cây (Tree)
C. Ngăn xếp (Stack)
D. Danh sách liên kết (Linked List)
96. Ưu điểm của việc sử dụng cây tìm kiếm cân bằng (ví dụ: cây AVL, cây đỏ-đen) so với cây nhị phân tìm kiếm thông thường là gì?
A. Dễ cài đặt hơn
B. Tiêu thụ í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
D. Duyệt nhanh hơn
97. Trong thuật toán Kruskal, cấu trúc dữ liệu nào đượ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. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Union-Find (Disjoint Set)
D. Cây nhị phân tìm kiếm (BST)
98. Độ phức tạp thời gian tốt nhất của thuật toán 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)
99. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra tính hợp lệ của dấu ngoặc trong một biểu thức?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
100. Thuật toán sắp xếp nào sau đây có hiệu suất tốt nhất trong trường hợp dữ liệu đã gần được sắp xếp?
A. Quick Sort
B. Merge Sort
C. Heap Sort
D. Insertion Sort
101. Khi nào nên sử dụng thuật toán Quick Sort thay vì Merge Sort?
A. Khi cần đảm bảo độ phức tạp thời gian O(n log n) trong mọi trường hợp
B. Khi bộ nhớ là yếu tố hạn chế
C. Khi dữ liệu đã gần được sắp xếp
D. Khi cần sắp xếp danh sách liên kết
102. Thuật toán nào sau đây thuộc loại ‘chia để trị’ (divide and conquer)?
A. Insertion Sort
B. Selection Sort
C. Bubble Sort
D. Merge Sort
103. Trong thuật toán Prim, cấu trúc dữ liệu nào thường được sử dụng để tìm cạnh có trọng số nhỏ nhất kết nối cây hiện tại với một đỉnh chưa thuộc cây?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Hàng đợi ưu tiên (Priority Queue)
D. Danh sách liên kết (Linked List)
104. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu hàng đợi (Queue)?
A. Quản lý lịch sử trình duyệt web
B. In ấn tài liệu
C. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức
D. Đánh giá biểu thức hậu tố (postfix)
105. Giải thuật sắp xếp nào sau đây không ổn định (unstable)?
A. Insertion Sort
B. Merge Sort
C. Bubble Sort
D. Heap Sort
106. Khi nào nên sử dụng danh sách liên kết kép (doubly linked list) thay vì danh sách liên kết đơn (singly linked list)?
A. Khi cần tiết kiệm bộ nhớ
B. Khi cần duyệt danh sách theo cả hai chiều
C. Khi cần chèn phần tử vào cuối danh sách
D. Khi cần tìm kiếm phần tử nhanh hơn
107. Trong cây nhị phân, thuật ngữ ‘lá’ (leaf) dùng để chỉ điều gì?
A. Nút gốc của cây
B. Nút có cả cây con trái và cây con phải
C. Nút không có cây con
D. Nút có giá trị lớn nhất
108. Trong cây nhị phân tìm kiếm (BST), 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 theo chiều rộng (BFS)
B. Duyệt theo chiều sâu (DFS)
C. Tìm kiếm một phần tử
D. Chèn một phần tử vào vị trí cuối cùng
109. 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)?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Đồ thị (Graph)
110. Ư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ì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước không xác định trước
C. Tìm kiếm phần tử nhanh hơn
D. Ít tốn bộ nhớ hơn
111. Thuật toán tìm kiếm nào sau đây có độ phức tạp thời gian O(n) trong trường hợp xấu nhất?
A. Tìm kiếm nhị phân (Binary Search)
B. Tìm kiếm tuyến tính (Linear Search)
C. Tìm kiếm theo chiều sâu (DFS)
D. Tìm kiếm theo chiều rộng (BFS)
112. 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) trong đồ thị?
A. Khi muốn tìm đường đi ngắn nhất
B. Khi không gian tìm kiếm rất lớn và chiều sâu có giới hạn
C. Khi đồ thị có trọng số
D. Khi muốn duyệt tất cả các đỉnh
113. Hàm băm (hash function) tốt cần có những đặc điểm gì?
A. Tính toán nhanh và phân phối đều các giá trị băm
B. Luôn trả về các giá trị băm duy nhất
C. Dễ bị đảo ngược
D. Phụ thuộc vào thứ tự của các phần tử đầu vào
114. Trong cây nhị phân tìm kiếm, phép duyệt nào sau đây cho phép in ra các nút theo thứ tự tăng dần?
A. Duyệt tiền thứ tự (preorder)
B. Duyệt trung thứ tự (inorder)
C. Duyệt hậu thứ tự (postorder)
D. Duyệt theo chiều rộng (BFS)
115. 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. Bubble Sort
B. Insertion Sort
C. Selection Sort
D. Merge Sort
116. Phương pháp nào sau đây thường được sử dụng để biểu diễn đồ thị trong bộ nhớ máy tính?
A. Mảng một chiều
B. Ma trận kề hoặc danh sách kề
C. Cây nhị phân
D. Bảng băm
117. 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, ví dụ như cây thư mục trong hệ điều hành?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Hàng đợi (Queue)
118. Trong cấu trúc dữ liệu, thao tác nào sau đây có độ phức tạp thời gian O(1) trong trường hợp tốt nhất đối với mảng?
A. Tìm kiếm một phần tử
B. Chèn một phần tử vào đầu mảng
C. Truy cập một phần tử tại vị trí đã biết
D. Xóa một phần tử khỏi mảng
119. Trong thuật toán tìm kiếm nhị phân, điều kiện tiên quyết để thuật toán hoạt động đúng là gì?
A. Dữ liệu phải được sắp xếp
B. Dữ liệu phải là số nguyên
C. Dữ liệu phải là duy nhất
D. Dữ liệu phải có kích thước nhỏ
120. 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. Hàng đợi ưu tiên (Priority Queue)
D. Danh sách liên kết (Linked List)
121. Phương pháp giải quyết xung đột nào sau đây thường được sử dụng trong bảng băm (hash table)?
A. Sắp xếp chèn (Insertion Sort)
B. Tìm kiếm nhị phân (Binary Search)
C. Liên kết riêng (Separate Chaining)
D. Đệ quy (Recursion)
122. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào sau đây có độ phức tạp thời gian O(h), với h là chiều cao của cây?
A. Duyệt cây theo thứ tự trước (Preorder Traversal)
B. Duyệt cây theo thứ tự sau (Postorder Traversal)
C. Tìm kiếm một phần tử
D. Duyệt cây theo thứ tự giữa (Inorder Traversal)
123. Trong cây B (B-tree), bậc của cây là gì?
A. Số lượng lá của cây
B. Chiều cao 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 trong cây
124. Thuật toán nào sau đây thường được sử dụng để tìm kiếm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Floyd-Warshall
D. Thuật toán Kruskal
125. 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?
A. Khi cần sắp xếp một lượng lớn dữ liệu
B. Khi dữ liệu đã gần như được sắp xếp
C. Khi cần đảm bảo độ phức tạp thời gian là O(n log n)
D. Khi cần sắp xếp dữ liệu trên ổ cứng
126. Trong thuật toán Kruskal, cấu trúc dữ liệu nào được sử dụng để kiểm tra xem hai đỉnh có thuộc cùng một tập hợp hay không?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cấu trúc tập hợp rời nhau (Disjoint Set Data Structure)
D. Bảng băm (Hash Table)
127. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) trong trường hợp tốt nhất là?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
128. Ưu điểm chính của việc sử dụng đồ thị biểu diễn bằng ma trận kề (adjacency matrix) là gì?
A. Tiết kiệm không gian bộ nhớ
B. Dễ dàng kiểm tra xem có cạnh nối giữa hai đỉnh hay không
C. Dễ dàng duyệt tất cả các đỉnh kề của một đỉnh
D. Dễ dàng thêm và xóa đỉnh
129. Cây nào sau đây đảm bảo thời gian tìm kiếm, chèn và xóa là O(log n) trong trường hợp xấu nhất?
A. Cây nhị phân tìm kiếm (Binary Search Tree)
B. Cây AVL
C. Cây tìm kiếm B (B-Tree)
D. Cây Huffman
130. 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?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Hàng đợi ưu tiên (Priority Queue)
D. Ngăn xếp (Stack)
131. Ưu điểm chính của việc sử dụng danh sách liên kết (linked list) so với mảng (array) là gì?
A. Truy cập ngẫu nhiên nhanh hơn
B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước đã biết trước
C. Dễ dàng chèn và xóa các phần tử
D. Tìm kiếm phần tử nhanh hơn
132. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai bộ nhớ cache?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Danh sách liên kết (Linked List)
D. Bảng băm (Hash Table)
133. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán Lempel-Ziv-Welch (LZW) để nén dữ liệu?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Bảng băm (Hash Table)
D. Ngăn xếp (Stack)
134. 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 đỉnh sẽ được duyệt?
A. Ngăn xếp (Stack)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Danh sách liên kết (Linked List)
135. Khi nào thì việc sử dụng bảng băm (hash table) trở nên kém hiệu quả?
A. Khi số lượng phần tử trong bảng nhỏ
B. Khi hàm băm phân phối các khóa đều
C. Khi có quá nhiều xung đột
D. Khi cần tìm kiếm phần tử nhỏ nhất
136. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n)?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
137. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc LIFO (Last In, First Out)?
A. Hàng đợi (Queue)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Ngăn xếp (Stack)
138. Cấu trúc dữ liệu nào sau đây hỗ trợ cả thao tác FIFO (First In, First Out) và LIFO (Last In, First Out)?
A. Mảng (Array)
B. Hàng đợi hai đầu (Deque)
C. Ngăn xếp (Stack)
D. Danh sách liên kết đơn (Singly Linked List)
139. 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. Bảng băm (Hash Table)
D. Hàng đợi ưu tiên (Priority Queue)
140. Trong thuật toán tìm kiếm A* (A star), hàm heuristic được sử dụng để làm gì?
A. Đảm bảo thuật toán luôn tìm thấy đường đi ngắn nhất
B. Ước tính chi phí từ một đỉnh đến đỉnh đích
C. Lưu trữ các đỉnh đã được duyệt
D. Sắp xếp các đỉnh theo thứ tự ưu tiên
141. 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 đoạn con, sắp xếp các đoạn con này, sau đó hợp nhất chúng lại?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp chọn (Selection Sort)
142. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều sâu (DFS) trên đồ thị biểu diễn bằng danh sách kề là?
A. O(V + E)
B. O(V log V)
C. O(V)
D. O(E)
143. Trong cây nhị phân đầy đủ (full binary tree), số lượng nút lá (leaf nodes) luôn như thế nào so với số lượng nút có ít nhất một con?
A. Ít hơn 1
B. Bằng nhau
C. Nhiều hơn 1
D. Nhiều hơn 2
144. Trong thuật toán Prim, mục đích chính là gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh
B. Tìm cây bao trùm tối thiểu của một đồ thị
C. Tìm chu trình Euler trong một đồ thị
D. Sắp xếp các đỉnh của một đồ thị theo thứ tự topo
145. Thuật toán nào sau đây có thể được sử dụng để tìm chu trình ngắn nhất trong một đồ thị có trọng số âm?
A. Thuật toán Dijkstra
B. Thuật toán Prim
C. Thuật toán Bellman-Ford
D. Thuật toán Kruskal
146. Loại cấu trúc dữ liệu nào phù hợp nhất cho việc kiểm tra xem một dấu ngoặc trong biểu thức toán học đã được đóng đúng cách hay chưa?
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)
147. 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 xấu nhất?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp trộn (Merge Sort)
D. Sắp xếp nhanh (Quick Sort)
148. Độ phức tạp thời gian của thao tác tìm kiếm trong bảng băm (hash table) trong trường hợp trung bình là?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
149. 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 hệ thống phân cấp?
A. Mảng (Array)
B. Hàng đợi (Queue)
C. Cây (Tree)
D. Bảng băm (Hash Table)
150. Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
