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

1. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ 'cha-con' trong một gia đình hoặc tổ chức?

A. Mảng (Array)

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

C. Cây (Tree)

D. Hàng đợi (Queue)

2. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n) và thường được sử dụng trong thực tế nhờ hiệu suất tố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)

3. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ tập hợp các đỉnh chưa được thăm và ưu tiên đỉnh có khoảng cách ngắn nhất?

A. Mảng (Array)

B. Ngăn xếp (Stack)

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

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

4. Ưu điểm chính 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. Truy cập phần tử nhanh hơn

C. Duyệt danh sách theo cả hai chiều

D. Thêm và xóa phần tử ở đầu danh sách nhanh hơn

5. Trong cấu trúc dữ liệu cây AVL, thao tác 'xoay cây' (tree rotation) được sử dụng để làm gì?

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

B. Cân bằng lại cây sau khi thêm hoặc xóa nút

C. Duyệt cây theo thứ tự trước (pre-order)

D. Tăng chiều cao của cây

6. Trong cây đỏ-đen (Red-Black Tree), thuộc tính nào sau đây không đúng?

A. Mỗi nút có màu đỏ hoặc đen

B. Gốc và lá (nút NULL) có màu đen

C. Nếu một nút là đỏ, cả hai con của nó phải là đen

D. Đường đi từ gốc đến mọi nút lá có số lượng nút đen bằng nhau

7. Trong thuật toán tô pô (topological sort), đồ thị đầu vào phải có tính chất gì để thuật toán có thể thực hiện được?

A. Phải là đồ thị có hướng và có chu trình

B. Phải là đồ thị vô hướng và liên thông

C. Phải là đồ thị có hướng và không có chu trình (DAG - Directed Acyclic Graph)

D. Phải là đồ thị đầy đủ (complete graph)

8. Khái niệm 'đệ quy' (Recursion) trong lập trình liên quan chặt chẽ đến cấu trúc dữ liệu nào sau đây khi thực hiện các cuộc gọi hàm?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

D. Mảng (Array)

9. Ứng dụng phổ biến của cây khung nhỏ nhất (Minimum Spanning Tree - MST) là gì?

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

B. Phân tích mạng xã hội

C. Thiết kế mạng lưới giao thông/điện lực/máy tính với chi phí tối thiểu

D. Sắp xếp dữ liệu

10. Cấu trúc dữ liệu nào sau đây thường được sử dụng để quản lý bộ nhớ động (dynamic memory allocation) trong hệ điều hành?

A. Mảng (Array)

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

C. Heap (Vùng nhớ Heap)

D. Ngăn xếp (Stack)

11. Điểm khác biệt chính giữa thuật toán tham lam (Greedy algorithm) và thuật toán quy hoạch động (Dynamic Programming) là gì?

A. Thuật toán tham lam luôn tìm ra nghiệm tối ưu, quy hoạch động thì không

B. Thuật toán quy hoạch động giải quyết bài toán bằng cách chia nhỏ thành các bài toán con và lưu kết quả để tái sử dụng, tham lam thì không

C. Thuật toán tham lam nhanh hơn quy hoạch động

D. Quy hoạch động chỉ áp dụng cho bài toán tối ưu hóa, tham lam thì không

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

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

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

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

D. Kiểm tra tính liên thông của đồ thị

13. Trong cấu trúc dữ liệu đồ thị (Graph), cách biểu diễn nào sau đây sử dụng ít bộ nhớ hơn khi đồ thị là đồ thị thưa (sparse graph)?

A. Ma trận kề (Adjacency Matrix)

B. Danh sách kề (Adjacency List)

C. Ma trận liên thuộc (Incidence Matrix)

D. Cả ba cách đều tương đương về bộ nhớ

14. 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. Heap (Cây Heap)

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

15. Trong ngữ cảnh của bảng băm (Hash Table), 'xung đột' (collision) xảy ra khi nào?

A. Khi bảng băm đầy

