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

1. Giải thuật tham lam (Greedy algorithm) thường được sử dụng để giải quyết loại bài toán nào?

A. Bài toán tìm kiếm đường đi ngắn nhất trong đồ thị.

B. Bài toán tối ưu hóa, tìm giải pháp tối ưu cục bộ với hy vọng đạt tối ưu toàn cục.

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

D. Bài toán tìm kiếm trong cây nhị phân tìm kiếm.

2. Hash Table (Bảng băm) hoạt động hiệu quả nhất khi nào?

A. Khi có quá nhiều phần tử trùng lặp.

B. Khi cần truy cập các phần tử theo thứ tự.

C. Khi hàm băm phân phối đều các khóa.

D. Khi số lượng phần tử nhỏ.

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

C. Queue (Hàng đợi)

D. Graph (Đồ thị)

4. Thuật toán nào sau đây là một ví dụ của phương pháp `Chia để trị` (Divide and Conquer)?

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

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

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

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

5. 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 trong đồ thị.

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

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

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

6. Đệ quy (Recursion) là gì trong lập trình?

A. Một kỹ thuật lặp đi lặp lại một đoạn mã cho đến khi một điều kiện dừng được đáp ứng.

B. Một hàm tự gọi chính nó để giải quyết một bài toán nhỏ hơn của cùng loại.

C. Một cách để tổ chức dữ liệu theo thứ tự tuyến tính.

D. Một phương pháp tối ưu hóa bộ nhớ bằng cách chia sẻ dữ liệu giữa các biến.

7. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) là gì?

A. Một cách cài đặt cụ thể của cấu trúc dữ liệu trong một ngôn ngữ lập trình.

B. Một mô hình toán học của cấu trúc dữ liệu, định nghĩa các thao tác và tính chất mà không quan tâm đến cài đặt.

C. Một loại biến đặc biệt chỉ lưu trữ địa chỉ bộ nhớ.

D. Một phương pháp tối ưu hóa tốc độ thực thi của chương trình.

8. Ư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 ngẫu nhiên các 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. Sắp xếp các phần tử nhanh hơn.

9. 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 giữa các đỉnh.

B. Phân chia các đỉnh thành các nhóm sao cho không có cạnh nào nối hai đỉnh cùng nhóm.

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

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

10. Độ phức tạp không gian của thuật toán Merge Sort (Sắp xếp trộn) là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

11. Trong một cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào 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 thứ tự giữa (In-order traversal).

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

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

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

D. Tree (Cây)

13. 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. Bubble Sort (Sắp xếp nổi bọt)

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

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

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

14. Khi nào thì việc sử dụng danh sách liên kết đôi (Doubly Linked List) trở nên hữu ích hơn so với danh sách liên kết đơn (Singly Linked List)?

A. Khi chỉ cần duyệt danh sách theo một chiều.

B. Khi cần chèn hoặc xóa nút ở cuối danh sách thường xuyên.

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

D. Khi số lượng phần tử trong danh sách rất lớn nhưng cố định.

15. Trong cây nhị phân đầy đủ (Full Binary Tree), nếu cây có chiều cao h (tính từ gốc, gốc ở mức 0), thì số lượng nút tối đa có thể có là bao nhiêu?

A. h + 1

B. 2h

C. 2^(h+1) - 1

D. 2^h - 1

16. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ `cha-con` trong một hệ thống phân cấp?

A. Queue (Hàng đợi)

B. Stack (Ngăn xếp)

C. Tree (Cây)

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

17. Cấu trúc dữ liệu đồ thị (Graph) được sử dụng để mô hình hóa loại quan hệ nào?

A. Quan hệ tuyến tính tuần tự.

B. Quan hệ phân cấp cha-con.

C. Quan hệ mạng lưới, nhiều-nhiều.

D. Quan hệ một-nhiều có thứ tự.

18. Bộ nhớ Cache hoạt động dựa trên nguyên tắc nào để tăng tốc độ truy cập dữ liệu?

A. Nguyên tắc LIFO (Last In, First Out).

B. Nguyên tắc FIFO (First In, First Out).

C. Nguyên tắc cục bộ (Locality).

D. Nguyên tắc đệ quy (Recursion).

19. Phương pháp lập trình động (Dynamic Programming) tiếp cận bài toán bằng cách nào?

A. Chia bài toán thành các bài toán con độc lập và giải quyết riêng lẻ.

B. Chia bài toán thành các bài toán con gối nhau và lưu trữ kết quả để tái sử dụng.

C. Giải quyết bài toán bằng cách đưa ra lựa chọn tối ưu cục bộ ở mỗi bước.

D. Thử tất cả các khả năng để tìm ra giải pháp tối ưu.

20. Trong ngữ cảnh cấu trúc dữ liệu và giải thuật, `overflow` (tràn bộ nhớ) xảy ra khi nào?

A. Khi cố gắng truy cập một vùng nhớ không hợp lệ.

B. Khi cấu trúc dữ liệu chứa quá nhiều phần tử vượt quá khả năng lưu trữ.

C. Khi thực hiện phép chia cho 0.

D. Khi chương trình chạy quá chậm.

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

B. Queue (Hàng đợi)

C. Heap (Vun đống)

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

22. Thuật toán sắp xếp nào sau đây là `ổn định` (stable), tức là duy trì thứ tự tương đối của các phần tử có khóa bằng nhau?

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

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

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

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

23. Độ phức tạp thời gian tốt nhất của thuật toán Insertion Sort (Sắp xếp chèn) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

24. 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 từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.

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

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

D. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô.

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

B. Stack (Ngăn xếp)

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

D. Tree (Cây)

26. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong một mảng (Array) đã được sắp xếp bằng thuật toán tìm kiếm nhị phân (Binary Search) là bao nhiêu?

A. O(n)

B. O(1)

C. O(log n)

D. O(n^2)

27. Cây AVL là gì?

A. Một loại cây nhị phân tìm kiếm không cân bằng.

B. Một loại cây nhị phân tìm kiếm tự cân bằng.

C. Một loại đồ thị có hướng không chu trình.

D. Một loại danh sách liên kết đôi.

28. Thuật toán quay lui (Backtracking) thường được sử dụng để giải quyết loại bài toán nào?

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

B. Bài toán liệt kê tất cả các cấu hình thỏa mãn một số điều kiện.

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

D. Bài toán nén dữ liệu.

29. So sánh độ phức tạp thời gian của tìm kiếm tuyến tính (Linear Search) và tìm kiếm nhị phân (Binary Search) trong trường hợp xấu nhất.

A. Tìm kiếm tuyến tính nhanh hơn tìm kiếm nhị phân.

B. Tìm kiếm nhị phân nhanh hơn tìm kiếm tuyến tính.

C. Cả hai có độ phức tạp thời gian như nhau.

D. Tùy thuộc vào kích thước dữ liệu.

30. Trong thuật toán sắp xếp Heap Sort (Sắp xếp vun đống), cấu trúc dữ liệu Heap được sử dụng có tính chất gì?

A. Mỗi nút con luôn lớn hơn hoặc bằng nút cha (Max-Heap).

B. Mỗi nút con luôn nhỏ hơn hoặc bằng nút cha (Min-Heap).

C. Cả hai tính chất Max-Heap và Min-Heap đều có thể được sử dụng.

D. Không có tính chất ràng buộc về giá trị giữa nút cha và nút con.