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

1. Thuật toán sắp xếp nào sau đây là ổn định (stable sorting)?

A. Quick Sort

B. Heap Sort

C. Selection Sort

D. Insertion Sort

2. Để kiểm tra xem một đồ thị có chu trình hay không, thuật toán nào sau đây có thể được sử dụng?

A. Dijkstra

B. BFS hoặc DFS

C. Prim

D. Kruskal

3. Ưu điểm chính của việc sử dụng cây AVL so với cây nhị phân tìm kiếm thông thường là gì?

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

B. Độ phức tạp thời gian tìm kiếm luôn là O(log n)

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

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

4. Trong ngữ cảnh của cấu trúc dữ liệu, 'abstract data type' (ADT) là gì?

A. Một loại cấu trúc dữ liệu cụ thể như mảng hoặc danh sách liên kết

B. Một mô hình trừu tượng mô tả các thao tác và tính chất của dữ liệu mà không quan tâm đến cách cài đặt cụ thể

C. Một thuật toán sắp xếp cụ thể

D. Một phương pháp tối ưu hóa bộ nhớ

5. 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 hệ thống phân cấp, ví dụ như cây thư mục trong máy tính?

A. Hàng đợi

B. Ngăn xếp

C. Cây (Tree)

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

6. Độ 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?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

7. Cây khung nhỏ nhất (Minimum Spanning Tree) của một đồ thị liên thông có trọng số là gì?

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

B. Cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất

C. Chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần

D. Đồ thị con liên thông lớn nhất của đồ thị ban đầu

8. Khi nào thì thuật toán sắp xếp chọn (Selection Sort) được ưu tiên sử dụng?

A. Khi cần sắp xếp mảng lớn

B. Khi cần sắp xếp ổn định

C. Khi số lượng thao tác ghi (swaps) là yếu tố quan trọng cần tối ưu

D. Khi cần sắp xếp nhanh nhất có thể

9. Trong thuật toán tìm kiếm theo chiều sâu (DFS), cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh cần duyệt?

A. Hàng đợi

B. Ngăn xếp

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

D. Mảng

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

11. Thuật toán Floyd-Warshall được sử dụng để giải quyết bài toán nào?

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. Tìm luồng cực đại

D. Sắp xếp tô pô

12. Trong cấu trúc dữ liệu đồ 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ố dương

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

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

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

13. Khi nào thì việc sử dụng danh sách liên kết (Linked List) hiệu quả 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 thay đổi thường xuyên và khó dự đoán

C. Khi biết trước kích thước dữ liệu và ít thay đổi

D. Khi cần tối ưu hóa bộ nhớ sử dụng

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

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

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

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

D. Đồ thị

15. Ưu điểm của cấu trúc dữ liệu Heap (đống) là gì trong việc sắp xếp (Heap Sort)?

A. Độ phức tạp thời gian tốt nhất là O(n)

B. Sắp xếp tại chỗ (in-place sorting)

C. Ổn định (stable sorting)

D. Dễ dàng cài đặt

16. Trong cấu trúc dữ liệu cây, nút nào không có nút con được gọi là gì?

A. Nút gốc

B. Nút trung gian

C. Nút lá

D. Nút cha

17. Trong bảng băm, '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 hàm băm ánh xạ đến cùng một vị trí

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

D. Khi thao tác xóa một phần tử trong bảng băm

18. Trong cấu trúc dữ liệu đồ thị, ma trận kề (Adjacency Matrix) được sử dụng để biểu diễn điều gì?

A. Danh sách các đỉnh và cạnh của đồ thị

B. Sự kết nối trực tiếp giữa các cặp đỉnh

C. Trọng số của các cạnh trong đồ thị

D. Đường đi ngắn nhất giữa các đỉnh

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

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

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

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

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

20. Cấu trúc dữ liệu bảng băm (Hash Table) dựa trên nguyên tắc nào để lưu trữ và truy xuất dữ liệu?

A. Sắp xếp các phần tử theo thứ tự

B. Sử dụng hàm băm để ánh xạ khóa tới vị trí lưu trữ

C. Lưu trữ dữ liệu theo cấu trúc cây

D. Sử dụng con trỏ để liên kết các phần tử

21. Ư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 phần tử vào đầu danh sách nhanh hơn

22. Cấu trúc dữ liệu nào sau đây cho phép thêm và xóa phần tử ở cả hai đầu một cách hiệu quả?

A. Ngăn xếp

B. Hàng đợi

C. Deque (Double-ended Queue)

D. Mảng

23. Thuật toán sắp xếp nhanh (Quick Sort) có hiệu suất tốt nhất trong trường hợp nào?

A. Mảng đã được sắp xếp

B. Mảng có kích thước nhỏ

C. Mảng có các phần tử phân bố ngẫu nhiên

D. Mảng sắp xếp ngược

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

25. Khi nào thì nên sử dụng thuật toán tham lam (Greedy Algorithm)?

A. Khi cần tìm tất cả các nghiệm của bài toán

B. Khi bài toán có cấu trúc con tối ưu và tính chất lựa chọn tham lam

C. Khi cần đảm bảo tìm được nghiệm tối ưu trong mọi trường hợp

D. Khi bài toán có không gian nghiệm lớn

26. Phương pháp tiếp cận 'chia để trị' (Divide and Conquer) thường được sử dụng trong thuật toán nào sau đây?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

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

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

B. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm

C. Tìm chu trình Hamilton

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

28. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp trộn (Merge Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

29. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (Binary Search Tree), tính chất nào sau đây luôn đúng?

A. Tất cả các nút lá đều nằm ở cùng một mức

B. Giá trị của nút cha luôn lớn hơn giá trị của nút con bên trái

C. Giá trị của nút cha luôn nhỏ hơn giá trị của nút con bên phải

D. Giá trị của mọi nút trong cây con bên trái nhỏ hơn giá trị của nút gốc của cây con đó, và giá trị của mọi nút trong cây con bên phải lớn hơn giá trị của nút gốc của cây con đó

30. Độ phức tạp thời gian trung bình tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)