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

1. Thuật toán duyệt đồ thị theo chiều rộng (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. Danh sách liên kết (Linked List)

D. Cây nhị phân (Binary Tree)

2. Ưu điểm của việc sử dụng cây khung tối thiểu (Minimum Spanning Tree - MST) trong bài toán mạng máy tính là gì?

A. Tăng tốc độ truyền dữ liệu

B. Giảm thiểu chi phí xây dựng mạng

C. Tăng cường bảo mật mạng

D. Đơn giản hóa cấu trúc mạng

3. Thuật toán Kruskal và thuật toán Prim đều được sử dụng để giải quyết bài toán nào?

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

B. Sắp xếp đồ thị

C. Tìm cây khung tối thiểu (MST)

D. Duyệt đồ thị

4. Ư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 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. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở vị trí bất kỳ trong thời gian O(1)?

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

B. Ngăn xếp (Stack)

C. Hàng đợi (Queue)

D. Mảng (Array)

6. Độ phức tạp thời gian của thao tác chèn một phần tử vào đầu danh sách liên kết đơn (Singly Linked List) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

7. Điểm khác biệt chính giữa thuật toán sắp xếp chọn (Selection Sort) và sắp xếp nổi bọt (Bubble Sort) là gì?

A. Độ phức tạp thời gian

B. Cách thức so sánh và hoán đổi phần tử

C. Độ phức tạp không gian

D. Tính ổn định (stability)

8. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm tuyến tính (Linear 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(1)

D. O(n log n)

9. 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 (Đống)

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

10. 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. Cây nhị phân tìm kiếm (Binary Search Tree)

11. Thuật toán duyệt đồ thị theo chiều sâu (DFS - Depth-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. 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)

12. Trong thuật toán sắp xếp trộn (Merge Sort), giai đoạn 'chia' (divide) thực hiện công việc gì?

A. So sánh và hoán đổi các phần tử để sắp xếp

B. Chia mảng ban đầu thành các mảng con nhỏ hơn

C. Trộn các mảng con đã sắp xếp lại thành mảng lớn hơn

D. Chọn phần tử nhỏ nhất và đưa về đầu mảng

13. Ứng dụng phổ biến nhất của cấu trúc dữ liệu hàng đợi (Queue) trong khoa học máy tính là gì?

A. Quản lý bộ nhớ

B. Lập lịch CPU

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

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

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

15. Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp nhanh (Quick Sort) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(n log n)

16. Trong cây đỏ-đen (Red-Black Tree), một tính chất quan trọng đảm bảo cây luôn cân bằng là gì?

A. Tất cả các nút đều phải có màu đỏ

B. Đường đi từ nút gốc đến bất kỳ nút lá nào phải có số lượng nút đen bằng nhau

C. Cây con trái và cây con phải của mỗi nút phải có chiều cao bằng nhau

D. Các nút lá phải có màu đỏ

17. Trong thuật toán tìm kiếm nhị phân (Binary Search), điều kiện tiên quyết để thuật toán hoạt động đúng là gì?

A. Mảng phải có kích thước lớn

B. Mảng phải được sắp xếp

C. Các phần tử trong mảng phải là duy nhất

D. Mảng phải chứa số lượng phần tử là số chẵn

18. Trong cây AVL, yếu tố cân bằng (balance factor) của một nút được định nghĩa là gì?

A. Tổng chiều cao của cây con trái và cây con phải

B. Hiệu chiều cao của cây con trái và cây con phải

C. Tích chiều cao của cây con trái và cây con phải

D. Thương chiều cao của cây con trái và cây con phải

19. 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. Danh sách liên kết (Linked List)

C. Cây (Tree)

D. Hàng đợi (Queue)

20. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (Binary Search Tree), nút con bên trái của một nút luôn có giá trị như thế nào so với nút cha?

A. Lớn hơn

B. Nhỏ hơn

C. Bằng

D. Lớn hơn hoặc bằng

21. Thuật toán nào sau đây thuộc loại thuật toán tham lam (Greedy Algorithm)?

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

B. Quy hoạch động (Dynamic Programming)

C. Thuật toán Dijkstra

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

22. Độ 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(1)

D. O(n log n)

23. Thuật toán Dijkstra thường được sử dụng để giải quyết bài toán nào?

A. Tìm kiếm tuyến tính

B. Sắp xếp mảng

C. Tìm đường đi ngắn nhất trên đồ thị

D. Duyệt cây nhị phân

24. 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. 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)

25. Khi nào thì việc sử dụng danh sách liên kết (Linked List) được ưu tiên hơn so với mảng (Array)?

A. Khi cần truy cập ngẫu nhiên đến các phần tử

B. Khi kích thước dữ liệu cố định và nhỏ

C. Khi số lượng thao tác chèn/xóa ở giữa danh sách là nhiều

D. Khi cần tìm kiếm nhanh chóng các phần tử

26. 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 được băm đến cùng một vị trí

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

D. Khi hàm băm không hiệu quả

27. 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)?

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)

28. Trong đồ thị vô hướng, bậc của một đỉnh được định nghĩa là gì?

A. Số cạnh đi vào đỉnh đó

B. Số cạnh đi ra khỏi đỉnh đó

C. Tổng số đỉnh kề với đỉnh đó

D. Số cạnh kết nối với đỉnh đó

29. Khi nào thì độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick Sort) có thể trở thành O(n^2)?

A. Khi mảng đầu vào đã được sắp xếp ngược

B. Khi phần tử chốt (pivot) luôn được chọn ngẫu nhiên

C. Khi mảng đầu vào gần như đã được sắp xếp

D. Khi phần tử chốt (pivot) luôn là phần tử nhỏ nhất hoặc lớn nhất trong mảng con

30. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp, ví dụ như cây thư mục trong hệ điều hành?

A. Mảng (Array)

B. Hàng đợi (Queue)

C. Cây (Tree)

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