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

1. Phương pháp 'quy hoạch động' (Dynamic Programming) thường được áp dụng để giải quyết các bài toán có tính chất gì?

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 yêu cầu tìm tất cả các nghiệm

C. Bài toán có cấu trúc con tối ưu (optimal substructure) và các bài toán con chồng chéo (overlapping subproblems)

D. Bài toán có thể giải quyết bằng phương pháp tham lam

2. Giải thuật nào sau đây thuộc loại 'chia để trị' (Divide and Conquer)?

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

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

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

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

3. 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 hệ điều hành?

A. Mảng (Array)

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

C. Cây (Tree)

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

4. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong hash table (bảng băm) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

5. Giải thuật sắp xếp nào sau đây ổn định (stable sort)?

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

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

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

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

6. 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. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

7. Trong cấu trúc dữ liệu cây nhị phân đầy đủ (Complete Binary Tree), nếu cây có chiều cao h (gốc có chiều cao 0), số lượng nút tối đa có thể có trong cây là:

A. h + 1

B. 2^h

C. 2^(h+1) - 1

D. 2^h - 1

8. Trong các cấu trúc dữ liệu sau, cấu trúc nào là phi tuyến tính?

A. Mảng (Array)

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

C. Hàng đợi (Queue)

D. Cây (Tree)

9. Thuật toán tìm kiếm 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 nút cần duyệt?

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)

10. 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) và thường được coi là nhanh nhất trong thực 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)

11. Ứng dụng phổ biến của hàng đợi ưu tiên (Priority Queue) là gì?

A. Quản lý lịch sử truy cập trang web

B. Lập lịch công việc trong hệ điều hành

C. Tìm kiếm đường đi ngắn nhất trong đồ thị bằng thuật toán BFS

D. Kiểm tra tính hợp lệ của biểu thức ngoặc

12. Để 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 hiệu quả?

A. Thuật toán sắp xếp tô pô (Topological Sort)

B. Thuật toán tìm kiếm theo chiều rộng (BFS)

C. Thuật toán tìm kiếm theo chiều sâu (DFS)

D. Thuật toán Dijkstra

13. Cho một mảng đã sắp xếp, thuật toán tìm kiếm nào hiệu quả nhất về mặt thời gian?

A. Tìm kiếm tuyến tính (Linear Search)

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

C. Tìm kiếm theo chiều rộng (BFS)

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

14. Độ phức tạp thời gian của thao tác chèn (insertion) vào mảng (array) ở vị trí đầu tiên là:

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

15. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) là gì?

A. Một cách cài đặt cụ thể của cấu trúc dữ liệu

B. Một mô hình toán học của cấu trúc dữ liệu, xác định các thao tác và tính chất của nó mà không quan tâm đến việc cài đặt

C. Một ngôn ngữ lập trình đặc biệt để thiết kế cấu trúc dữ liệu

D. Một công cụ để phân tích độ phức tạp của thuật toán

16. Phương pháp tiếp cận 'tham lam' (Greedy) trong thiết kế thuật toán thường được sử dụng khi nào?

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 chồng chéo (overlapping subproblems)

C. Khi có thể đưa ra quyết định tối ưu cục bộ tại mỗi bước với hy vọng đạt được nghiệm tối ưu toàn cục

D. Khi cần đảm bảo tìm ra nghiệm chính xác trong mọi trường hợp

17. Giải thuật nào sau đây không phải là thuật toán sắp xếp so sánh?

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

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

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

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

18. Thuật toán 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 đếm (Counting Sort)

19. Trong hash table (bảng băm), 'collision' (xung đột) xảy ra khi nào?

A. Khi bảng băm đầy

B. Khi hai khóa khác nhau được băm thành cùng một vị trí trong bảng

C. Khi một khóa không thể tìm thấy trong bảng

D. Khi kích thước bảng băm quá nhỏ

20. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân (Binary Search) trong trường hợp mảng đã được sắp xếp là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

21. Trong cây nhị phân tìm kiếm cân bằng (Balanced Binary Search Tree) như AVL tree hoặc Red-Black tree, mục đích chính của việc cân bằng là gì?

A. Giảm độ phức tạp không gian

B. Đảm bảo độ phức tạp thời gian trung bình cho các thao tác tìm kiếm, chèn, xóa là O(log n)

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

D. Đơn giản hóa việc cài đặt cây

22. Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

23. Thao tác nào sau đây không phải là thao tác cơ bản trên ngăn xếp (Stack)?

A. Push (Thêm phần tử)

B. Pop (Lấy phần tử)

C. Dequeue (Lấy phần tử khỏi hàng đợi)

D. Peek (Xem phần tử trên cùng)

24. 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. Giá trị của nút con trái lớn hơn nút cha

B. Giá trị của nút con phải nhỏ hơn nút cha

C. Giá trị của nút con trái nhỏ hơn hoặc bằng nút cha và giá trị của nút con phải lớn hơn nút cha

D. Giá trị của tất cả các nút trong cây là duy nhất

25. Trong đồ thị (Graph), duyệt theo chiều sâu (DFS - Depth-First Search) khác với duyệt theo chiều rộng (BFS - Breadth-First Search) ở điểm nào?

A. DFS luôn tìm đường đi ngắn nhất

B. DFS duyệt các nút ở cùng mức trước

C. DFS đi sâu vào một nhánh trước khi chuyển sang nhánh khác

D. DFS sử dụng hàng đợi, BFS sử dụng ngăn xếp

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

27. Ư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ì?

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 khi kích thước dữ liệu không cố định

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

D. Sắp xếp phần tử nhanh hơn

28. Hash table (Bảng băm) thường được sử dụng để làm gì?

A. Sắp xếp dữ liệu

B. Tìm kiếm và truy xuất dữ liệu nhanh chóng dựa trên khóa

C. Lưu trữ dữ liệu theo thứ tự tuyến tính

D. Quản lý bộ nhớ động

29. Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc FIFO (First-In, First-Out)?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

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

30. Trong cấu trúc dữ liệu đồ thị (Graph), ma trận kề (Adjacency Matrix) và danh sách kề (Adjacency List) khác nhau chủ yếu ở điểm nào?

A. Ma trận kề chỉ dùng cho đồ thị có hướng, danh sách kề cho đồ thị vô hướng

B. Ma trận kề sử dụng nhiều bộ nhớ hơn cho đồ thị thưa (sparse graph), danh sách kề hiệu quả hơn

C. Danh sách kề chỉ lưu trữ thông tin về đỉnh, ma trận kề lưu trữ cả cạnh và đỉnh

D. Ma trận kề nhanh hơn trong việc duyệt đồ thị, danh sách kề nhanh hơn trong việc kiểm tra sự tồn tại cạnh