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

1. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai chức năng 'undo/redo' trong các ứng dụng chỉnh sửa?

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)

2. 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 trên đồ thị có trọng số âm

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 được tối ưu toàn cục

C. Bài toán sắp xếp một lượng lớn dữ liệu

D. Bài toán tìm kiếm trong không gian trạng thái lớn

3. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào sau đây có thể làm mất cân bằng cây và dẫn đến hiệu suất suy giảm trong trường hợp xấu nhất?

A. Tìm kiếm (Search)

B. Chèn (Insertion)

C. Duyệt cây (Traversal)

D. Xóa (Deletion)

4. Độ 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à gì?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

5. Để phát hiện chu trình trong một đồ thị có hướng, thuật toán nào sau đây thường được sử dụng?

A. Thuật toán Dijkstra

B. Thuật toán Kruskal

C. DFS (Depth-First Search)

D. BFS (Breadth-First Search)

6. Trong cây Trie (tiền tố), thao tác nào sau đây có độ phức tạp thời gian phụ thuộc vào chiều dài của khóa (từ) chứ không phụ thuộc vào số lượng khóa trong cây?

A. Duyệt cây (Traversal)

B. Tìm kiếm (Search)

C. Sắp xếp (Sorting)

D. Cân bằng cây (Balancing)

7. Thuật toán DFS (Depth-First Search) trong đồ thị thường được sử dụng để làm gì?

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

B. Tìm kiếm theo chiều rộng

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

D. Sắp xếp các đỉnh theo thứ tự độ ưu tiên

8. Trong cấu trúc dữ liệu đồ thị (Graph), thuật toán BFS (Breadth-First Search) thường được sử dụng để làm gì?

A. Tìm đường đi ngắn nhất trong đồ thị có trọng số dương

B. Tìm đường đi ngắn nhất trong đồ thị không trọng số

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

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

9. Ưu điểm chính của danh sách liên kết (Linked List) so với mảng (Array) là gì khi thực hiện các thao tác chèn và xóa phần tử?

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

C. Chèn và xóa phần tử ở đầu hoặc giữa danh sách nhanh hơn

D. Dễ dàng triển khai hơn

10. Cấu trúc dữ liệu hàng đợi (Queue) thường được sử dụng trong ứng dụng nào sau đây?

A. Quản lý lịch sử duyệt web

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

C. Xử lý tác vụ theo thứ tự đến trước phục vụ trước (FIFO)

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

11. Cấu trúc dữ liệu cây nào sau đây đả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 lý tưởng?

A. Cây nhị phân suy biến (Degenerate Binary Tree)

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

C. Cây phân đoạn (Segment Tree)

D. Cây Trie

12. Trong 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 ra cùng một vị trí chỉ mục

C. Khi khóa tìm kiếm không tồn tại trong bảng băm

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

13. Trong biểu diễn đồ thị bằng danh sách kề (Adjacency List), không gian bộ nhớ cần thiết phụ thuộc vào yếu tố nào?

A. Số đỉnh của đồ thị

B. Số cạnh của đồ thị

C. Tổng số đỉnh và cạnh của đồ thị

D. Mức độ kết nối của đồ thị

14. Cấu trúc dữ liệu nào sau đây là phù hợp nhất để triển khai 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)

15. Đệ quy (Recursion) trong lập trình liên quan mật thiết đến cấu trúc dữ liệu nào sau đây?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Mảng (Array)

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

16. Độ phức tạp thời gian trung bình của thuật toán tìm kiếm tuyến tính (Linear Search) là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

17. Hàm băm (Hash function) lý tưởng nên có tính chất nào sau đây?

A. Luôn tạo ra các giá trị băm giống nhau cho các khóa khác nhau

B. Phân phối đều các khóa vào các vị trí trong bảng băm để giảm thiểu xung đột

C. Có độ phức tạp tính toán cao để tăng tính bảo mật

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

18. Giải thuật Dijkstra được sử dụng để giải quyết bài toán nào trong đồ thị?

A. Tìm chu trình âm

B. 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

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

D. Sắp xếp topo

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

20. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên đế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 (Linked List)

B. Hàng đợi (Queue)

C. Mảng (Array)

D. Ngăn xếp (Stack)

21. Kỹ thuật 'chia để trị' (Divide and Conquer) là nền tảng của 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 nổi bọt (Bubble Sort)

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

22. 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. Mảng (Array)

23. Trong thuật toán sắp xếp vun đống (Heap Sort), cấu trúc dữ liệu 'đống' (heap) được sử dụng để làm gì?

A. Lưu trữ các phần tử đã được sắp xếp

B. Chọn phần tử chốt

C. Tìm phần tử nhỏ nhất hoặc lớn nhất một cách hiệu quả

D. Chia mảng thành các đoạn con

24. Thuật toán sắp xếp nào sau đây 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 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 trộn (Merge Sort)

25. Thuật toán sắp xếp nào sau đây là 'không ổn định' (unstable sorting algorithm)?

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

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

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

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

26. Thuật toán tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất trên cấu trúc dữ liệu nào?

A. Danh sách liên kết (Linked List) chưa sắp xếp

B. Mảng (Array) đã sắp xếp

C. Cây nhị phân tìm kiếm (Binary Search Tree) chưa cân bằng

D. Đồ thị (Graph)

27. Khi nào thì thuật toán tìm kiếm tuyến tính (Linear Search) có thể 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 kích thước mảng rất lớn

C. Khi cần tìm phần tử đầu tiên trong mảng

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

28. Ưu điểm của việc sử dụng cây so với danh sách liên kết hoặc mảng để lưu trữ dữ liệu có thứ tự là gì?

A. Tiết kiệm bộ nhớ hơn

B. Truy cập phần tử nhanh hơn trong mọi trường hợp

C. Tìm kiếm, chèn và xóa hiệu quả hơn trong nhiều trường hợp

D. Dễ dàng duyệt tuần tự hơn

29. Trong thuật toán sắp xếp nhanh (Quick Sort), kỹ thuật 'phân vùng' (partitioning) có vai trò gì?

A. Chọn phần tử trung vị

B. Chia mảng thành các đoạn con bằng nhau

C. Sắp xếp tại chỗ các phần tử nhỏ hơn và lớn hơn phần tử chốt

D. Trộn hai mảng đã sắp xếp

30. Kỹ thuật 'quy hoạch động' (Dynamic Programming) thường được áp dụng để giải quyết các bài toán có tính chất nào?

A. Bài toán có không gian trạng thái nhỏ

B. Bài toán có cấu trúc cây

C. Bài toán con tối ưu chồng lấn và cấu trúc con tối ưu

D. Bài toán có thể giải quyết bằng giải thuật tham lam