Đề 1 – Đề 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 tốt nhất của thuật toán tìm kiếm nhị phân là gì?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

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

A. JPEG

B. MPEG

C. Huffman coding

D. MP3

3. Cấu trúc dữ liệu nào cho phép truy cập phần tử ở cả hai đầu?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Deque (Double-ended queue)

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

4. Hoạt động nào sau đây không phải là hoạt động cơ bản trên cấu trúc dữ liệu ngăn xếp (Stack)?

A. Push

B. Pop

C. Peek

D. Search

5. Trong biểu đồ, thuật toán nào được sử dụng để tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút khác?

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

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

C. Thuật toán Dijkstra

D. Thuật toán Prim

6. Thuật toán sắp xếp nào 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)

7. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

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

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây (Tree)

D. Đồ thị (Graph)

9. Cấu trúc dữ liệu nào sau đây là một ví dụ về cấu trúc dữ liệu phi tuyến tính?

A. Mảng (Array)

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

C. Ngăn xếp (Stack)

D. Đồ thị (Graph)

10. Cấu trúc dữ liệu nào hoạt động theo nguyên tắc LIFO (Last In, First Out)?

A. Hàng đợi (Queue)

B. Mảng (Array)

C. Ngăn xếp (Stack)

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

11. Cấu trúc dữ liệu nào thích hợp nhất để biểu diễn mối quan hệ phân cấp?

A. Hàng đợi (Queue)

B. Cây (Tree)

C. Mảng (Array)

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

12. 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 nổi bọt (Bubble Sort)

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

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

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

13. Trong cây nhị phân tìm kiếm (Binary Search Tree), thuộc tính nào sau đây luôn đúng?

A. Tất cả các nút bên trái lớn hơn nút gốc

B. Tất cả các nút bên phải nhỏ hơn nút gốc

C. Nút gốc không có con

D. Tất cả các nút bên trái nhỏ hơn nút gốc và tất cả các nút bên phải lớn hơn nút gốc

14. Kỹ thuật nào sau đây được sử dụng để giảm độ phức tạp không gian của thuật toán?

A. Đệ quy (Recursion)

B. Tham lam (Greedy)

C. Lập trình động (Dynamic Programming)

D. Bit manipulation

15. Thuật toán sắp xếp nào có độ phức tạp thời gian 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 Shell (Shell Sort)

16. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

17. Thuật toán nào sau đây được sử dụng để tìm kiếm mẫu trong một chuỗi?

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

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

C. Thuật toán Knuth-Morris-Pratt (KMP)

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

18. Độ phức tạp thời gian của thao tác tìm kiếm trong bảng băm (Hash Table) trong trường hợp tốt nhất là gì?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

19. Cấu trúc dữ liệu nào sau đây là phù hợp nhất để triển khai hàng đợi ưu tiên (Priority Queue)?

A. Mảng (Array)

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

C. Heap

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

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

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)

21. Trong một bảng băm (Hash Table) với độ phân giải xung đột bằng phương pháp dò tuyến tính (linear probing), điều gì xảy ra khi bảng đầy?

A. Chương trình bị lỗi

B. Phần tử mới được bỏ qua

C. Bảng băm được tự động tăng kích thước

D. Không thể chèn thêm phần tử nào

22. Cấu trúc dữ liệu nào sau đây là một ví dụ về cấu trúc dữ liệu trừu tượng (Abstract Data Type)?

A. Mảng (Array)

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

C. Ngăn xếp (Stack)

D. Số nguyên (Integer)

23. Trong lập trình động (Dynamic Programming), kỹ thuật nào được sử dụng để tránh tính toán lại các bài toán con đã giải?

A. Đệ quy (Recursion)

B. Tham lam (Greedy)

C. Ghi nhớ (Memoization)

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

24. Trong thuật toán tìm kiếm theo chiều sâu (Depth-First Search), cấu trúc dữ liệu nào được sử dụng để theo dõi các nút đã được thăm?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

C. Mảng (Array)

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

25. Độ phức tạp thời gian của thao tác chèn (insertion) vào một mảng đã được sắp xếp là gì?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

26. Loại cây nào tự cân bằng sau mỗi thao tác chèn và xóa?

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

B. Cây AVL

C. Cây B

D. Cây Huffman

27. Phương pháp nào sau đây thường được sử dụng để giải quyết xung đột trong bảng băm (Hash Table)?

A. Sắp xếp (Sorting)

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

C. Liên kết chuỗi (Chaining)

D. Đệ quy (Recursion)

28. Thuật toán nào sau đây thường được sử dụng để tìm cây bao trùm tối thiểu (Minimum Spanning Tree) trong một đồ thị?

A. Thuật toán Dijkstra

B. Thuật toán Floyd-Warshall

C. Thuật toán Kruskal

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

29. Trong cây đỏ-đen (Red-Black Tree), thuộc tính nào sau đây luôn đúng?

A. Tất cả các nút đều có màu đỏ

B. Tất cả các nút đều có màu đen

C. Đường đi từ bất kỳ nút nào đến các nút lá của nó đều chứa cùng một số lượng nút đen

D. Đường đi từ bất kỳ nút nào đến các nút lá của nó đều chứa cùng một số lượng nút đỏ

30. Ư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 xác định trước

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

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