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

1. Trong ngữ cảnh của cấu trúc dữ liệu đồ thị, 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à không có đường đi giữa chúng

B. Một tập hợp các cạnh mà tạo thành một chu trình

C. Một tập hợp các đỉnh mà từ bất kỳ đỉnh nào trong tập hợp, có thể đến bất kỳ đỉnh nào khác trong tập hợp

D. Một tập hợp các đỉnh mà có đường đi đến tất cả các đỉnh khác trong đồ thị

2. Trong ngữ cảnh của lập trình động, kỹ thuật ghi nhớ (memoization) là gì?

A. Một kỹ thuật để tối ưu hóa việc sử dụng bộ nhớ

B. Một kỹ thuật để lưu trữ kết quả của các cuộc gọi hàm tốn kém và trả về kết quả đã lưu khi đầu vào tương tự xảy ra lại

C. Một kỹ thuật để gỡ lỗi mã

D. Một kỹ thuật để tăng độ phức tạp của thuật toán

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

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

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

B. Tìm cây bao trùm nhỏ nhất trong một đồ thị

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

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

5. Trong ngữ cảnh của thuật toán, 'tham lam' (greedy) có nghĩa là gì?

A. Chọn giải pháp tối ưu toàn cục

B. Chọn giải pháp tốt nhất hiện tại mà không quan tâm đến hậu quả trong tương lai

C. Tìm kiếm tất cả các giải pháp có thể

D. Sử dụng bộ nhớ hiệu quả nhất

6. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn quan hệ 'cha-con'?

A. Hàng đợi

B. Ngăn xếp

C. Cây

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

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

C. Dễ dàng chèn và xóa các phần tử

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

8. Độ 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^2)

9. Thuật toán nào sau đây được sử dụng để tìm cây bao trùm nhỏ nhất (minimum spanning tree) trong một đồ thị?

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 Kruskal

D. Thuật toán sắp xếp nổi bọt (Bubble Sort)

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

A. Tìm cây bao trùm nhỏ nhất

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

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

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

11. Ưu điểm chính 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. Độ phức tạp thời gian tốt hơn trong trường hợp xấu nhất

B. Duy trì thứ tự của các phần tử

C. Thời gian truy cập trung bình nhanh hơn

D. Sử dụng bộ nhớ hiệu quả hơn

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

A. Sắp xếp chèn

B. Sắp xếp nổi bọt

C. Sắp xếp nhanh

D. Sắp xếp chọn

13. Cây Trie (cây tiền tố) được sử dụng hiệu quả nhất cho việc gì?

A. Sắp xếp số

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

C. Biểu diễn đồ thị

D. Tính toán số học

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

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

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

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

D. Tìm kiếm một chuỗi con trong một chuỗi

15. Tìm kiếm theo chiều rộng (BFS) sử dụng cấu trúc dữ liệu nào sau đây?

A. Ngăn xếp

B. Hàng đợi

C. Cây

D. Đồ thị

16. Độ phức tạp thời gian của thao tác xóa một phần tử khỏi đầu một danh sách liên kết đơn là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

17. Trong ngữ cảnh của đồ thị, chu trình Euler là gì?

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

B. Một đường đi đ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. Độ phức tạp thời gian của thao tác tìm kiếm trong cây tìm kiếm nhị phân cân bằng (ví dụ: cây AVL, cây đỏ-đen) là bao nhiêu trong trường hợp xấu nhất?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(1)

19. Độ phức tạp thời gian để tìm kiếm nhị phân trong một mảng đã được sắp xếp là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

20. Kỹ thuật 'backtracking' thường được sử dụng để giải quyết loại vấn đề nào?

A. Vấn đề tối ưu hóa

B. Vấn đề tìm kiếm

C. Vấn đề sắp xếp

D. Vấn đề nén dữ liệu

21. Cấu trúc dữ liệu nào sau đây phù hợp nhất để triển khai chức năng 'undo' trong một trình soạn thảo văn bản?

A. Hàng đợi

B. Ngăn xếp

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

D. Cây

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

B. Ngăn xếp

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

D. Cây

23. Thuật toán nào sau đây sử dụng chiến lược 'chia để trị'?

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

B. Sắp xếp nổi bọt

C. Sắp xếp trộn

D. Sắp xếp chèn

24. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc FIFO (First In, First Out)?

A. Ngăn xếp

B. Hàng đợi

C. Cây

D. Đồ thị

25. Độ phức tạp thời gian của thao tác tìm kiếm trong một cây băm (B-tree) là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

26. Thuật toán Bellman-Ford được sử dụng để giải quyết vấn đề nào sau đây?

A. Tìm cây bao trùm nhỏ nhất

B. Tìm đường đi ngắn nhất trong đồ thị có trọng số âm

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

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

27. Ưu điểm chính của việc sử dụng cây đỏ-đen so với cây tìm kiếm nhị phân thông thường là gì?

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

B. Tìm kiếm nhanh hơn trong mọi trường hợp

C. Đảm bảo độ phức tạp thời gian O(log n) cho các thao tác

D. Ít tốn bộ nhớ hơn

28. 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. Heap

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

29. Độ phức tạp thời gian của thao tác chèn vào một bảng băm (hash table) với độ phân giải xung đột bằng phương pháp xích là bao nhiêu trong trường hợp xấu nhất?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

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

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

C. Ngăn xếp

D. Cây