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

1. Thuật toán nào sau đây không thuộc nhóm thuật toán sắp xếp so sánh (comparison sort)?

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

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

C. Sắp xếp đếm (Counting Sort)

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

2. Thuật toán tìm kiếm nào sau đây có thể hoạt động trên dữ liệu chưa được sắp xếp?

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

B. Tìm kiếm tuyến tính (Linear Search)

C. Tìm kiếm nội suy (Interpolation Search)

D. Tìm kiếm bước nhảy (Jump Search)

3. Độ 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) trong một mảng đã sắp xếp là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

4. Khi nào thì việc sử dụng danh sách liên kết đôi (Doubly Linked List) được ưu tiên hơn danh sách liên kết đơn (Singly Linked List)?

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

B. Khi chỉ cần duyệt danh sách theo một chiều

C. Khi cần duyệt danh sách theo cả hai chiều hoặc xóa nút nhanh chóng

D. Khi số lượng nút rất lớn

5. 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 phần tử

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

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

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

C. Heap (Đống)

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

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

8. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian ổn định (stable sort)?

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

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

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

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

9. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất là O(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 đếm (Counting Sort)

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

10. Trong đồ thị (Graph), ma trận kề (Adjacency Matrix) phù hợp nhất để biểu diễn đồ thị nào?

A. Đồ thị thưa (Sparse Graph)

B. Đồ thị dày đặc (Dense Graph)

C. Cây (Tree)

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

11. Phương pháp xử lý xung đột phổ biến nhất trong bảng băm (Hash Table) là gì?

A. Sắp xếp lại bảng băm

B. Tăng kích thước bảng băm

C. Xử lý xung đột bằng danh sách liên kết (Separate Chaining)

D. Giảm hàm băm

12. 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, ví dụ như cây thư mục trong hệ điều hành?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Cây (Tree)

D. Bảng băm (Hash Table)

13. Trong thuật toán sắp xếp trộn (Merge Sort), quá trình `trộn` (merge) hai mảng con đã sắp xếp có độ phức tạp thời gian là bao nhiêu?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n^2)

14. Trong cấu trúc dữ liệu đồ thị (Graph), thuật toán nào sau đây đượ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. Tìm kiếm theo chiều rộng (BFS)

B. Tìm kiếm theo chiều sâu (DFS)

C. Thuật toán Dijkstra

D. Thuật toán Prim

15. Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

16. 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)?

A. Khi cần tìm đường đi ngắn nhất

B. Khi không gian tìm kiếm rất rộng và sâu

C. Khi cần duyệt tất cả các nút theo mức

D. Khi cần tìm kiếm trên đồ thị vô hướng

17. Phương pháp tiếp cận `chia để trị` (Divide and Conquer) được sử dụng trong thuật toán sắp xếp nào sau đây?

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)

18. Trong các cấu trúc dữ liệu sau, cấu trúc 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)

19. Cấu trúc dữ liệu nào sau đây KHÔNG phải là cấu trúc dữ liệu tuyến tính?

A. Mảng (Array)

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

C. Cây (Tree)

D. Hàng đợi (Queue)

20. Ư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 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 dữ liệu cố định

C. Dễ dàng chèn và xóa phần tử ở đầu hoặc giữa danh sách

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

21. Ưu điểm của việc sử dụng đồ thị (Graph) so với cây (Tree) là gì?

A. Dễ dàng duyệt qua tất cả các nút hơn

B. Biểu diễn mối quan hệ phức tạp hơn, không chỉ phân cấp

C. Tìm kiếm đường đi ngắn nhất hiệu quả hơn

D. Sử dụng ít bộ nhớ hơn

22. Cấu trúc dữ liệu nào thường được sử dụng để kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức toán học?

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)

23. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ tập hợp các đỉnh chưa được thăm và khoảng cách hiện tại từ đỉnh nguồn?

A. Mảng (Array)

B. Ngăn xếp (Stack)

C. Hàng đợi ưu tiên (Priority Queue)

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

24. Trong bảng băm (Hash Table), `xung đột` (collision) xảy ra khi nào?

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

B. Khi hai khóa khác nhau được băm đến cùng một vị trí

C. Khi khóa không tồn tại trong bảng

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

25. Ứ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 trong hệ điều hành

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

D. Đảo ngược chuỗi

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 một đồ thị liên thông có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Kruskal

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

27. 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 (Array)

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 (Stack)

28. Trong cây nhị phân cân bằng (Balanced Binary Tree), chiều cao của cây được giới hạn bởi độ phức tạp nào so với số lượng nút (n)?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(sqrt(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 coi là hiệu quả nhất cho mảng lớ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)

30. Bảng băm (Hash Table) hoạt động hiệu quả nhất khi nào?

A. Khi có quá nhiều phần tử trùng lặp

B. Khi cần truy cập tuần tự các phần tử

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

D. Khi số lượng phần tử rất nhỏ