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

1. Trong thuật toán tìm kiếm theo chiều sâu (DFS) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để quản lý các nút cần được thăm?

A. Queue

B. Stack

C. Priority Queue

D. Hash Table

2. Độ phức tạp thời gian tốt nhất, trung bình và xấu nhất của thuật toán Insertion Sort lần lượt là:

A. O(n), O(n log n), O(n^2)

B. O(1), O(log n), O(n)

C. O(n), O(n^2), O(n^2)

D. O(log n), O(n log n), O(n^2)

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

C. Merge Sort

D. Selection Sort

4. Trong cây tìm kiếm nhị phân, thao tác `in-order traversal` (duyệt trung thứ tự) sẽ cho ra kết quả gì?

A. Các nút được duyệt theo thứ tự mức

B. Các nút được duyệt theo thứ tự giảm dần

C. Các nút được duyệt theo thứ tự tăng dần

D. Thứ tự duyệt không xác định

5. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong một mảng đã được sắp xếp bằng thuật toán tìm kiếm nhị phân là bao nhiêu?

A. O(n)

B. O(1)

C. O(log n)

D. O(n log n)

6. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở đầu và cuối với độ phức tạp O(1)?

A. Mảng

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

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

D. Stack

7. Giải thuật nào sau đây là một ví dụ của kỹ thuật `chia để trị` (divide and conquer)?

A. Linear Search

B. Bubble Sort

C. Merge Sort

D. Insertion Sort

8. Kiểu duyệt cây nào sau đây duyệt các nút theo chiều rộng, từng mức một?

A. Pre-order

B. In-order

C. Post-order

D. Breadth-First Search (BFS)

9. Trong bảng băm (hash table), `xung đột` xảy ra khi nào?

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

B. Khi hai khóa khác nhau được băm thành cùng một chỉ số

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

D. Khi hàm băm không hiệu quả

10. Cấu trúc dữ liệu nào sau đây là `phi tuyến tính`?

A. Mảng

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

C. Stack

D. Cây

11. Giải thuật Floyd-Warshall được sử dụng để giải quyết bài toán nào?

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

B. Tìm cây khung nhỏ nhất của đồ thị

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

D. Kiểm tra xem đồ thị có chu trình âm hay không

12. Trong bảng băm, kích thước bảng băm (số lượng vị trí) nên được chọn như thế nào để giảm thiểu xung đột?

A. Luôn chọn kích thước là lũy thừa của 2

B. Chọn kích thước là số nguyên tố lớn

C. Chọn kích thước nhỏ nhất có thể để tiết kiệm bộ nhớ

D. Kích thước không ảnh hưởng đến số lượng xung đột

13. Kiểu duyệt cây nào sau đây thường được sử dụng để sao chép cây?

A. Pre-order

B. In-order

C. Post-order

D. Level-order (BFS)

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

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

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

15. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào được sử dụng để theo dõi khoảng cách ngắn nhất hiện tại từ nút nguồn đến tất cả các nút khác?

A. Stack

B. Queue

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

D. Linked List

16. Phương pháp nào sau đây thường được sử dụng để giải quyết xung đột trong bảng băm?

A. Sắp xếp tuyến tính

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

C. Liên kết riêng (Separate Chaining)

D. Duyệt theo chiều rộng

17. Ưu điểm của việc sử dụng cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) so với cây tìm kiếm nhị phân thông thường là gì?

A. Cân bằng giúp giảm độ phức tạp không gian

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

C. Cân bằng giúp đơn giản hóa việc triển khai

D. Cân bằng luôn cho phép duyệt cây nhanh hơn

18. Trong thuật toán QuickSort, việc chọn phần tử chốt (pivot) ảnh hưởng đến điều gì?

A. Độ phức tạp không gian của thuật toán

B. Độ phức tạp thời gian trung bình và xấu nhất của thuật toán

C. Tính ổn định của thuật toán

D. Khả năng song song hóa của thuật toán

19. Trong cấu trúc dữ liệu đồ thị, ma trận kề (adjacency matrix) phù hợp nhất cho việc biểu diễn đồ thị nào?

A. Đồ thị thưa (sparse graph)

B. Đồ thị dày đặc (dense graph)

C. Đồ thị có số lượng đỉnh lớn

D. Đồ thị vô hướng

20. Thuật toán Bellman-Ford được sử dụng để giải bài toán đường đi ngắn nhất nguồn đơn trong đồ thị có đặc điểm gì?

A. Chỉ áp dụng cho đồ thị vô hướng

B. Chỉ áp dụng cho đồ thị không có chu trình

C. Có thể xử lý đồ thị có cạnh trọng số âm

D. Hiệu quả hơn Dijkstra trên đồ thị không có chu trình

21. Trong cấu trúc dữ liệu Stack, thao tác nào sau đây tuân theo nguyên tắc LIFO (Last-In, First-Out)?

A. Enqueue

B. Dequeue

C. Push

D. Peek

22. Độ phức tạp thời gian để chèn một phần tử vào vị trí đầu của 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 log n)

23. Cho một mảng số nguyên chưa sắp xếp. Để tìm phần tử lớn thứ k trong mảng, giải thuật nào sau đây hiệu quả nhất về mặt thời gian (trung bình)?

A. Sắp xếp toàn bộ mảng rồi lấy phần tử thứ k

B. Sử dụng thuật toán QuickSelect

C. Duyệt mảng k lần để tìm phần tử lớn nhất, lớn nhì,...

D. Sử dụng Heap Sort để sắp xếp k phần tử lớn nhất

24. Thuật toán sắp xếp nào sau đây hoạt động tốt nhất với dữ liệu đã gần như được sắp xếp?

A. Quick Sort

B. Merge Sort

C. Insertion Sort

D. Selection Sort

25. 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 (Đống)

D. Stack

26. Độ phức tạp không gian của thuật toán Merge Sort là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

27. Thuật toán Kruskal và Prim đều được sử dụng để giải quyết bài toán nào trên đồ thị?

A. Tìm đường đi ngắn nhất

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST)

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

D. Tìm chu trình Euler

28. Trong đồ thị, chu trình Euler tồn tại khi nào?

A. Khi đồ thị là đồ thị đầy đủ

B. Khi tất cả các đỉnh của đồ thị có bậc chẵn

C. Khi đồ thị là cây

D. Khi đồ thị có ít nhất một đỉnh bậc lẻ

29. Cấu trúc dữ liệu nào sau đây hoạt động tốt nhất cho việc biểu diễn mối quan hệ `cha-con` trong một hệ thống phân cấp?

A. Mảng

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

C. Cây

D. Hàng đợi

30. Thuật toán sắp xếp nào sau đây là một ví dụ của thuật toán `tham lam` (greedy algorithm)?

A. Quick Sort

B. Merge Sort

C. Selection Sort

D. Insertion Sort