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

1. Độ phức tạp thời gian của phép toán tìm kiếm trong bảng băm (hash table) trung bình là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

2. Khi so sánh giữa mảng (Array) và danh sách liên kết (Linked List) về mặt bộ nhớ, phát biểu nào sau đây thường đúng?

A. Mảng luôn sử dụng bộ nhớ hiệu quả hơn danh sách liên kết

B. Danh sách liên kết luôn sử dụng bộ nhớ hiệu quả hơn mảng

C. Mảng có thể lãng phí bộ nhớ nếu kích thước khai báo quá lớn so với dữ liệu thực tế

D. Danh sách liên kết không bao giờ lãng phí bộ nhớ

3. Cấu trúc dữ liệu nào thường được sử dụng để cài đặt thuật toán BFS (Breadth-First Search)?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây nhị phân (Binary Tree)

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

4. Trong cây nhị phân đầy đủ (Full Binary Tree), mỗi nút (trừ lá) có bao nhiêu nút con?

A. 0

B. 1

C. 2

D. Tùy ý

5. Khi nào thì 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 danh sách nhanh hơn

B. Khi cần duyệt danh sách theo cả hai chiều (từ đầu đến cuối và ngược lại)

C. Khi cần tiết kiệm bộ nhớ

D. Khi số lượng phần tử trong danh sách rất lớn

6. Độ phức tạp thời gian tốt nhất của giải thuật sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

7. Giải thuật sắp xếp nào có độ phức tạp thời gian trung bình và trường hợp tốt nhất 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 nhanh (Quick Sort)

D. Sắp xếp chọn (Selection Sort)

8. Trong cây nhị phân tìm kiếm, thao tác tìm kiếm một nút có độ phức tạp thời gian trung bình là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

9. Thuật toán nào sau đây tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Bellman-Ford

C. Thuật toán Floyd-Warshall

D. Thuật toán Prim

10. Cấu trúc dữ liệu nào thường được sử dụng để cài đặt 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 đôi (Doubly Linked List)

D. Cây tìm kiếm nhị phân (Binary Search Tree)

11. Giải thuật nào sau đây thường được sử dụng để tìm kiếm đường đi trong mê cung?

A. Sắp xếp nổi bọt (Bubble Sort)

B. Tìm kiếm nhị phân (Binary Search)

C. Tìm kiếm theo chiều sâu (Depth-First Search - DFS)

D. Sắp xếp trộn (Merge Sort)

12. Cấu trúc dữ liệu 'vun đống' (heap) thường được sử dụng để cài đặt giải thuật sắp xếp nào?

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 vun đống (Heap Sort)

D. Sắp xếp nhanh (Quick Sort)

13. Cấu trúc dữ liệu nào thích hợp nhất để kiểm tra xem một từ có tồn tại trong một tập hợp lớn các từ hay không, với hiệu suất cao?

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. Bảng băm (Hash Table)

14. Giải thuật sắp xếp nào có độ phức tạp thời gian trung bình tốt nhất trong số các giải thuật sắp xếp so sánh?

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 vun đống (Heap Sort)

D. Sắp xếp cơ số (Radix Sort)

15. Cấu trúc dữ liệu nào sau đây là 'phi tuyến tính' (non-linear)?

A. Mảng (Array)

B. Ngăn xếp (Stack)

C. Hàng đợi (Queue)

D. Đồ thị (Graph)

16. Ưu điểm chính của danh sách liên kết (Linked List) so với mảng (Array) là gì?

A. Truy cập phần tử nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn cho dữ liệu có kích thước cố định

C. Kích thước có thể thay đổi động

D. Tìm kiếm phần tử nhanh hơn

17. Giải thuật nào sau đây có thể phát hiện chu trình âm trong đồ thị có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Prim

C. Thuật toán Kruskal

D. Thuật toán Bellman-Ford

18. Trong cây khung nhỏ nhất (Minimum Spanning Tree), mục tiêu chính là gì?

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

B. Kết nối tất cả các đỉnh trong đồ thị với tổng trọng số cạnh nhỏ nhất

C. Tìm chu trình ngắn nhất trong đồ thị

D. Phân hoạch đồ thị thành các thành phần liên thông

19. Cấu trúc dữ liệu nào cho phép truy cập ngẫu nhiên (random access) các phần tử với độ phức tạp thời gian O(1)?

A. Danh sách liên kết đơn (Singly Linked List)

B. Danh sách liên kết đôi (Doubly Linked List)

C. Mảng (Array)

D. Hàng đợi (Queue)

20. Giải thuật tìm đường đi ngắn nhất nào thường được sử dụng cho đồ thị có trọng số không âm?

A. Thuật toán Floyd-Warshall

B. Thuật toán Bellman-Ford

C. Thuật toán Dijkstra

D. Thuật toán tìm kiếm theo chiều sâu (DFS)

21. 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. Ngăn xếp (Stack)

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

D. Cây nhị phân (Binary Tree)

22. Giải thuật nào sau đây là một ví dụ của giải 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 nhanh (Quick Sort)

D. Sắp xếp chọn (Selection Sort)

23. Trong cây nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree), mục đích của việc cân bằng cây là gì?

A. Giảm độ phức tạp bộ nhớ

B. Tăng tốc độ duyệt cây theo thứ tự trước

C. Đảm bảo độ phức tạp thời gian tìm kiếm, chèn, xóa là O(log n)

D. Đơn giản hóa việc cài đặt

24. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ 'cha-con' trong hệ thống phân cấp?

A. Mảng (Array)

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

C. Cây (Tree)

D. Đồ thị (Graph)

25. Thao tác nào sau đây không phải là thao tác cơ bản trên cấu trúc dữ liệu hàng đợi (Queue)?

A. Enqueue (Thêm vào cuối)

B. Dequeue (Lấy ra khỏi đầu)

C. Peek (Xem phần tử đầu)

D. Pop (Lấy ra khỏi đỉnh)

26. Giải thuật sắp xếp nào thường được sử dụng trong thư viện chuẩn của nhiều ngôn ngữ lập trình vì tính hiệu quả cao trong thực 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 nhanh (Quick Sort)

D. Sắp xếp chọn (Selection Sort)

27. Giải thuật sắp xếp nào có độ phức tạp thời gian luôn là O(n^2) trong mọi trường hợp?

A. Sắp xếp nhanh (Quick Sort)

B. Sắp xếp trộn (Merge Sort)

C. Sắp xếp chọn (Selection Sort)

D. Sắp xếp vun đống (Heap Sort)

28. Trong đồ thị, thuật ngữ 'bậc của đỉnh' (degree of a vertex) dùng để chỉ điều gì?

A. Số đỉnh trong đồ thị

B. Số cạnh trong đồ thị

C. Số cạnh liên kết với đỉnh đó

D. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác

29. Hàm băm (hash function) tốt cần đáp ứng tính chất nào sau đây?

A. Luôn tạo ra giá trị băm giống nhau cho các đầu vào khác nhau

B. Tạo ra ít xung đột (collision) nhất có thể

C. Luôn tạo ra giá trị băm khác nhau cho các đầu vào giống nhau

D. Độ phức tạp tính toán cao

30. Giải thuật tìm kiếm nào hoạt động hiệu quả nhất trên dữ liệu đã được sắp xếp?

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)