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

1. Phương pháp `chia để trị` (Divide and Conquer) khác biệt với `lập trình động` (Dynamic Programming) chủ yếu ở điểm nào?

A. Chia để trị luôn đệ quy, lập trình động luôn lặp

B. Chia để trị giải quyết bài toán con độc lập, lập trình động giải quyết bài toán con chồng lấp

C. Chia để trị luôn nhanh hơn lập trình động

D. Chia để trị chỉ áp dụng cho bài toán sắp xếp, lập trình động cho bài toán tối ưu hóa

2. Trong cây B, bậc của cây (order) thường được dùng để chỉ điều gì?

A. Chiều cao tối đa của cây

B. Số lượng nút tối đa trong cây

C. Số lượng con tối đa mà mỗi nút (không phải lá) có thể có

D. Số lượng khóa tối đa có thể lưu trữ trong cây

3. Ư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 ngược danh sách dễ dàng hơn

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

4. Ưu điểm chính của cây AVL so với cây nhị phân tìm kiếm (BST) thông thường là gì?

A. Cây AVL dễ cài đặt hơn

B. Cây AVL luôn có độ phức tạp tìm kiếm O(log n) trong trường hợp xấu nhất

C. Cây AVL sử dụng ít bộ nhớ hơn

D. Cây AVL có thời gian thêm/xóa nút nhanh hơn

5. 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. Sắp xếp nổi bọt (Bubble Sort)

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

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

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

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

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

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

C. Heap (Vun đống)

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

7. Ứng dụng nào sau đây KHÔNG phải là ứng dụng phổ biến của ngăn xếp (stack)?

A. Quản lý bộ nhớ

B. Đánh giá biểu thức hậu tố

C. Duyệt đồ thị theo chiều rộng (BFS)

D. Gọi hàm đệ quy

8. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là O(n) do nguyên nhân chính nào?

A. Sử dụng đệ quy

B. Cần mảng phụ để trộn các nửa đã sắp xếp

C. Cần lưu trữ các chỉ số trung gian

D. Sử dụng cấu trúc dữ liệu cây

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

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

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

C. Tìm luồng cực đại (Maximum Flow)

D. Tìm chu trình Hamilton

10. Cấu trúc dữ liệu nào sau đây thích hợp nhất để biểu diễn mối quan hệ `nhiều-nhiều` giữa các đối tượng?

A. Mảng (Array)

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

C. Đồ thị (Graph)

D. Cây (Tree)

11. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) trong trường hợp dữ liệu đã được sắp xếp một phần là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

12. Cấu trúc dữ liệu nào sau đây thích hợp nhất để kiểm tra xem một từ có tồn tại trong một tập hợp lớn các từ hay không, với hiệu suất tìm kiếm nhanh?

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

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

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

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

13. Phương pháp lập trình động (Dynamic Programming) hiệu quả nhất khi giải quyết bài toán có tính chất nào sau đây?

A. Bài toán có thể chia nhỏ thành các bài toán con độc lập

B. Bài toán có cấu trúc con tối ưu và chồng lấp

C. Bài toán yêu cầu độ phức tạp thời gian tuyến tính

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

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

C. Ngăn xếp (Stack)

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

15. Trong cấu trúc dữ liệu cây nhị phân tìm kiếm (BST), 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 (Search)

D. Duyệt cây theo thứ tự giữa (In-order Traversal)

16. Phương pháp tiếp cận `tham lam` (Greedy) thường được sử dụng để giải quyết loại bài toán nào?

A. Bài toán tìm đường đi ngắn nhất trên đồ thị

B. Bài toán tối ưu hóa

C. Bài toán sắp xếp

D. Bài toán tìm kiếm

17. Trong thuật toán Dijkstra tìm đường đi ngắn nhất, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ đỉnh nguồn đến các đỉnh khác và nhanh chóng chọn đỉnh có khoảng cách nhỏ nhất?

A. Mảng

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

C. Hàng đợi ưu tiên (Priority Queue)

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

18. Trong cấu trúc dữ liệu đồ thị vô hướng, bậc của một đỉnh được định nghĩa là:

A. Số đỉnh kề với đỉnh đó

B. Số cạnh liên thuộc với đỉnh đó

C. Tổng trọng số của các cạnh liên thuộc với đỉnh đó

D. Chiều dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác

19. Trong cây nhị phân đầy đủ (Full Binary Tree) với chiều cao h, số nút tối đa có thể có là bao nhiêu?

A. h

B. 2^h

C. 2^(h+1) - 1

D. 2^h - 1

20. Cấu trúc dữ liệu nào sau đây sử dụng bộ nhớ không liên tục?

A. Mảng (Array)

B. Ngăn xếp (Stack) (dựa trên mảng)

C. Hàng đợi (Queue) (dựa trên mảng)

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

21. Giải thuật 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 chọn (Selection Sort)

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

22. Giải thuật nào sau đây có độ phức tạp thời gian tốt nhất, trung bình và xấu nhất đều là O(n)? (với giả định đầu vào phù hợp)

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

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

C. Sắp xếp đếm (Counting Sort)

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

23. 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. Dữ liệu phải được sắp xếp

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

C. Dữ liệu không được chứa phần tử trùng lặp

D. Kích thước dữ liệu phải là lũy thừa của 2

24. Thuật toán duyệt đồ thị theo chiều sâu (DFS) 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. Cây nhị phân tìm kiếm (Binary Search Tree)

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

25. Độ phức tạp thời gian của thao tác thêm một phần tử vào cuối hàng đợi (queue) sử dụng mảng vòng (circular array) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

26. Trong cấu trúc dữ liệu cây đỏ-đen (Red-Black Tree), thuộc tính nào sau đây KHÔNG đúng?

A. Mỗi nút có màu đỏ hoặc đen

B. Nút gốc luôn là màu đen

C. Tất cả các đường đi từ một nút đến các nút lá của nó chứa cùng một số lượng nút đen

D. Nút con của nút đỏ phải là nút đen

27. Trong bảng băm (Hash Table), hiện tượng `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 kích thước bảng băm quá nhỏ

D. Khi hàm băm không đủ tốt

28. Thuật toán sắp xếp nào sau đây có độ phức tạp không gian là O(1)?

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 đếm (Counting Sort)

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

A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị

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

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

D. Tìm chu trình Euler

30. Kỹ thuật `backtracking` (quay lui) thường được sử dụng để giải quyết loại bài toán nào?

A. Bài toán tìm kiếm đường đi ngắn nhất

B. Bài toán liệt kê tất cả các nghiệm

C. Bài toán tối ưu hóa bằng phương pháp tham lam

D. Bài toán sắp xếp mảng lớn