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

1. Ứng dụng phổ biến của hàng đợi (Queue) là gì?

A. Quản lý bộ nhớ.

B. Xử lý cuộc gọi trong tổng đài điện thoại.

C. Đánh giá biểu thức số học.

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

2. Trong đồ thị (Graph), 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 còn lại trong đồ thị có trọng số không âm?

A. Tìm kiếm theo chiều rộng (Breadth-First Search)

B. Tìm kiếm theo chiều sâu (Depth-First Search)

C. Thuật toán Dijkstra

D. Thuật toán Prim

3. Kỹ thuật '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 chèn (Insertion Sort)

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

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

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

4. Giải thuật tìm kiếm nào sau đây hoạt động hiệu quả nhất trên dữ liệu đã được sắp xếp?

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 rộng (Breadth-First Search)

D. Tìm kiếm theo chiều sâu (Depth-First Search)

5. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt qua mảng, phần tử nào sẽ được đặt đúng vị trí cuối cùng?

A. Phần tử nhỏ nhất.

B. Phần tử lớn nhất.

C. Phần tử ở giữa.

D. Không có phần tử nào chắc chắn được đặt đúng vị trí.

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

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

B. Đồ thị dày (Dense graph).

C. Cả đồ thị thưa và đồ thị dày đều phù hợp.

D. Không phù hợp với bất kỳ loại đồ thị nào.

7. Khi nào thì thuật toán sắp xếp nhanh (Quick Sort) hoạt động kém hiệu quả nhất?

A. Khi dữ liệu đã được sắp xếp hoặc gần sắp xếp.

B. Khi dữ liệu có kích thước lớn.

C. Khi dữ liệu chứa nhiều phần tử trùng lặp.

D. Khi bộ nhớ không đủ.

8. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để quản lý các đỉnh cần thăm?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

9. Hạn chế chính của việc sử dụng cây nhị phân tìm kiếm (Binary Search Tree) là gì?

A. Khó cài đặt.

B. Không hiệu quả với dữ liệu lớn.

C. Có thể trở nên mất cân bằng, dẫn đến độ phức tạp thời gian xấu nhất là O(n).

D. Chỉ hoạt động với dữ liệu số.

10. Trong cây, duyệt theo thứ tự giữa (In-order traversal) thường được sử dụng để làm gì trong cây nhị phân tìm kiếm?

A. Sao chép cây.

B. Xóa cây.

C. In ra các phần tử của cây theo thứ tự tăng dần.

D. Tìm kiếm phần tử lớn nhất.

11. Độ 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à bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

12. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt chức năng 'undo' trong các ứng dụng phần mềm?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

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

13. Trong cây nhị phân tìm kiếm, 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 (Search)

D. Sắp xếp các nút theo thứ tự tăng dần (In-order traversal to get sorted elements)

14. Cấu trúc dữ liệu nào sau đây sử dụng hàm băm (hash function) để ánh xạ khóa tới giá trị?

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

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

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

D. Hàng đợi (Queue)

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

16. Độ phức tạp thời gian của thao tác thêm một phần tử vào đầu danh sách liên kết đơn (singly linked list) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

17. Phương pháp lập trình độ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ìm kiếm.

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

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

18. 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ố?

A. Thuật toán Dijkstra

B. Thuật toán Prim

C. Thuật toán Floyd-Warshall

D. Tìm kiếm theo chiều rộng (Breadth-First Search)

19. Ư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 số lượng phần tử cố định.

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.

20. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình và xấu nhất đều là O(n log n)?

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

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

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

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

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

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Prim

D. Tìm kiếm theo chiều sâu (Depth-First Search)

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à bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

23. Trong biểu đồ Big O, O(1) biểu thị độ phức tạp thời gian như thế nào?

A. Tuyến tính.

B. Logarit.

C. Hằng số.

D. Bậc hai.

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

25. Cấu trúc dữ liệu nào thích hợp nhất để 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. Heap (Đống)

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

26. Thuật toán nào sau đây thuộc loại 'tham lam' (Greedy)?

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

B. Thuật toán Dijkstra

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

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

27. Trong cây AVL, thao tác cân bằng cây (tree balancing) được thực hiện khi nào?

A. Sau mỗi thao tác tìm kiếm.

B. Sau mỗi thao tác chèn hoặc xóa nút.

C. Khi cây trở nên quá lớn.

D. Không cần thực hiện thao tác cân bằng cây.

28. Thuật toán sắp xếp nào sau đây hoạt động dựa trên việc so sánh và đổi chỗ các phần tử lân cận nếu chúng không đúng thứ tự?

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

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

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

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

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

30. Khi nào thì nên sử dụng danh sách liên kết đôi (Doubly Linked List) thay vì danh sách liên kết đơn (Singly Linked List)?

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

B. Khi cần duyệt danh sách theo cả hai chiều (từ đầu đến cuối và từ cuối lên đầu).

C. Khi cần truy cập phần tử ở giữa danh sách nhanh hơn.

D. Khi cần sắp xếp danh sách nhanh hơn.