Đề 15 – 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 sắp xếp nào sau đây có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?

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

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

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

D. Sắp xếp Shell (Shell Sort)

2. Giải thuật nào sau đây có thể được sử dụng để phát hiện chu trình trong đồ thị có hướng?

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

3. Ứng dụng của thuật toán sắp xếp tô pô (Topological Sort) là:

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

B. Phát hiện chu trình trong đồ thị

C. Lập lịch công việc phụ thuộc

D. Tìm cây khung nhỏ nhất

4. Thuật toán sắp xếp nào sau đây ổn định (stable)?

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

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

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

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

5. Ư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ử 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. Dễ dàng cài đặt hơn

6. Cấu trúc dữ liệu nào sau đây 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)

7. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) trong trường hợp dữ liệu đã được sắp xếp một phần hoặc gần như sắp xếp là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

8. 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ố dương?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Prim

D. Thuật toán Kruskal

9. Điểm khác biệt chính giữa thuật toán BFS và DFS trong duyệt đồ thị là gì?

A. BFS nhanh hơn DFS

B. BFS sử dụng hàng đợi, DFS sử dụng ngăn xếp

C. DFS luôn tìm được đường đi ngắn nhất

D. BFS không thể duyệt đồ thị có chu trình

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

C. Hàng đợi (Queue)

D. Cây (Tree)

11. Độ phức tạp không gian của thuật toán tìm kiếm nhị phân (Binary Search) là:

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

12. 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 (Searching for a node)

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

13. Cây AVL và cây đỏ đen (Red-Black Tree) là các loại cây:

A. Cây nhị phân không cân bằng

B. Cây nhị phân tìm kiếm cân bằng

C. Cây đa phân

D. Cây khung

14. 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 (Queue)

B. Ngăn xếp (Stack)

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

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

15. Giải thuật tìm kiếm theo chiều sâu (Depth-First Search - DFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần duyệt?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Mảng (Array)

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

16. Tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất trên loại dữ liệu nào?

A. Dữ liệu không có thứ tự

B. Dữ liệu đã được sắp xếp

C. Dữ liệu động

D. Dữ liệu có kích thước lớn

17. Ưu điểm của việc sử dụng danh sách liên kết đôi (Doubly Linked List) so với danh sách liên kết đơn (Singly Linked List) là gì?

A. Tiết kiệm bộ nhớ hơn

B. Duyệt ngược danh sách dễ dàng hơn

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

D. Cài đặt đơn giản hơn

18. Cấu trúc dữ liệu nào thích hợp nhất để biểu diễn 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. Hàng đợi (Queue)

19. Giải thuật quy hoạch động (Dynamic Programming) thường được áp dụng để giải quyết loại bài toán nào?

A. Bài toán sắp xếp

B. Bài toán tối ưu hóa

C. Bài toán tìm kiếm

D. Bài toán duyệt đồ thị

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

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 Prim hoặc Kruskal

D. Thuật toán sắp xếp tô pô (Topological Sort)

21. Thuật toán nào sau đây có độ phức tạp thời gian trung bình là O(n log n)?

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

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

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

D. Sắp xếp chèn (Insertion Sort)

22. Độ 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à:

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

23. Giải thuật nào sau đây thuộc loại `chia để trị` (Divide and Conquer)?

A. Sắp xếp chèn (Insertion Sort)

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

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

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

24. Ứng dụng phổ biến của hàng đợi (Queue) trong khoa học máy tính là gì?

A. Quản lý ngăn xếp lệnh gọi hàm

B. Xử lý tác vụ theo thứ tự đến trước phục vụ trước (FIFO)

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

D. Lưu trữ dữ liệu phân cấp

25. Trong bảng băm (Hash Table), phương pháp xử lý xung đột `dây chuyền` (chaining) sử dụng cấu trúc dữ liệu nào?

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

26. Trong bảng băm (Hash Table), `xung đột` (collision) xảy ra khi:

A. Bảng băm đầy

B. Hai khóa khác nhau băm ra cùng một chỉ số

C. Khóa không tồn tại trong bảng băm

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

27. Giải thuật nào sau đây là giải thuật tham lam (Greedy algorithm)?

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

B. Thuật toán Dijkstra tìm đường đi ngắn nhất

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

D. Quy hoạch động (Dynamic Programming)

28. Trong thuật toán sắp xếp vun đống (Heap Sort), quá trình `vun đống` (heapify) có vai trò gì?

A. Sắp xếp mảng đầu vào

B. Xây dựng vun đống từ mảng đầu vào

C. Tìm kiếm phần tử lớn nhất trong mảng

D. Chia mảng thành các phần nhỏ hơn

29. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt hàng đợi ưu tiên (Priority Queue)?

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. Vun đống (Heap)

30. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là:

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)