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

1. 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 cây in-order

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

C. Chèn một nút ở cuối cây

D. Xóa nút gốc

2. Trong cây nhị phân cân bằng (Balanced Binary Tree), mục đích của việc cân bằng cây là gì?

A. Giảm số lượng nút trong cây.

B. Tăng tốc độ duyệt cây theo chiều rộng.

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

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

3. Thuật toán sắp xếp nào sau đây có độ ổn định (stability)?

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

B. Heap Sort (Sắp xếp heap)

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

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

4. Thuật toán 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 duyệt?

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

C. Heap (Heap)

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

5. Cấu trúc dữ liệu nào sau đây thường được sử dụng để quản lý bộ nhớ trong hệ điều hành?

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

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

D. Bitmap (Bản đồ bit)

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

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

C. Deque (Hàng đợi hai đầu)

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

7. Trong đồ thị, thành phần liên thông (connected component) là gì?

A. Một nút và tất cả các cạnh kề với nó.

B. Tập hợp các nút mà giữa chúng có đường đi.

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

D. Chu trình ngắn nhất trong đồ thị.

8. Độ phức tạp không gian (space complexity) của thuật toán sắp xếp trộn (Merge Sort) là:

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

9. Trong cấu trúc dữ liệu đồ thị, đồ thị vô hướng (undirected graph) khác với đồ thị có hướng (directed graph) ở điểm nào?

A. Số lượng nút.

B. Loại dữ liệu lưu trữ trong nút.

C. Hướng của các cạnh.

D. Cách biểu diễn đồ thị.

10. Thuật toán nào sau đây là một ví dụ của thuật toán `tham lam` (Greedy Algorithm)?

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

B. Dijkstra`s Algorithm (Thuật toán Dijkstra)

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

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

11. Cấu trúc dữ liệu nào sau đây thường được sử dụng để kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức toán học?

A. Queue (Hàng đợi)

B. Stack (Ngăn xếp)

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

D. Array (Mảng)

12. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên (random access) đến các phần tử với độ phức tạp thời gian O(1)?

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

B. Stack (Ngăn xếp)

C. Queue (Hàng đợi)

D. Array (Mảng)

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

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

B. Unsorted Array (Mảng chưa sắp xếp)

C. Sorted Array (Mảng đã sắp xếp)

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

14. Trong cây nhị phân đầy đủ (Full Binary Tree), mỗi nút (trừ nút lá) có bao nhiêu nút con?

A. 0 hoặc 1

B. 0 hoặc 2

C. 1 hoặc 2

D. Chỉ 2

15. Thuật toán sắp xếp nhanh (Quick Sort) dựa trên nguyên tắc nào?

A. Chia để trị (Divide and Conquer)

B. Tham lam (Greedy)

C. Quy hoạch động (Dynamic Programming)

D. Duyệt vét cạn (Brute Force)

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

A. Pre-order (Tiền thứ tự)

B. Post-order (Hậu thứ tự)

C. In-order (Trung thứ tự)

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

17. Trong đồ thị, chu trình Euler (Eulerian cycle) là gì?

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

B. Chu trình đi qua tất cả các cạnh mỗi cạnh đúng một lần.

C. Chu trình đi qua tất cả các nút mỗi nút đúng một lần.

D. Chu trình không chứa cạnh lặp lại.

18. Thuật toán sắp xếp nào sau đây có thể sắp xếp `tại chỗ` (in-place), tức là không cần thêm không gian bộ nhớ đáng kể?

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

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

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

D. Radix Sort (Sắp xếp cơ số)

19. Độ phức tạp thời gian xấu nhất (worst-case time complexity) 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(n^2)

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

B. Queue (Hàng đợi)

C. Heap (Heap)

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

21. Cấu trúc dữ liệu nào sau đây phù hợp nhất để xây dựng bộ nhớ cache (cache memory)?

A. Array (Mảng)

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

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

D. Tree (Cây)

22. 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. Queue (Hàng đợi)

B. Stack (Ngăn xếp)

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

D. Array (Mảng)

23. Trong cấu trúc dữ liệu dạng cây, nút gốc (root node) là nút:

A. Không có nút con.

B. Nằm ở mức cao nhất của cây.

C. Có nhiều nút cha nhất.

D. Nằm ở mức thấp nhất của cây.

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

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

25. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian trung bình (average-case time complexity) là O(n log n)?

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

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

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

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

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

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

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

C. Dijkstra`s Algorithm (Thuật toán Dijkstra)

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

27. Độ phức tạp thời gian tốt nhất (best-case time complexity) của thuật toán sắp xếp chèn (Insertion Sort) là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

28. 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?

A. Mảng (Array)

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

C. Cây (Tree)

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

29. Ư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ử 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ử ở giữa danh sách.

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

30. Trong cấu trúc dữ liệu đồ thị (Graph), cạnh (edge) biểu diễn điều gì?

A. Một nút trong đồ thị.

B. Mối quan hệ giữa hai nút.

C. Trọng số của một nút.

D. Hướng đi của một nút.