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

1. Độ 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 nếu các xung đột được giải quyết hiệu quả?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

2. Độ phức tạp không gian của giải thuật sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

3. 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 (Binary Tree)

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

A. O(n^2)

B. O(n log n)

C. O(log n)

D. O(n)

5. Giải thuật sắp xếp nào sau đây hoạt động bằng cách chia mảng thành các nửa nhỏ hơn, sắp xếp từng nửa, và sau đó trộn các nửa đã sắp xếp lại?

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

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

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

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

6. Giải thuật nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa hai nút trong một đồ thị có trọng số không âm?

A. Tìm kiếm theo chiều sâu (Depth-First Search - DFS)

B. Tìm kiếm theo chiều rộng (Breadth-First Search - BFS)

C. Giải thuật Dijkstra

D. Giải thuật sắp xếp tô pô (Topological Sort)

7. Cấu trúc dữ liệu đồ thị (Graph) được sử dụng để mô hình hóa mối quan hệ giữa các đối tượng như thế nào?

A. Mối quan hệ thứ bậc (Hierarchical)

B. Mối quan hệ tuyến tính (Linear)

C. Mối quan hệ mạng lưới (Network)

D. Mối quan hệ tuần tự (Sequential)

8. Giải thuật nào sau đây là một ví dụ về giải thuật tham lam (Greedy Algorithm)?

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

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

C. Giải thuật Dijkstra

D. Tìm kiếm theo chiều sâu (Depth-First Search - DFS)

9. Giải thuật tìm kiếm theo chiều rộng (Breadth-First Search - BFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các nút cần thăm?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

10. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?

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

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

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

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

11. Trong cây nhị phân cân bằng (Balanced Binary Tree) như cây AVL hoặc cây đỏ-đen, mục đích chính của việc cân bằng cây là gì?

A. Giảm dung lượng bộ nhớ

B. Tăng tốc độ duyệt cây

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

D. Làm cho cây dễ cài đặt hơn

12. Trong cấu trúc dữ liệu đồ thị có hướng không chu trình (DAG), giải thuật sắp xếp tô pô (Topological Sort) được sử dụng để làm gì?

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

B. Tìm chu trình

C. Sắp xếp các đỉnh theo thứ tự tuyến tính sao cho với mọi cạnh (u, v), đỉnh u xuất hiện trước đỉnh v

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

13. Trong cấu trúc dữ liệu cây, nút gốc (root) là nút như thế nào?

A. Nút có bậc cao 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

14. 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 nút của đồ thị

B. Số lượng cạnh trong đồ thị

C. Sự tồn tại của cạnh giữa các cặp nút

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

15. Trong giải thuật tìm kiếm nhị phân (Binary Search), dữ liệu đầu vào cần phải có đặc điểm gì?

A. Đã được sắp xếp

B. Không có phần tử trùng lặp

C. Chỉ chứa số nguyên

D. Có kích thước nhỏ

16. Giải thuật nào sau đây thường được sử dụng để tìm chu trình trong đồ thị?

A. Giải thuật Dijkstra

B. Tìm kiếm theo chiều rộng (Breadth-First Search - BFS)

C. Tìm kiếm theo chiều sâu (Depth-First Search - DFS)

D. Sắp xếp tô pô (Topological Sort)

17. Phương pháp giải quyết xung đột nào sau đây thường được sử dụng trong bảng băm (Hash Table) để xử lý khi nhiều khóa băm vào cùng một vị trí?

A. Sắp xếp lại các khóa

B. Tuyến tính hóa (Linear Probing)

C. Thay thế khóa cũ bằng khóa mới

D. Xóa khóa cũ

18. Trong cây nhị phân tìm kiếm (Binary Search Tree), 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 cây theo thứ tự trước (Pre-order traversal)

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

C. Tìm kiếm một nút (Searching for a node)

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

19. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (Binary Search Tree), khi nào thì cây trở thành cây suy biến (skewed tree) và hiệu suất của các thao tác tìm kiếm trở nên kém nhất?

A. Khi cây chứa quá nhiều nút

B. Khi cây được cân bằng hoàn hảo

C. Khi các nút được thêm vào theo thứ tự đã sắp xếp

D. Khi cây chỉ chứa nút lá

20. Trong bảng băm (Hash Table), 'hàm băm' (hash function) có vai trò gì?

A. Sắp xếp các khóa

B. Tính toán địa chỉ lưu trữ cho khóa

C. Kiểm tra xem khóa đã tồn tại trong bảng chưa

D. Giải quyết xung đột khi có nhiều khóa cùng địa chỉ

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ử ngẫu nhiên nhanh hơn

C. Duyệt ngược danh sách dễ dàng hơn

D. Thêm và xóa phần tử ở đầu danh sách nhanh hơn

22. Cấu trúc dữ liệu nào sau đây 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. Ngăn xếp (Stack)

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

24. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian trung bình là O(n log n) và thường được sử dụng trong thực tế vì hiệu suất tốt?

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. Độ phức tạp không gian của giải thuật 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)

26. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một dấu ngoặc trong biểu thức toán học có hợp lệ (đóng mở đúng cặp) hay không?

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)

27. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn quan hệ 'cha-con' trong hệ thống phân cấp, ví dụ như cây thư mục trong hệ điều hành?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Cây (Tree)

D. Đồ thị (Graph)

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ì khi thêm hoặc xóa phần tử ở giữa danh sách?

A. Truy cập phần tử nhanh hơn

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

C. Thêm và xóa phần tử hiệu quả hơn

D. Dễ dàng cài đặt hơn

29. Giải thuật sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự?

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

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

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

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

30. Giải thuật sắp xếp nào sau đây thường được sử dụng để sắp xếp các đối tượng lớn hoặc dữ liệu trên đĩa vì nó có tính ổn định và hiệu quả với dữ liệu lớ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 (Selection Sort)

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