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

1. 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 đỉnh cần duyệt?

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)

2. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình tốt nhấ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)

3. Cây cân bằng (Balanced tree) như cây AVL hay cây đỏ-đen (Red-Black tree) được sử dụng để giải quyết vấn đề gì của cây nhị phân tìm kiếm thông thường?

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

B. Đảm bảo độ phức tạp thời gian tìm kiếm, chèn, xóa là O(log n) trong trường hợp xấu nhất.

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

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

4. Thao tác duyệt cây theo thứ tự trước (Preorder traversal) trong cây nhị phân được thực hiện như thế nào?

A. Duyệt cây con trái, duyệt nút gốc, duyệt cây con phải.

B. Duyệt nút gốc, duyệt cây con trái, duyệt cây con phải.

C. Duyệt cây con trái, duyệt cây con phải, duyệt nút gốc.

D. Duyệt nút gốc, duyệt cây con phải, duyệt cây con trái.

5. Độ phức tạp thời gian trung bình để tìm kiếm một phần tử trong một mảng đã sắp xếp bằng thuật toán tìm kiếm nhị phân là bao nhiêu?

A. O(n)

B. O(1)

C. O(log n)

D. O(n^2)

6. 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, ví dụ như cấu trúc 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. Bảng băm (Hash Table)

7. Bộ nhớ cache (Cache memory) thường được sử dụng để cải thiện hiệu suất truy cập dữ liệu. Nguyên tắc locality (tính cục bộ) nào được cache tận dụng?

A. Tính toàn vẹn dữ liệu (Data integrity)

B. Tính cục bộ thời gian (Temporal locality) và tính cục bộ không gian (Spatial locality)

C. Tính nhất quán dữ liệu (Data consistency)

D. Tính bảo mật dữ liệu (Data security)

8. Hash table (Bảng băm) sử dụng hàm băm (hash function) để làm gì?

A. Sắp xếp các phần tử trong bảng.

B. Chuyển đổi khóa (key) thành chỉ số (index) trong bảng.

C. Mã hóa dữ liệu trước khi lưu trữ.

D. Nén dữ liệu để tiết kiệm không gian.

9. 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 (Tree)

D. Đồ thị (Graph)

10. Ưu điểm chính của việc sử dụng cấu trúc dữ liệu phù hợp là gì?

A. Giảm độ phức tạp của thuật toán.

B. Tăng tốc độ phát triển phần mềm.

C. Tối ưu hóa việc sử dụng bộ nhớ và thời gian xử lý.

D. Đơn giản hóa việc thiết kế giao diện người dùng.

11. Đồ thị (Graph) được sử dụng để mô hình hóa mối quan hệ giữa các đối tượng. Loại đồ thị nào mà các cạnh có hướng?

A. Đồ thị vô hướng (Undirected Graph)

B. Đồ thị có hướng (Directed Graph)

C. Đồ thị đầy đủ (Complete Graph)

D. Đồ thị cây (Tree Graph)

12. Giải thuật 'chia để trị' (Divide and Conquer) hoạt động bằng cách nào?

A. Giải quyết bài toán trực tiếp mà không cần chia nhỏ.

B. Chia bài toán lớn thành các bài toán con nhỏ hơn, giải quyết các bài toán con một cách độc lập, sau đó kết hợp kết quả để được lời giải cho bài toán ban đầu.

C. Lặp lại một chuỗi các bước cho đến khi đạt được kết quả.

D. Tìm kiếm lời giải tốt nhất bằng cách thử tất cả các khả năng.

13. Trong cây Heap (đống), loại nào sau đây đảm bảo rằng nút gốc luôn có giá trị lớn nhất trong số tất cả các nút trong cây?

A. Min-Heap

B. Max-Heap

C. Binary Search Tree

D. AVL Tree

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

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

15. Trong cấu trúc dữ liệu đồ thị (Graph), chu trình Euler (Eulerian cycle) là gì?

A. Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần.

B. Đường đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần và quay trở lại đỉnh xuất phát.

C. Đường đi ngắn nhất giữa hai đỉnh trong đồ thị.

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

16. Xung đột (collision) trong bảng băm (hash table) xảy ra khi nào?

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

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

C. Khi hàm băm tạo ra chỉ số âm.

D. Khi dữ liệu được chèn vào bảng băm không theo thứ tự.

17. Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở đầu và cuối một cách hiệu quả?

A. Mảng (Array)

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

C. Hàng đợi hai đầu (Deque - Double-ended Queue)

D. Ngăn xếp (Stack)

18. Trong lập trình động (Dynamic Programming), kỹ thuật 'ghi nhớ' (memoization) dùng để làm gì?

A. Tối ưu hóa không gian bộ nhớ.

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. Đảm bảo tính đúng đắn của thuật toán.

19. 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. Enqueue (Thêm vào hàng đợi)

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

20. Thuật toán tham lam (Greedy algorithm) 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 đường đi ngắn nhất.

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

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

D. Bài toán tìm kiếm.

21. Trong thuật toán sắp xếp nhanh (Quick Sort), thao tác 'phân vùng' (partition) có vai trò gì?

A. Sắp xếp toàn bộ mảng.

B. Chia mảng thành hai phần: một phần chứa các phần tử nhỏ hơn pivot và phần còn lại chứa các phần tử lớn hơn pivot.

C. Tìm phần tử nhỏ nhất và lớn nhất trong mảng.

D. Trộn hai mảng đã sắp xếp lại với nhau.

22. Đâu là phát biểu đúng nhất về cấu trúc dữ liệu?

A. Cấu trúc dữ liệu là một cách tổ chức và lưu trữ dữ liệu trong máy tính để có thể truy cập và sử dụng dữ liệu một cách hiệu quả.

B. Cấu trúc dữ liệu là một thuật toán cụ thể để sắp xếp dữ liệu.

C. Cấu trúc dữ liệu chỉ liên quan đến việc lưu trữ dữ liệu trên ổ cứng.

D. Cấu trúc dữ liệu là một ngôn ngữ lập trình đặc biệt.

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

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

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

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

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

25. Danh sách liên kết đơn (Singly Linked List) khác với mảng (Array) ở điểm nào?

A. Danh sách liên kết đơn cho phép truy cập ngẫu nhiên các phần tử.

B. Danh sách liên kết đơn có kích thước cố định.

C. Danh sách liên kết đơn sử dụng bộ nhớ động để lưu trữ các phần tử.

D. Mảng dễ dàng chèn và xóa phần tử ở đầu danh sách hơn.

26. Trong thuật toán tìm kiếm theo chiều sâu (DFS - Depth-First Search), thứ tự duyệt các đỉnh phụ thuộc vào yếu tố nào?

A. Trọng số của các cạnh.

B. Thứ tự các đỉnh kề được xét đến.

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

D. Màu sắc của các đỉnh.

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

A. Một kiểu dữ liệu cụ thể được cài đặt trong một ngôn ngữ lập trình cụ thể.

B. Một mô hình toán học cho các kiểu dữ liệu với các thao tác được định nghĩa trên đó, độc lập với việc cài đặt cụ thể.

C. Một cách để biểu diễn dữ liệu trong bộ nhớ máy tính.

D. Một thuật toán cụ thể để xử lý dữ liệu.

28. 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 một đồ thị có trọng số không âm?

A. Thuật toán sắp xếp nổi bọt (Bubble Sort)

B. Thuật toán tìm kiếm nhị phân (Binary Search)

C. Thuật toán Dijkstra

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

29. Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm (hash table) là bao nhiêu, giả sử hàm băm tốt và phân bố đều?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

30. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(log n)