B. Khi hai khóa khác nhau băm vào cùng một vị trí trong bảng

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

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

16. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong bảng băm (Hash Table) là bao nhiêu, giả sử hàm băm phân phối đều các khóa?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

17. Phương pháp tiếp cận 'chia để trị' (Divide and Conquer) thường được sử dụng trong thuật toán nào sau đây?

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)

18. Trong cấu trúc dữ liệu đồ thị, thuật toán Prim và Kruskal được sử dụng để giải quyết cùng một bài toán nào?

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

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

C. Tìm luồng cực đại (Maximum Flow)

D. Tìm chu trình Hamilton

19. Thuật toán sắp xếp nào sau đây là 'ổn định' (stable sort), nghĩa là các phần tử có khóa bằng nhau giữ nguyên thứ tự tương đối ban đầu của chúng?

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)

20. Trong thuật toán KMP (Knuth-Morris-Pratt) để tìm kiếm chuỗi con, bảng 'bảng tiền tố' (prefix table) được sử dụng để làm gì?

A. Lưu trữ vị trí xuất hiện của chuỗi con

B. Tối ưu hóa việc so sánh mẫu khi có sự không khớp

C. Giảm độ phức tạp không gian của thuật toán

D. Tăng tốc độ tìm kiếm trong trường hợp chuỗi văn bản ngắn

21. Phương pháp 'backtracking' (quay lui) thường được sử dụng để giải quyết loại bài toán nào sau đây?

A. Bài toán tìm đường đi ngắn nhất

B. Bài toán tối ưu hóa bằng quy hoạch động

C. Bài toán tìm tất cả các nghiệm hoặc nghiệm tối ưu trong không gian nghiệm lớn

D. Bài toán sắp xếp dữ liệu

22. Trong cây nhị phân tìm kiếm (BST), khi nào thao tác tìm kiếm có độ phức tạp thời gian xấu nhất là O(n)?

A. Khi cây là cây cân bằng (balanced tree)

B. Khi cây là cây suy biến (skewed tree)

C. Khi cây có ít nút

D. Độ phức tạp luôn là O(log n)

23. 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 được 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. Đồ thị (Graph)

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

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

25. Khi nào thì nên sử dụng thuật toán sắp xếp chèn (Insertion Sort) thay vì các thuật toán sắp xếp phức tạp hơn như Quick Sort hay Merge Sort?

A. Khi cần sắp xếp một lượng lớn dữ liệu

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

C. Khi yêu cầu độ phức tạp thời gian tốt nhất là O(log n)

D. Khi cần sắp xếp dữ liệu ngẫu nhiên hoàn toàn

26. Cho một mảng đã sắp xếp. Thuật toán nào sau đây có thể được sử dụng để tìm kiếm một phần tử với độ phức tạp thời gian O(log n)?

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)

27. Trong cấu trúc dữ liệu đồ thị, chu trình Euler tồn tại trong đồ thị vô hướng liên thông khi và chỉ khi điều kiện nào sau đây được thỏa mãn?

A. Tất cả các đỉnh có bậc chẵn

B. Có đúng hai đỉnh có bậc lẻ

C. Có nhiều hơn hai đỉnh có bậc lẻ

D. Luôn tồn tại trong đồ thị vô hướng liên thông

28. Trong các cấu trúc dữ liệu sau, cấu trúc 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)

29. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là O(n), điều này chủ yếu là do đâu?

A. Sử dụng đệ quy

B. Cần mảng phụ trợ để trộn các mảng con

C. Thao tác so sánh phần tử

D. Số lượng vòng lặp trong thuật toán

30. Ưu điểm chính của việc sử dụng cây Trie (tiền tố) là gì?

A. Tìm kiếm nhanh hơn trong mảng

B. Tiết kiệm bộ nhớ hơn so với bảng băm

C. Tìm kiếm tiền tố (prefix search) hiệu quả

D. Sắp xếp dữ liệu nhanh hơn