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

1. Cấu trúc dữ liệu nào 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 (Đống)

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

2. Phương pháp tiếp cận 'chia để trị' (Divide and Conquer) đượ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)

3. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là:

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

4. Thuật toán Kruskal được sử dụng để giải quyết bài toán nào sau đây?

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. Sắp xếp đồ thị

D. Tìm kiếm theo chiều rộng trên đồ thị

5. Thuật toán tìm kiếm theo chiều sâu (DFS - Depth-First Search) thường được sử dụng để làm gì?

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

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

C. Duyệt và khám phá các thành phần liên thông của đồ thị

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

6. Trong cây AVL, khi nào cần thực hiện phép quay cây?

A. Khi cây trở nên quá cao

B. Khi cây trở nên quá thấp

C. Khi cây mất cân bằng (hệ số cân bằng vượt quá ±1)

D. Khi số lượng nút trong cây vượt quá một ngưỡng nhất định

7. Trong cây Trie (cây tiền tố), mục đích chính của việc sử dụng cấu trúc này là gì?

A. Sắp xếp dữ liệu theo thứ tự

B. Tìm kiếm gần đúng (fuzzy search)

C. Lưu trữ và tìm kiếm hiệu quả các chuỗi (tiền tố)

D. Nén dữ liệu

8. Thuật toán BFS (Breadth-First Search) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần thăm?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Mảng (Array)

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

9. Kiểu dữ liệu trừu tượng (ADT - Abstract Data Type) nào mô tả một tập hợp các phần tử không có thứ tự và không cho phép phần tử trùng lặp?

A. Danh sách (List)

B. Tập hợp (Set)

C. Hàng đợi (Queue)

D. Ngăn xếp (Stack)

10. Trong cây đỏ-đen (Red-Black Tree), màu sắc của một nút được sử dụng để làm gì?

A. Biểu thị giá trị của nút

B. Xác định độ ưu tiên của nút

C. Duy trì tính cân bằng của cây

D. Xác định nút cha của nút

11. Cấu trúc dữ liệu nào cho phép truy cập ngẫu nhiên (random access) đến các phần tử với độ phức tạp thời gian 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. Hàng đợi (Queue)

12. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ 'nhiều-nhiều'?

A. Mảng (Array)

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

C. Cây (Tree)

D. Đồ thị (Graph)

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

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

B. Bài toán sắp xếp mảng

C. Bài toán tìm kiếm nhị phân

D. Bài toán quy hoạch động

14. Thuật toán tìm kiếm nào hiệu quả nhất trên một mảng đã đượ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)

15. Cấu trúc dữ liệu nào sau đây là 'phi tuyến tính'?

A. Mảng (Array)

B. Hàng đợi (Queue)

C. Cây (Tree)

D. Ngăn xếp (Stack)

16. Trong lập trình động (Dynamic Programming), kỹ thuật 'ghi nhớ' (memoization) là gì?

A. Kỹ thuật chia nhỏ bài toán thành các bài toán con

B. Kỹ thuật lưu trữ kết quả của các bài toán con đã giải để tránh tính toán lại

C. Kỹ thuật sắp xếp các bài toán con theo thứ tự

D. Kỹ thuật tối ưu hóa không gian bộ nhớ sử dụng

17. Ưu điểm chính của 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 ngẫu nhiên nhanh hơn

C. Duyệt ngược danh sách dễ dàng hơn

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

18. 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 từ đỉnh nguồn đến các đỉnh khác?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Mảng (Array)

D. Heap (Đống) ưu tiên

19. Trong bảng băm (Hash Table), 'xử lý đụng độ' (collision resolution) là gì?

A. Quá trình tính toán hàm băm

B. Quá trình tìm kiếm giá trị trong bảng băm

C. Kỹ thuật giải quyết khi nhiều khóa băm vào cùng một vị trí

D. Quá trình thay đổi kích thước bảng băm

20. Thuật toán nào sau đây không phải là thuật toán sắp xếp so sánh?

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

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

C. Sắp xếp đếm (Counting Sort)

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

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

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

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

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

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

22. Thuật toán nào sau đây là một ví dụ của thuật toán 'quay lui' (Backtracking)?

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

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

C. Giải Sudoku

D. Thuật toán Dijkstra

23. Cấu trúc dữ liệu 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. Mảng (Array)

24. Trong 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 (Searching for a node)

D. Duyệt cây theo thứ tự giữa (In-order traversal)

25. Trong thuật toán sắp xếp vun đống (Heap Sort), giai đoạn 'vun đống' (heapify) có mục đích gì?

A. Chia mảng thành các phần nhỏ hơn

B. Trộn các mảng đã sắp xếp

C. Xây dựng một heap từ mảng đầu vào

D. Tìm phần tử nhỏ nhất trong mảng

26. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick Sort) là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

27. Độ 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) trong trường hợp mảng đã được sắp xếp là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

28. Cấu trúc dữ liệu nào 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 nhị phân tìm kiếm (Binary Search Tree)

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

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

30. Thuật toán nào sau đây tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số âm, nhưng không có chu trình âm?

A. Dijkstra

B. BFS

C. DFS

D. Bellman-Ford