Đề 14 – 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 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 heap (Heap Sort)

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

2. Cấu trúc dữ liệu nào cho phép truy cập ngẫu nhiên 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)

3. Thuật toán 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. Mảng không sắp xếp

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

C. Mảng đã sắp xếp

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

4. Trong bảng băm (Hash Table), `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 vào cùng một vị trí

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

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

5. Ưu điểm chính của cây AVL so với cây nhị phân tìm kiếm (Binary Search Tree) thông thường là gì?

A. Thao tác chèn và xóa nhanh hơn

B. Luôn đảm bảo cây cân bằng, tránh trường hợp suy biến thành danh sách

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

D. Dễ dàng cài đặt hơn

6. Khi nào thì việc sử dụng đệ quy (recursion) trong giải thuật có thể không hiệu quả và nên tránh?

A. Khi bài toán có thể giải quyết hiệu quả hơn bằng vòng lặp (iteration)

B. Khi độ sâu đệ quy quá lớn, dẫn đến tràn stack (stack overflow)

C. Khi cần tối ưu hóa độ phức tạp không gian

D. Tất cả các đáp án trên

7. Cấu trúc dữ liệu nào thường được dùng để biểu diễn 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. Mảng (Array)

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

C. Cây (Tree)

D. Đồ thị (Graph)

8. Độ phức tạp thời gian trung bình để tìm kiếm trong bảng băm (Hash Table) là bao nhiêu, giả sử phân bố băm đều và xử lý collision hiệu quả?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

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

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

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

B. Thay đổi hàm băm

C. Chaining (Liên kết) hoặc Open Addressing (Địa chỉ mở)

D. Xóa các phần tử gây ra collision

11. 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ụ: `(){}[]`)?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

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

12. Trong thuật toán Kruskal, mục đích chính là gì?

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

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị

C. Tìm chu trình Euler

D. Sắp xếp đồ thị theo thứ tự topological

13. Trong cây nhị phân tìm kiếm, phép duyệt `in-order` sẽ cho ra kết quả các nút theo thứ tự nào?

A. Thứ tự trước (Pre-order)

B. Thứ tự sau (Post-order)

C. Thứ tự tăng dần của giá trị khóa

D. Thứ tự giảm dần của giá trị khóa

14. Trong thuật toán sắp xếp nhanh (Quick Sort), `pivot` (phần tử chốt) được sử dụng để làm gì?

A. Xác định phần tử nhỏ nhất trong mảng

B. Chia mảng thành hai phần: các phần tử nhỏ hơn pivot và lớn hơn pivot

C. Tìm vị trí trung tâm của mảng

D. Đếm số lượng phần tử trong mảng

15. Thuật toán Dijkstra đượ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 tất cả các cặp đỉnh trong đồ thị

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

C. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm

D. Tìm chu trình Hamilton

16. Thuật toán Prim được sử dụng để làm gì?

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

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị

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

D. Sắp xếp topological đồ thị

17. Cây đỏ-đen (Red-Black Tree) là một ví dụ của loại cây nào?

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

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

C. Cây quyết định

D. Cây Trie

18. Độ 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) là gì?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

19. Thuật toán DFS (Depth-First Search) trong đồ thị 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. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Heap (Đống)

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

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

21. Trong cấu trúc dữ liệu đồ thị (Graph), `chu trình` (cycle) là gì?

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

B. Đường đi bắt đầu và kết thúc tại cùng một đỉnh, đi qua ít nhất một cạnh

C. Tập hợp các cạnh nối tất cả các đỉnh

D. Thứ tự duyệt các đỉnh theo chiều rộng

22. Thuật toán Floyd-Warshall giải quyết bài toán nào?

A. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác

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

C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có thể có trọng số âm

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

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

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

D. Sắp xếp phần tử dễ dàng hơn

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

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

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

27. Trong đồ thị (Graph), thuật toán BFS (Breadth-First Search) thường được sử dụng để làm gì?

A. Tìm đường đi ngắn nhất trong đồ thị có trọng số dương

B. Tìm chu trình âm

C. Tìm đường đi ngắn nhất trong đồ thị không trọng số

D. Sắp xếp các đỉnh theo thứ tự topological

28. Thuật toán nào sau đây thuộc loại `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 trộn (Merge Sort)

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

29. Cấu trúc dữ liệu Trie (cây tiền tố) thường được ứng dụng trong trường hợp nào?

A. Sắp xếp số lượng lớn các số nguyên

B. Tìm kiếm xâu tiền tố (prefix) hiệu quả

C. Nén dữ liệu

D. Mô hình hóa quan hệ đồ thị

30. Trong cấu trúc dữ liệu, thuật ngữ `ADT` thường được dùng để chỉ điều gì?

A. Kiểu dữ liệu trừu tượng (Abstract Data Type)

B. Kiểu dữ liệu thích ứng (Adaptive Data Type)

C. Kiểu dữ liệu ứng dụng (Applied Data Type)

D. Kiểu dữ liệu tăng cường (Augmented Data Type)