Đề 7 – Đề thi, câu hỏi 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 sau đây phù hợp nhất để 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 tìm kiếm nhị phân (Binary Search Tree)

2. Trong cây tìm kiếm nhị phân tự cân bằng (ví dụ: AVL tree), thao tác nào sau đây được sử dụng để duy trì tính cân bằng của cây sau khi chèn hoặc xóa một nút?

A. Sắp xếp (Sorting)

B. Băm (Hashing)

C. Xoay (Rotation)

D. Tìm kiếm (Searching)

3. Độ phức tạp thời gian của thao tác tìm kiếm trong cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) là bao nhiêu trong trường hợp xấu nhất?

A. O(n)

B. O(1)

C. O(log n)

D. O(n^2)

4. Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong mảng đã được sắp xếp một cách hiệu quả nhất?

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

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

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

D. Tìm kiếm theo chiều rộng (BFS)

5. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp?

A. Mảng (Array)

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

C. Cây (Tree)

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

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

A. O(n)

B. O(n^2)

C. O(log n)

D. O(n log n)

7. Thuật toán nào sau đây là một thuật toán tham lam (Greedy algorithm)?

A. Thuật toán Bellman-Ford

B. Thuật toán Dijkstra

C. Thuật toán Floyd-Warshall

D. Lập trình động (Dynamic Programming)

8. Thuật toán nào sau đây được sử dụng để tìm cây bao trùm tối thiểu (Minimum Spanning Tree) trong một đồ thị có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Ford-Fulkerson

C. Thuật toán Kruskal

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

9. Cho một mảng đã được sắp xếp, thuật toán nào sau đây có độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử?

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

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

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

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

10. Thuật toán nào sau đây có độ phức tạp thời gian trung bình tốt nhất để sắp xếp một mảng?

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 nhanh (Quick Sort)

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

11. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một từ có tồn tại trong một tập hợp lớn các từ hay không?

A. Mảng (Array)

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

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

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

12. Trong bảng băm (Hash Table), điều gì xảy ra khi hai khóa khác nhau băm đến cùng một vị trí?

A. Xảy ra lỗi

B. Ghi đè giá trị cũ

C. Xảy ra xung đột (Collision)

D. Tự động tăng kích thước bảng

13. Trong lập trình động (Dynamic Programming), kỹ thuật nào sau đây được sử dụng để lưu trữ kết quả của các bài toán con để tránh tính toán lại?

A. Đệ quy (Recursion)

B. Tham lam (Greedy)

C. Ghi nhớ (Memoization)

D. Chia để trị (Divide and Conquer)

14. Thuật toán nào sau đây được sử dụng để giải quyết bài toán đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có trọng số?

A. Thuật toán Dijkstra

B. Thuật toán Bellman-Ford

C. Thuật toán Floyd-Warshall

D. Thuật toán Prim

15. Cấu trúc dữ liệu nào sau đây hỗ trợ thao tác thêm và xóa phần tử ở cả hai đầu một cách hiệu quả?

A. Mảng (Array)

B. Hàng đợi (Queue)

C. Deque (Double-ended queue)

D. Ngăn xếp (Stack)

16. Trong cấu trúc dữ liệu đồ thị, thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác?

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 Dijkstra

D. Thuật toán sắp xếp tô pô

17. 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. Danh sách liên kết (Linked List)

C. Ngăn xếp (Stack)

D. Cây (Tree)

18. Trong cấu trúc dữ liệu đồ thị, một đồ thị vô hướng liên thông là gì?

A. Đồ thị không có cạnh

B. Đồ thị có một chu trình Euler

C. Đồ thị trong đó có một đường đi giữa mọi cặp đỉnh

D. Đồ thị không có chu trình

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

B. O(n)

C. O(1)

D. O(n^2)

20. Trong lập trình động (Dynamic Programming), phương pháp nào sau đây bắt đầu giải quyết bài toán từ các bài toán con nhỏ nhất và xây dựng dần lên lời giải cho bài toán lớn hơn?

A. Top-down (Memoization)

B. Bottom-up (Tabulation)

C. Divide and Conquer

D. Greedy

21. Ư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 ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn

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

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

22. Cấu trúc dữ liệu nào sau đây cho phép truy cập các phần tử một cách ngẫu nhiên với độ phức tạp thời gian O(1)?

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

B. Hàng đợi (Queue)

C. Mảng (Array)

D. Ngăn xếp (Stack)

23. Cấu trúc dữ liệu nào sau đây phù hợp nhất để lưu trữ lịch sử các thao tác để có thể hoàn tác (undo) chúng?

A. Hàng đợi (Queue)

B. Mảng (Array)

C. Ngăn xếp (Stack)

D. Cây (Tree)

24. Độ phức tạp thời gian của thao tác chèn (insertion) trong bảng băm (Hash Table) trong trường hợp tốt nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

25. Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng (BFS) trong đồ thị là bao nhiêu?

A. O(V + E)

B. O(V * E)

C. O(V)

D. O(E)

26. Trong cây tìm kiếm nhị phân, thứ tự duyệt nào sau đây cho phép in ra các nút theo thứ tự tăng dần?

A. Pre-order

B. Post-order

C. In-order

D. Level-order

27. Trong một đồ thị có trọng số, cây bao trùm tối thiểu (Minimum Spanning Tree - MST) là gì?

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

B. Tập hợp tất cả các cạnh trong đồ thị

C. Cây bao gồm tất cả các đỉnh với tổng trọng số cạnh là nhỏ nhất

D. Chu trình có tổng trọng số cạnh là nhỏ nhất

28. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều sâu (DFS) một cách hiệu quả?

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)

29. Thuật toán nào sau đây sử dụng chiến lược 'chia để trị'?

A. Tìm kiếm tuyến tính

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)

30. Thuật toán nào sau đây được sử dụng để phát hiện chu trình trong một đồ thị có hướng?

A. Thuật toán Dijkstra

B. Thuật toán Prim

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

D. Tìm kiếm theo chiều rộng (BFS)