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

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

A. Khi mảng có kích thước lớn

B. Khi mảng gần như đã được sắp xếp

C. Khi cần sắp xếp dữ liệu một cách ngẫu nhiên

D. Khi cần sắp xếp dữ liệu có nhiều phần tử trùng lặp

2. Cây khung nhỏ nhất (Minimum Spanning Tree) của một đồ thị là gì?

A. Một cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là lớn nhất

B. Một cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất

C. Một cây bao gồm một số đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất

D. Một đồ thị con liên thông không chứa chu trình

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

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

C. Heap

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

4. Khi nào nên sử dụng cấu trúc dữ liệu Trie?

A. Khi cần lưu trữ dữ liệu số

B. Khi cần tìm kiếm các chuỗi có tiền tố chung

C. Khi cần sắp xếp dữ liệu

D. Khi cần lưu trữ dữ liệu theo thứ tự ưu tiên

5. Độ phức tạp không gian của thuật toán sắp xếp trộn (merge sort) là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

6. 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. Queue

B. Stack

C. Linked List

D. Tree

7. 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. Mảng (Array)

C. Ngăn xếp (Stack)

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

8. Sự khác biệt chính giữa thuật toán tham lam (Greedy algorithm) và quy hoạch động (Dynamic programming) là gì?

A. Thuật toán tham lam luôn tìm ra nghiệm tối ưu

B. Quy hoạch động luôn tìm ra nghiệm tối ưu

C. Thuật toán tham lam đưa ra quyết định dựa trên thông tin cục bộ, trong khi quy hoạch động xem xét tất cả các khả năng

D. Quy hoạch động nhanh hơn thuật toán tham lam

9. Cho một mảng đã được sắp xếp, thuật toán nào sau đây hiệu quả nhất để tìm kiếm một phần tử?

A. Tìm kiếm tuyến tính

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

C. Tìm kiếm theo chiều rộng

D. Tìm kiếm theo chiều sâu

10. 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. Tìm kiếm

B. Chèn

C. Xóa

D. Tất cả các đáp án trên

11. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình tốt nhất?

A. Bubble Sort

B. Selection Sort

C. Merge Sort

D. Insertion Sort

12. Trong thuật toán tìm kiếm theo chiều sâu (DFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các đỉnh sẽ được duyệt?

A. Queue

B. Stack

C. Linked List

D. Heap

13. Giải thuật 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 đỉnh trong đồ thị

B. Tìm tất cả các cặp đường đi ngắn nhất trong đồ thị

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

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

14. Cho một đồ thị có hướng, thuật toán nào sau đây được sử dụng để tìm các thành phần liên thông mạnh (strongly connected components)?

A. Dijkstra's algorithm

B. Prim's algorithm

C. Kruskal's algorithm

D. Tarjan's algorithm

15. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử đầu tiên và cuối cùng trong 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 đôi

D. Ngăn xếp

16. Giải thuật Dijkstra thường được sử dụng để giải quyết vấn đề nào?

A. Tìm kiếm một phần tử trong mảng

B. Sắp xếp một danh sách các số

C. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị

D. Nén dữ liệu

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

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

18. 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 nút đều có màu đen

C. Đường đi từ gốc đến mọi nút lá có số lượng nút đen như nhau

D. Đường đi từ gốc đến mọi nút lá có số lượng nút đỏ như nhau

19. Độ phức tạp thời gian của thao tác chèn vào heap là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

20. Khi nào nên sử dụng thuật toán quy hoạch độ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 một nghiệm gần đúng trong thời gian ngắn

D. Khi dữ liệu đầu vào có kích thước nhỏ

21. Độ 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 xấu nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(n log n)

22. Độ phức tạp không gian của thuật toán sắp xếp nhanh (quick sort) trong trường hợp trung bình là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

23. 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. Merge Sort

B. Heap Sort

C. Quick Sort

D. Insertion Sort

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

B. Queue

C. Linked List

D. Tree

25. Ưu điểm của việc sử dụng bảng băm (hash table) so với cây tìm kiếm là gì?

A. Bảng băm luôn sử dụng ít bộ nhớ hơn

B. Bảng băm có thể duy trì thứ tự của các phần tử

C. Bảng băm có thời gian truy cập trung bình nhanh hơn

D. Bảng băm có thể xử lý các khóa trùng lặp

26. Kỹ thuật 'chia để trị' (Divide and Conquer) thường được sử dụng trong thuật toán nào sau đây?

A. Bubble Sort

B. Linear Search

C. Merge Sort

D. Insertion Sort

27. Ư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ử dễ dàng hơn

28. Hashing được sử dụng chủ yếu cho mục đích gì?

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

B. Tìm kiếm dữ liệu nhanh chóng

C. Nén dữ liệu

D. Mã hóa dữ liệu

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

A. Heap Sort

B. Quick Sort

C. Selection Sort

D. Insertion Sort

30. 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 Trie

D. Cây Heap