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

1. Thuật toán sắp xếp nào thường được coi là nhanh nhất trong thực tế cho dữ liệu lớn, mặc dù độ phức tạp trường hợp xấu nhất là O(n^2)?

A. Bubble Sort

B. Insertion Sort

C. Quick Sort

D. Merge Sort

2. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị có trọng số dương?

A. Breadth-First Search (BFS)

B. Depth-First Search (DFS)

C. Dijkstra

D. Bubble Sort

3. Trong thuật toán BFS (Breadth-First Search), cấu trúc dữ liệu nào được sử dụng để quản lý các đỉnh cần duyệt?

A. Stack

B. Queue

C. Heap

D. Tree

4. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc FIFO (First In, First Out)?

A. Stack

B. Queue

C. Tree

D. Graph

5. Cấu trúc dữ liệu nào cho phép truy cập phần tử đầu và cuối trong thời gian O(1)?

A. Mảng (Array)

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

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

D. Hàng đợi hai đầu (Deque)

6. Thuật toán nào sau đây có thể phát hiện chu trình trong đồ thị có hướng?

A. Breadth-First Search (BFS)

B. Depth-First Search (DFS)

C. Dijkstra

D. Binary Search

7. Thuật toán sắp xếp nào có tính ổn định (stable sort), nghĩa là các phần tử bằng nhau giữ nguyên thứ tự tương đối sau khi sắp xếp?

A. Quick Sort

B. Heap Sort

C. Merge Sort

D. Selection Sort

8. Trong thuật toán tìm kiếm nhị phân trên mảng có n phần tử, số phép so sánh tối đa trong trường hợp xấu nhất là bao nhiêu?

A. n

B. log₂(n)

C. n log₂(n)

D. n²

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

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

10. Trong cấu trúc dữ liệu Stack, thao tác nào sau đây tuân theo nguyên tắc LIFO (Last In, First Out)?

A. Enqueue

B. Dequeue

C. Push

D. Pop

11. Độ phức tạp thời gian tốt nhất của thuật toán Bubble Sort là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(1)

12. 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. Bubble Sort

B. Insertion Sort

C. Quick Sort

D. Merge Sort

13. Ưu điểm 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. Duyệt theo chiều ngược lại dễ dàng hơn

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

D. Truy cập phần tử ngẫu nhiên nhanh hơn

14. Giải thuật sắp xếp nào có độ phức tạp thời gian tốt nhất là O(n) trong trường hợp dữ liệu đã gần như được sắp xếp?

A. Quick Sort

B. Merge Sort

C. Insertion Sort

D. Bubble Sort

15. Thuật toán nào sau đây là ví dụ của phương pháp `tham lam` (greedy algorithm)?

A. Merge Sort

B. Dijkstra

C. Dynamic Programming

D. Depth-First Search

16. Cấu trúc dữ liệu nào sử dụng hàm băm (hash function) để ánh xạ khóa (key) đến vị trí lưu trữ?

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

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

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

D. Hàng đợi (Queue)

17. Trong cây, nút gốc (root node) là nút có đặc điểm gì?

A. Nút có nhiều nút con nhất

B. Nút không có nút cha

C. Nút nằm ở mức sâu nhất của cây

D. Nút có giá trị lớn nhất

18. Khi nào thì việc sử dụng bảng băm (Hash Table) trở nên kém hiệu quả hơn so với cây nhị phân tìm kiếm (Binary Search Tree)?

A. Khi cần sắp xếp dữ liệu theo thứ tự

B. Khi số lượng phần tử rất lớn

C. Khi hàm băm phân bố đều

D. Khi cần tìm kiếm phần tử nhỏ nhất/lớn nhất

19. Độ phức tạp không gian của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

20. Phương pháp tiếp cận `chia để trị` (Divide and Conquer) được sử dụng hiệu quả trong thuật toán sắp xếp nào?

A. Bubble Sort

B. Insertion Sort

C. Quick Sort

D. Selection Sort

21. Trong thuật toán DFS (Depth-First Search), cấu trúc dữ liệu nào thường được sử dụng (một cách ngầm định hoặc tường minh) để theo dõi đường đi?

A. Queue

B. Stack

C. Heap

D. Array

22. 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, ví dụ như cây thư mục trong máy tính?

A. Mảng (Array)

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

C. Cây (Tree)

D. Hàng đợi (Queue)

23. Cấu trúc dữ liệu nào phù hợp để cài đặt hàng đợi ưu tiên (Priority Queue)?

A. Stack

B. Queue

C. Heap

D. Linked List

24. Giải thuật nào sau đây sử dụng kỹ thuật `ghi nhớ` (memoization) để tối ưu hóa hiệu suất?

A. Bubble Sort

B. Linear Search

C. Dynamic Programming

D. Depth-First Search

25. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác nào sau đây có thể cho độ phức tạp thời gian trường hợp xấu nhất là O(n)?

A. Tìm kiếm (Search)

B. Chèn (Insert)

C. Xóa (Delete)

D. Cả ba đáp án trên

26. Trong thuật toán tìm kiếm nhị phân (Binary Search), dữ liệu đầu vào cần phải đáp ứng điều kiện tiên quyết nào?

A. Dữ liệu phải là số nguyên

B. Dữ liệu phải được sắp xếp

C. Dữ liệu phải là duy nhất

D. Dữ liệu phải có kích thước nhỏ

27. Trong cây nhị phân đầy đủ (full binary tree), mỗi nút (trừ lá) có bao nhiêu nút con?

A. 0

B. 1

C. 2

D. Tùy ý

28. Ư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ử ngẫu nhiên 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 phần tử nhanh hơn

29. Trong cấu trúc dữ liệu đồ thị (Graph), ma trận kề (adjacency matrix) phù hợp nhất để biểu diễn loại đồ thị nào?

A. Đồ thị thưa (sparse graph)

B. Đồ thị dày (dense graph)

C. Cây (tree)

D. Danh sách liên kết (linked list)

30. Cấu trúc dữ liệu nào có thể được sử dụng để kiểm tra xem một biểu thức ngoặc có hợp lệ (ví dụ: `()[]{}`) hay không?

A. Queue

B. Stack

C. Heap

D. Linked List