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

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

A. Mảng

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

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

D. Ngăn xếp

2. Ứng dụng phổ biến nhất của hàng đợi (Queue) là gì?

A. Quản lý bộ nhớ

B. Lập lịch CPU

C. Tính toán biểu thức số học

D. Tìm kiếm đường đi trong đồ thị

3. Hàm băm (hash function) lý tưởng nên có tính chất nào sau đây?

A. Dễ dàng đảo ngược để lấy lại khóa gốc

B. Tạo ra các giá trị băm trùng lặp cho các khóa khác nhau

C. Phân phối đều các khóa vào các ô băm

D. Luôn tạo ra giá trị băm giống nhau cho cùng một khóa

4. 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 muốn tìm tất cả các đỉnh có thể đạt được từ đỉnh nguồn

C. Khi không gian tìm kiếm rất rộng và có thể có đường đi sâu

D. Khi đồ thị là đồ thị vô hướng

5. Độ phức tạp thời gian nào sau đây thường được coi là hiệu quả nhất cho một thuật toán?

A. O(n^2)

B. O(log n)

C. O(n!)

D. O(2^n)

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

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

7. Thuật toán duyệt đồ thị theo chiều rộng (BFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần thăm?

A. Ngăn xếp

B. Hàng đợi

C. Cây nhị phân

D. Mảng

8. 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 không gian

B. Tăng tốc độ duyệt cây

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

9. 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 (Pre-order traversal)

B. Duyệt cây theo thứ tự sau (Post-order traversal)

C. Tìm kiếm một nút

D. Duyệt cây theo chiều rộng (Breadth-first traversal)

10. 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)

11. Khi nào nên sử dụng danh sách liên kết thay vì mảng?

A. Khi cần truy cập ngẫu nhiên nhanh chóng

B. Khi kích thước dữ liệu không cố định và thường xuyên thay đổi

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

D. Khi cần thực hiện các phép toán số học trên dữ liệu

12. Khi nào thuật toán sắp xếp chèn (Insertion Sort) hoạt động hiệu quả hơn so với sắp xếp nhanh (Quick Sort)?

A. Khi dữ liệu đầu vào rất lớn

B. Khi dữ liệu đầu vào đã gần như được sắp xếp

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

D. Khi cần sắp xếp dữ liệu số thực

13. Trong cây nhị phân tìm kiếm, thao tác xóa một nút có hai con phức tạp hơn xóa nút lá hoặc nút có một con. Vì sao?

A. Cần phải cân bằng lại cây sau khi xóa

B. Cần tìm nút thay thế phù hợp để duy trì tính chất cây nhị phân tìm kiếm

C. Phải duyệt toàn bộ cây để tìm nút cần xóa

D. Không thể xóa nút có hai con trong cây nhị phân tìm kiếm

14. Độ 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 log n)

15. Trong đồ thị, thuật toán nào được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm?

A. Thuật toán duyệt theo chiều sâu (DFS)

B. Thuật toán duyệt theo chiều rộng (BFS)

C. Thuật toán Dijkstra

D. Thuật toán Prim

16. Ưu điểm của việc sử dụng bảng băm (hash table) là gì?

A. Duyệt các phần tử theo thứ tự sắp xếp

B. Tìm kiếm, chèn, xóa phần tử với độ phức tạp trung bình O(1)

C. Lưu trữ dữ liệu có thứ tự

D. Đảm bảo không có xung đột băm

17. Thuật toán nào sau đây là một ví dụ của phương pháp `chia để trị` (divide and conquer)?

A. Sắp xếp chèn

B. Sắp xếp chọn

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

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

18. Thuật toán sắp xếp nào có độ phức tạp thời gian tốt nhất trong trường hợp dữ liệu đã gần như được sắp xếp?

A. Sắp xếp nhanh

B. Sắp xếp trộn

C. Sắp xếp chèn

D. Sắp xếp chọn

19. Cấu trúc dữ liệu nào cho phép truy cập phần tử đầu tiên và cuối cùng, thêm và xóa ở cả hai đầu một cách hiệu quả?

A. Ngăn xếp

B. Hàng đợi

C. Deque (hàng đợi hai đầu)

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

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

21. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm (hash table) là O(1), nhưng trong trường hợp xấu nhất có thể lên đến O(n). Trường hợp xấu nhất này xảy ra khi nào?

A. Khi bảng băm đầy

B. Khi hàm băm phân phối đều các khóa

C. Khi tất cả các khóa băm vào cùng một ô (xung đột băm)

D. Khi bảng băm có kích thước quá nhỏ

22. Trong thuật toán sắp xếp nhanh (Quick Sort), việc lựa chọn phần tử chốt (pivot) ảnh hưởng như thế nào đến hiệu suất của thuật toán?

A. Không ảnh hưởng, Quick Sort luôn có độ phức tạp O(n log n)

B. Chọn chốt tốt giúp giảm độ phức tạp không gian

C. Chọn chốt không tốt (ví dụ luôn chọn phần tử đầu tiên trên mảng đã sắp xếp) có thể dẫn đến độ phức tạp O(n^2)

D. Chọn chốt ngẫu nhiên luôn đảm bảo độ phức tạp tốt nhất

23. Trong thuật toán tìm kiếm nhị phân, dữ liệu đầu vào cần phải có tính chất gì?

A. Đã được sắp xếp

B. Chưa sắp xếp

C. Chỉ chứa số nguyên

D. Chỉ chứa chuỗi ký tự

24. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp trộn (Merge Sort) là bao nhiêu?

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(log n)

25. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ `một-nhiều` giữa các phần tử?

A. Mảng

B. Hàng đợi

C. Cây

D. Ngăn xếp

26. Thuật toán nào sau đây được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree) trong đồ thị?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Kruskal

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

27. Cấu trúc dữ liệu `đồ thị` (Graph) được sử dụng để mô hình hóa loại quan hệ nào giữa các đối tượng?

A. Quan hệ phân cấp `cha-con`

B. Quan hệ tuyến tính `trước-sau`

C. Quan hệ `nhiều-nhiều` hoặc quan hệ phức tạp, không thứ bậc

D. Quan hệ `một-nhiều` có thứ tự

28. Cấu trúc dữ liệu nào phù hợp nhất để kiểm tra xem một chuỗi ngoặc có hợp lệ hay không (ví dụ `()[]{}` là hợp lệ, `([)]` là không hợp lệ)?

A. Hàng đợi

B. Ngăn xếp

C. Mảng

D. Cây nhị phân

29. 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) và thường được sử dụng 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)

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

A. Truy cập phần tử ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước thay đổi

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

D. Sắp xếp phần tử nhanh hơn