Đề 10 – 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 Floyd-Warshall được sử dụng để làm gì?

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

B. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số

C. Sắp xếp đồ thị theo thứ tự topo

D. Tìm luồng cực đại trong mạng

2. Ưu điểm chính của danh sách liên kết so với mảng 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 cho dữ liệu tĩnh

C. Dễ dàng chèn và xóa phần tử

D. Tìm kiếm phần tử nhanh hơn

3. Trong cây nhị phân tìm kiếm, thứ tự duyệt nào cho phép in ra các nút theo thứ tự tăng dần?

A. Duyệt theo thứ tự trước (Pre-order traversal)

B. Duyệt theo thứ tự giữa (In-order traversal)

C. Duyệt theo thứ tự sau (Post-order traversal)

D. Duyệt theo chiều rộng (Breadth-first traversal)

4. Thuật toán sắp xếp nào hoạt động tốt nhất trên dữ liệu đã gần như được sắp xếp?

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

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

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

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

5. Trong đồ thị, 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ố âm

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

C. Tìm chu trình Hamilton

D. Sắp xếp đồ thị theo thứ tự topo

6. 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. Cây nhị phân (Binary Tree)

7. Mục đích chính của việc sử dụng cấu trúc dữ liệu là gì?

A. Tăng độ phức tạp của thuật toán

B. Tổ chức và lưu trữ dữ liệu một cách hiệu quả để dễ dàng truy cập và thao tác

C. Giảm dung lượng lưu trữ dữ liệu

D. Làm cho mã nguồn khó đọc hơn

8. Cấu trúc dữ liệu nào cho phép truy cập phần tử ngẫu nhiên 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. Cây nhị phân (Binary Tree)

9. Kiểu dữ liệu trừu tượng (ADT) nào mô tả một tập hợp các phần tử mà việc thêm và xóa chỉ xảy ra ở một đầu?

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)

10. Trong cây nhị phân tìm kiếm, thao tác nào sau đây có độ phức tạp thời gian trung bình là O(log n)?

A. Duyệt theo thứ tự trước (Pre-order traversal)

B. Duyệt theo thứ tự sau (Post-order traversal)

C. Tìm kiếm một nút

D. Duyệt theo chiều rộng (Breadth-first traversal)

11. Độ phức tạp thời gian trường hợp xấu nhất của thuật toán tìm kiếm tuyến tính trong một mảng có kích thước n là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

12. Trong cây nhị phân, nút gốc (root node) là gì?

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

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

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

D. Nút nằm ở mức thấp nhất

13. Trong thuật toán sắp xếp nhanh (Quick Sort), thao tác `phân vùng` (partition) làm gì?

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

B. Chọn phần tử chốt và sắp xếp mảng sao cho các phần tử nhỏ hơn chốt ở bên trái và lớn hơn ở bên phải

C. Chia mảng thành hai nửa bằng nhau

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

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

15. Thuật toán sắp xếp nào có độ phức tạp thời gian tốt nhất trong trường hợp xấu nhất 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 nổi bọt (Bubble Sort)

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

A. Mảng (Array)

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

C. Cây (Tree)

D. Ngăn xếp (Stack)

17. Trong ngữ cảnh Cấu trúc dữ liệu, thuật ngữ `ADT` đề cập đến điều gì?

A. Kiểu dữ liệu trừu tượng

B. Kiểu dữ liệu động

C. Kiểu dữ liệu thích ứng

D. Kiểu dữ liệu ứng dụng

18. Thuật toán Dijkstra được sử dụng để làm gì?

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

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. Sắp xếp đồ thị theo thứ tự topo

D. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)

19. Cấu trúc dữ liệu nào thường được sử dụng để kiểm tra dấu ngoặc đúng trong biểu thức?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Mảng

D. Danh sách liên kết

20. Ưu điểm chính của cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) so với cây nhị phân tìm kiếm không cân bằng là gì?

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

B. Duyệt cây nhanh hơn

C. Đảm bảo độ phức tạp O(log n) cho các thao tác tìm kiếm, chèn, xóa

D. Cài đặt đơn giản hơn

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

A. Mảng

B. Danh sách liên kết

C. Cây (Tree)

D. Đồ thị (Graph)

22. Thuật toán Kruskal đượ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 (Minimum Spanning Tree) trong đồ thị có trọng số

C. Sắp xếp đồ thị theo thứ tự topo

D. Tìm chu trình Euler

23. Hash table (Bảng băm) sử dụng hàm băm để làm gì?

A. Sắp xếp các phần tử

B. Tính toán địa chỉ chỉ mục cho khóa

C. Mã hóa dữ liệu

D. Nén dữ liệu

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

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

25. Ứng dụng phổ biến của hàng đợi (Queue) là gì?

A. Quản lý ngăn xếp lệnh gọi hàm

B. Xử lý tác vụ theo thứ tự đến trước phục vụ trước (FIFO) trong hệ điều hành

C. Tìm kiếm theo chiều sâu trong đồ thị

D. Lưu trữ lịch sử truy cập trang web

26. Khi nào thì nên sử dụng bảng băm (Hash table) thay vì cây tìm kiếm nhị phân?

A. Khi cần dữ liệu được sắp xếp

B. Khi cần tìm kiếm, chèn, xóa với độ phức tạp trung bình O(1)

C. Khi cần duyệt các phần tử theo thứ tự

D. Khi dữ liệu có cấu trúc phân cấp rõ ràng

27. Cấu trúc dữ liệu nào thường được sử dụng để cài đặt hàng đợi ưu tiên?

A. Mảng

B. Danh sách liên kết

C. Heap (Đống)

D. Cây tìm kiếm nhị phân

28. Thuật toán nào sau đây là một ví dụ của kỹ thuật `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 trộn (Merge Sort)

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

29. Trong ngữ cảnh đồ thị, chu trình (cycle) là gì?

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

B. Đường đi bắt đầu và kết thúc tại cùng một đỉnh

C. Đường đi không lặp lại đỉnh

D. Đường đi dài nhất trong đồ thị

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