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

1. 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 (Binary Tree)

2. Hash table (Bảng băm) giải quyết vấn đề xung đột (collision) bằng cách nào?

A. Luôn tăng kích thước bảng băm

B. Sử dụng hàm băm hoàn hảo

C. Sử dụng các kỹ thuật như separate chaining hoặc open addressing

D. Loại bỏ các phần tử trùng lặp

3. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp trung bình?

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)

4. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt undo/redo trong các ứng dụng chỉnh sửa văn bản?

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)

5. Thuật toán sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự?

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

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

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

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

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

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

7. Trong cài đặt danh sách liên kết đôi (Doubly Linked List), mỗi nút có bao nhiêu con trỏ (pointers)?

A. Một

B. Hai

C. Ba

D. Không có con trỏ nào

8. Đồ thị vô hướng liên thông có bao nhiêu cạnh tối thiểu để đảm bảo tính liên thông (với n đỉnh)?

A. n - 2

B. n - 1

C. n

D. n + 1

9. Kiểu duyệt đồ thị nào sử dụng hàng đợi (Queue) như cấu trúc dữ liệu phụ trợ?

A. Duyệt theo chiều sâu (DFS - Depth First Search)

B. Duyệt theo chiều rộng (BFS - Breadth First Search)

C. Duyệt tiền thứ tự (Pre-order Traversal)

D. Duyệt hậu thứ tự (Post-order Traversal)

10. Trong thuật toán tô màu đồ thị (Graph Coloring), mục tiêu chính là gì?

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

B. Tìm chu trình Euler trong đồ thị

C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau có cùng màu

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

11. 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 (Linked List)

B. Hàng đợi (Queue)

C. Mảng (Array)

D. Ngăn xếp (Stack)

12. Độ phức tạp thời gian trung bình của thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp là bao nhiêu?

A. O(n)

B. O(n^2)

C. O(log n)

D. O(1)

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

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

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

C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

D. Sắp xếp đồ thị tô pô (Topological Sort)

14. Giải thuật nào sau đây là ví dụ của giải thuật '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)

15. Thuật toán Kruskal đượ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 đỉnh

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

C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

D. Sắp xếp đồ thị tô pô (Topological Sort)

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

17. Ưu điểm chính của việc sử dụng cây nhị phân tìm kiếm (Binary Search Tree) so với mảng đã sắp xếp là gì khi thực hiện chèn và xóa?

A. Tìm kiếm nhanh hơn

B. Chèn và xóa nhanh hơn

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

D. Dễ dàng duyệt qua tất cả các phần tử hơn

18. Cấu trúc dữ liệu cây nào đảm bảo thời gian tìm kiếm, chèn và xóa trung bình là O(log n) trong trường hợp xấu nhất?

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

B. Cây AVL

C. Cây Heap

D. Cây Trie

19. Thuật toán sắp xếp nào có độ phức tạp thời gian trung bình và trường hợp xấu nhất đều là O(n log n)?

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

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

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

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

20. Trong cây nhị phân tìm kiếm (Binary Search Tree), khi duyệt theo thứ tự giữa (in-order traversal), các nút được thăm theo thứ tự nào?

A. Từ gốc đến lá

B. Theo thứ tự tăng dần của khóa

C. Theo thứ tự giảm dần của khóa

D. Ngẫu nhiên

21. 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. Hàng đợi (Queue)

C. Cây (Tree)

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

22. Trong cấu trúc dữ liệu đồ thị (Graph), điều gì được dùng để biểu diễn mối quan hệ giữa các đỉnh?

A. Mảng (Array)

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

C. Cạnh (Edge)

D. Ngăn xếp (Stack)

23. Trong biểu diễn đồ thị bằng danh sách kề (Adjacency List), mỗi đỉnh sẽ lưu trữ danh sách các gì?

A. Tất cả các đỉnh khác trong đồ thị

B. Các đỉnh không kề với nó

C. Các đỉnh kề với nó

D. Trọng số của tất cả các cạnh

24. Kỹ thuật 'memoization' thường được sử dụng trong phương pháp lập trình nào để tối ưu hiệu suất?

A. Tham lam (Greedy)

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

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

D. Quay lui (Backtracking)

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

B. O(n log n)

C. O(n^2)

D. O(1)

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

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

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

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

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

27. Khi nào thì thuật toán tìm kiếm tuyến tính (Linear Search) hiệu quả hơn thuật toán tìm kiếm nhị phân (Binary Search)?

A. Khi mảng đã được sắp xếp

B. Khi mảng có kích thước lớn

C. Khi mảng chưa được sắp xếp hoặc kích thước nhỏ

D. Không bao giờ

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

A. Thuật toán quay lui (Backtracking)

B. Thuật toán sắp xếp trộn (Merge Sort)

C. Thuật toán Dijkstra

D. Thuật toán quy hoạch động (Dynamic Programming)

29. Cấu trúc dữ liệu nào phù 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 (Cây Heap)

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

30. Ư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 sắp xếp hơn