Đề 5 – Đề thi, câu hỏi trắc nghiệm online Cấu trúc dữ liệu và giải thuật

1. Trong thuật toán KMP (Knuth-Morris-Pratt), bảng tiền xử lý (prefix table) được sử dụng để làm gì?

A. Để lưu trữ các ký tự của mẫu

B. Để lưu trữ vị trí của các ký tự trong văn bản

C. Để tránh so sánh lại các ký tự đã khớp khi có sự không khớp

D. Để sắp xếp các ký tự của mẫu

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

A. Mảng

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

C. Danh sách liên kết kép

D. Hàng đợi

3. Hash table giải quyết xung đột (collision) bằng phương pháp nào sau đây?

A. Sắp xếp lại các phần tử

B. Xóa các phần tử trùng lặp

C. Sử dụng hàm băm khác

D. Chaining hoặc Open Addressing

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

A. Array

B. Stack

C. Linked List

D. Queue

5. Giải thuật Bellman-Ford được sử dụng để giải quyết vấn đề nào?

A. Tìm đường đi ngắn nhất giữa hai nút trong đồ thị có cạnh âm

B. Tìm cây khung nhỏ nhất

C. Sắp xếp một mảng

D. Tìm luồng cực đại trong mạng

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

A. Tìm đường đi ngắn nhất giữa hai nút

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)

C. Sắp xếp một mảng

D. Tìm luồng cực đại trong mạng

7. Ư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 xác định trước

C. Tìm kiếm nhanh hơn

D. Dễ dàng sắp xếp hơn

8. 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 của cây

B. Giảm kích thước của cây và tránh overfitting

C. Tăng độ phức tạp của cây

D. Cân bằng cây

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

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

10. Cấu trúc dữ liệu nào thường được sử dụng để triển khai hàng đợi ưu tiên (Priority Queue)?

A. Stack

B. Queue

C. Heap

D. Linked List

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

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

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

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

13. Cấu trúc dữ liệu Trie được sử dụng để làm gì?

A. Sắp xếp dữ liệu

B. Lưu trữ và tìm kiếm chuỗi

C. Lưu trữ số nguyên

D. Lưu trữ đồ thị

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

A. Tìm đường đi ngắn nhất giữa hai nút

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)

C. Sắp xếp một mảng

D. Tìm luồng cực đại trong mạng

15. Độ 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)

16. Cấu trúc dữ liệu nào sau đây thích hợp nhất để kiểm tra xem một dấu ngoặc đóng có khớp với dấu ngoặc mở tương ứng hay không?

A. Queue

B. Stack

C. Linked List

D. Tree

17. Kỹ thuật quay lui (Backtracking) thường được sử dụng để giải quyết các bài toán nào?

A. Bài toán tìm kiếm đường đi ngắn nhất

B. Bài toán tối ưu hóa

C. Bài toán liệt kê tất cả các cấu hình thỏa mãn điều kiện

D. Bài toán sắp xếp

18. Trong đồ 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 không có cạnh lặp lại

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

A. Tìm đường đi ngắn nhất

B. Tìm cây khung nhỏ nhất

C. Tìm luồng cực đại trong mạng

D. Sắp xếp các nút

20. Điểm khác biệt chính giữa Breadth-First Search (BFS) và Depth-First Search (DFS) là gì?

A. BFS sử dụng stack, DFS sử dụng queue

B. BFS duyệt theo chiều rộng, DFS duyệt theo chiều sâu

C. BFS nhanh hơn DFS

D. DFS luôn tìm thấy đường đi ngắn nhất

21. Cây tìm kiếm nhị phân (Binary Search Tree) có tính chất nào sau đây?

A. Tất cả các nút bên trái lớn hơn nút gốc

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

C. Nút gốc lớn hơn tất cả các nút con

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

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

A. Queue

B. Stack

C. Linked List

D. Tree

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

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

24. 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. Stack

B. Queue

C. Priority Queue

D. Linked List

25. Thuật toán nào sau đây là một thuật toán chia để trị (Divide and Conquer)?

A. Insertion Sort

B. Bubble Sort

C. Merge Sort

D. Selection Sort

26. Phương pháp tiếp cận 'tham lam' (Greedy) thường được sử dụng trong các bài toán nào?

A. Tìm kiếm đường đi ngắn nhất

B. Tối ưu hóa cục bộ với hy vọng đạt được tối ưu toàn cục

C. Sắp xếp dữ liệu

D. Tìm kiếm trong cây

27. Thuật toán Floyd-Warshall được sử dụng để giải quyết vấn đề nào?

A. Tìm đường đi ngắn nhất giữa hai nút

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 nút

D. Sắp xếp một mảng

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

A. Binary Search Tree

B. AVL Tree

C. Complete Binary Tree

D. Binary Tree

29. Trong lập trình động (Dynamic Programming), kỹ thuật memoization dùng để làm gì?

A. Tối ưu hóa việc sử dụng bộ 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. Chia bài toán thành các bài toán con nhỏ hơn

D. Sắp xếp dữ liệu đầu vào

30. Trong cây đỏ đen (Red-Black Tree), mục đích của việc sử dụng màu đỏ và đen cho các nút là gì?

A. Để dễ dàng phân biệt các nút

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

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

D. Để giảm dung lượng bộ nhớ