Đề 12 – 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 (Binary Search Tree), 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 (Searching for a node)

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

2. Trong đồ thị vô hướng (Undirected Graph), bậc của một đỉnh là gì?

A. Số lượng đỉnh kề với đỉnh đó

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

C. Số lượng cạnh trong đồ thị

D. Số lượng đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác

3. Giải thuật nào sau đây là một ví dụ của kỹ thuật `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 nhanh (Quick Sort)

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

4. Trong biểu đồ (Graph), thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm?

A. Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS)

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

C. Thuật toán Dijkstra

D. Thuật toán Prim

5. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt bộ nhớ cache?

A. Mảng (Array)

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

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

D. Cây AVL

6. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian trường hợp xấu nhất là O(n^2) và thường không được khuyến khích sử dụng cho dữ liệu lớn?

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

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

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

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

7. Trong cây nhị phân cân bằng (ví dụ: cây AVL), mục đích của việc cân bằng cây là gì?

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

B. Tăng tốc độ duyệt cây theo thứ tự trước

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

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

8. Trong lập trình động (Dynamic Programming), kỹ thuật `ghi nhớ` (memoization) là gì?

A. Tối ưu hóa việc sử dụng bộ nhớ bằng cách giải phóng bộ nhớ không cần thiết

B. Lưu trữ kết quả của các bài toán con đã giải để tránh tính toán lại

C. Chia bài toán lớn thành các bài toán con độc lập

D. Sử dụng đệ quy để giải quyết bài toán

9. Hash collision (xung đột băm) xảy ra khi nào trong bảng băm?

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

B. Khi hai khóa khác nhau được băm thành cùng một chỉ số

C. Khi khóa không tồn tại trong bảng băm

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

10. Thuật toán duyệt đồ thị theo chiều rộng (BFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh cần duyệt?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Cây nhị phân (Binary Tree)

D. Mảng (Array)

11. Trong thuật toán tô màu đồ thị (Graph Coloring), mục tiêu là gì?

A. Tìm đường đi ngắn nhất trong đồ thị

B. Phân chia đồ thị thành các thành phần liên thông

C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau nào có cùng màu

D. Tìm cây khung tối thiểu của đồ thị

12. 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 sử dụng trong thực tế vì hiệu suất tố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)

13. Khi nào nên sử dụng hàng đợi ưu tiên (Priority Queue) thay vì hàng đợi thông thường (Queue)?

A. Khi cần đảm bảo thứ tự vào trước ra trước (FIFO)

B. Khi cần truy cập ngẫu nhiên đến các phần tử

C. Khi cần xử lý các phần tử theo độ ưu tiên

D. Khi cần tìm kiếm phần tử nhanh chóng

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

B. Hàng đợi (Queue)

C. Mảng (Array)

D. Ngăn xếp (Stack)

15. Trong thuật toán sắp xếp trộn (Merge Sort), quá trình `trộn` (merge) có vai trò gì?

A. Chia mảng thành các mảng con

B. So sánh các phần tử và đổi chỗ nếu cần

C. Kết hợp hai mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp

D. Tìm phần tử nhỏ nhất trong mảng

16. Cấu trúc dữ liệu nào sau đây thường được sử dụng để triển khai thuật toán Dijkstra?

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

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

D. Mảng (Array)

17. Thuật toán Prim và Kruskal đượ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 hai đỉnh

B. Tìm cây khung tối thiểu (Minimum Spanning Tree)

C. Tìm chu trình Euler trong đồ thị

D. Sắp xếp các đỉnh của đồ thị theo thứ tự topo

18. Thuật toán sắp xếp nào sau đây hoạt động tốt nhất (độ phức tạp thời gian gần như O(n)) khi dữ liệu đầu vào 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)

19. Đệ quy (Recursion) là gì trong lập trình?

A. Một kỹ thuật lập trình lặp đi lặp lại một khối lệnh

B. Một hàm gọi chính nó

C. Một cách tổ chức dữ liệu theo cấu trúc cây

D. Một phương pháp tối ưu hóa bộ 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) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

21. Ứng dụng nào sau đây không phải là ứng dụng phổ biến của đồ thị (Graph)?

A. Mạng xã hội

B. Hệ thống định tuyến đường đi (bản đồ)

C. Quản lý dữ liệu dạng bảng

D. Mạng máy tính

22. Cây khung tối thiểu (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là gì?

A. Đồ thị con chứa tất cả các đỉnh và có tổng trọng số cạnh lớn nhất

B. Đồ thị con chứa tất cả các đỉnh và có tổng trọng số cạnh nhỏ nhất, không chứa chu trình

C. Đồ thị con chứa một số đỉnh và có tổng trọng số cạnh nhỏ nhất

D. Đồ thị con chứa tất cả các đỉnh và có tổng trọng số cạnh nhỏ nhất, có thể chứa chu trình

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

A. Duyệt theo thứ tự trước (Pre-order traversal)

B. Duyệt theo thứ tự giữa (In-order traversal)

C. Duyệt theo thứ tự sau (Post-order traversal)

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

24. Độ phức tạp không gian của thuật toán sắp xếp chèn (Insertion Sort) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)

25. Ư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. Duyệt danh sách theo cả hai chiều

C. Truy cập phần tử nhanh hơn

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

26. Giải thuật nào sau đây được sử dụng để tìm kiếm một mẫu (pattern) trong một chuỗi văn bản (text)?

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

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

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

D. Thuật toán Dijkstra

27. Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ `cha-con` trong một hệ thống phân cấp?

A. Mảng (Array)

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

C. Cây (Tree)

D. Hàng đợi (Queue)

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

29. Ưu điểm chính của việc sử dụng thuật toán tìm kiếm nhị phân (Binary Search) so với tìm kiếm tuyến tính (Linear Search) là gì?

A. Tìm kiếm nhị phân có thể hoạt động trên dữ liệu chưa được sắp xếp

B. Tìm kiếm nhị phân có độ phức tạp thời gian tốt hơn cho dữ liệu lớn

C. Tìm kiếm nhị phân dễ cài đặt hơn

D. Tìm kiếm nhị phân sử dụng ít bộ nhớ hơn

30. Độ phức tạp thời gian để chèn một phần tử vào đầu danh sách liên kết đơn (Singly Linked List) là:

A. O(n)

B. O(log n)

C. O(n log n)

D. O(1)