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

1. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trong trường hợp xấu nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(1)

2. Thuật toán nào sau đây sử dụng phương pháp 'chia để trị' để tìm kiếm phần tử lớn thứ k trong một mảng chưa sắp xếp?

A. Tìm kiếm tuyến tính

B. Sắp xếp nổi bọt

C. Quickselect

D. Sắp xếp chèn

3. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong bảng băm với giải quyết xung đột bằng phương pháp xích (chaining) là bao nhiêu, giả sử các khóa được phân bố đều?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

4. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm tuyến tính là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

5. Ưu điểm chính của việc sử dụng danh sách liên kết so với mảng là gì?

A. Truy cập ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn khi kích thước không biết trước

C. Tìm kiếm nhanh hơn

D. Sắp xếp dễ dàng hơn

6. 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. Cây (Tree)

D. Ngăn xếp (Stack)

7. 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 kiếm

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

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

D. Bài toán duyệt đồ thị

8. Khi nào nên sử dụng thuật toán sắp xếp vun đống (Heap Sort) thay vì sắp xếp trộn (Merge Sort)?

A. Khi cần độ ổn định (stability)

B. Khi không gian bộ nhớ là một hạn chế

C. Khi dữ liệu đã gần được sắp xếp

D. Khi cần độ phức tạp thời gian tốt nhất

9. Thuật toán nào sau đây là một ví dụ về thuật toán chia để trị (Divide and Conquer)?

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

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

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

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

10. Trong một cây AVL, yếu tố cân bằng (balance factor) của một nút được định nghĩa là gì?

A. Số lượng nút con của nút đó

B. Hiệu giữa chiều cao của cây con trái và cây con phải

C. Tổng chiều cao của cây con trái và cây con phải

D. Chiều cao của cây

11. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên đến các phần tử?

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)

12. Trong thuật toán Dijkstra, cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ khoảng cách từ nút nguồn đến các nút khác?

A. Ngăn xếp

B. Hàng đợi ưu tiên

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

D. Mảng

13. Trong cây, nút nào không có nút con được gọi là gì?

A. Nút gốc (Root Node)

B. Nút lá (Leaf Node)

C. Nút cha (Parent Node)

D. Nút con (Child Node)

14. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán tìm kiếm theo chiều rộng (BFS)?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây (Tree)

D. Đồ thị (Graph)

15. Trong 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 O(h), với h là chiều cao của cây?

A. Duyệt theo chiều rộng (Breadth-First Search)

B. Tìm kiếm (Search)

C. Sắp xếp (Sort)

D. Đảo ngược (Reverse)

16. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai bảng băm (hash table)?

A. Cây nhị phân

B. Mảng

C. Đồ thị

D. Hàng đợi

17. Trong cây nhị phân, số lượng nút con tối đa mà một nút có thể có là bao nhiêu?

A. 1

B. 2

C. 3

D. Vô hạn

18. 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)?

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 trộn (Merge Sort)

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

19. Cấu trúc dữ liệu nào sau đây là một tập hợp các nút và các cạnh, trong đó mỗi cạnh kết nối hai nút?

A. Mảng (Array)

B. Ngăn xếp (Stack)

C. Đồ thị (Graph)

D. Hàng đợi (Queue)

20. Thuật toán nào sau đây thường được sử dụng để nén dữ liệu không mất mát?

A. JPEG

B. MPEG

C. Huffman coding

D. MP3

21. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ phân cấp?

A. Mảng

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

C. Cây

D. Bảng băm

22. Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình trong một đồ thị?

A. Tìm kiếm nhị phân

B. Tìm kiếm tuyến tính

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

D. Sắp xếp trộn

23. Trong cấu trúc dữ liệu đồ thị (Graph), điều gì đại diện cho mối quan hệ giữa hai đỉnh?

A. Nút (Node)

B. Cạnh (Edge)

C. Cây (Tree)

D. Danh sách (List)

24. Độ phức tạp thời gian để chèn một phần tử vào một mảng đã được sắp xếp là bao nhiêu, nếu phải duy trì thứ tự sắp xếp?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

25. Thuật toán nào sau đây được sử dụng để tìm cây bao trùm tối thiểu (minimum spanning tree) trong một đồ thị có trọng số?

A. Dijkstra

B. Floyd-Warshall

C. Prim

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

26. Trong thuật toán Floyd-Warshall, mục đích chính là gì?

A. Tìm đường đi ngắn nhất giữa hai nút cụ thể

B. Tìm cây bao trùm tối thiểu

C. Tìm đường đi ngắn nhất giữa tất cả các cặp nút

D. Sắp xếp các nút trong một đồ thị

27. Trong lập trình động (dynamic programming), kỹ thuật nào sau đây được sử dụng để tránh tính toán lại các giá trị đã biết?

A. Đệ quy

B. Chia để trị

C. Ghi nhớ (Memoization)

D. Tham lam

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

A. O(n)

B. O(log n)

C. O(n^2)

D. O(1)

29. Thuật toán sắp xếp nào sau đây hoạt động tốt nhất trên dữ liệu gần như đã được sắp xếp?

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

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

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

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

30. Cấu trúc dữ liệu nào sau đây cho phép cả chèn và xóa ở cả hai đầu?

A. Ngăn xếp

B. Hàng đợi

C. Deque (Double-ended queue)

D. Cây