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

1. Trong cây nhị phân tìm kiếm (Binary Search Tree - BST), các nút có khóa nhỏ hơn khóa của nút gốc được đặt ở đâu?

A. Nút con bên phải

B. Nút con bên trái

C. Cả hai nút con trái và phải

D. Không có quy tắc cụ thể

2. Thuật toán tìm kiếm nào hiệu quả nhất trên một mảng đã được sắp xếp?

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

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

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

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

3. Đệ quy đuôi (tail recursion) là gì và tại sao nó quan trọng?

A. Một loại đệ quy gây ra lỗi tràn stack; Nó quan trọng vì cần tránh sử dụng

B. Một loại đệ quy mà lời gọi đệ quy là thao tác cuối cùng trong hàm; Nó quan trọng vì có thể được tối ưu hóa bởi trình biên dịch để tránh tràn stack

C. Một loại đệ quy chỉ sử dụng một tham số; Nó quan trọng vì đơn giản hơn

D. Một loại đệ quy luôn trả về giá trị 0; Nó quan trọng vì dễ kiểm tra

4. Phương pháp tiếp cận 'chia để trị' (Divide and Conquer) được sử dụng trong thuật toán sắp xếp nào sau đây?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

5. Cấu trúc dữ liệu nào phù hợp nhất để biểu diễn mối quan hệ phân cấp, ví dụ như cây gia phả hoặc 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)

6. Kỹ thuật 'ghi nhớ' (memoization) trong lập trình động (Dynamic Programming) được sử dụng để làm gì?

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

B. Tăng độ phức tạp thời gian

C. 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, từ đó cải thiện hiệu suất

D. Đảm bảo tính đúng đắn của thuật toán

7. Khi nào thì nên sử dụng thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) thay vì tìm kiếm theo chiều rộng (Breadth-First Search - BFS) trong đồ thị?

A. Khi muốn tìm đường đi ngắn nhất trong đồ thị không trọng số

B. Khi muốn tìm kiếm nhanh hơn các đỉnh ở xa đỉnh nguồn

C. Khi không gian tìm kiếm rất rộng và có khả năng đi sâu vào các nhánh không triển vọng

D. Khi muốn duyệt qua tất cả các đỉnh theo thứ tự khoảng cách từ đỉnh nguồn

8. Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi ngoặc có hợp lệ (ví dụ: '()[]{}' là hợp lệ, '([)]' là không hợp lệ) hay không?

A. Queue

B. Linked List

C. Stack

D. Hash Table

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

A. Stack (Ngăn xếp)

B. Queue (Hàng đợi)

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

D. Tree (Cây)

10. Ư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ử ngẫu nhiên nhanh hơn

B. Sử dụng bộ nhớ hiệu quả hơn cho dữ liệu có kích thước thay đổi

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

D. Sắp xếp phần tử nhanh hơn

11. Thuật toán nào sau đây KHÔNG thuộc nhóm thuật toán sắp xếp so sánh (comparison sort)?

A. Quick Sort

B. Merge Sort

C. Counting Sort

D. Heap Sort

12. Độ 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) với phương pháp xử lý xung đột tốt (ví dụ: separate chaining) là bao nhiêu?

A. O(n)

B. O(log n)

C. O(1)

D. O(n log n)

13. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) nào mô tả một tập hợp các phần tử mà việc thêm và loại bỏ phần tử chỉ có thể thực hiện ở một đầu?

A. Queue

B. Linked List

C. Stack

D. Array

14. Trong cấu trúc dữ liệu, thuật ngữ LIFO là viết tắt của nguyên tắc hoạt động nào?

A. Last In, First Out

B. Least Important, First Out

C. Largest In, First Out

D. Linear Index, First Out

15. Thuật toán Kruskal và Prim được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?

A. Tìm đường đi ngắn nhất

B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST)

C. Tìm chu trình Euler

D. Tìm chu trình Hamilton

16. Hoạt động nào sau đây KHÔNG phải là thao tác cơ bản trên Stack?

A. Push (Đẩy)

B. Pop (Lấy ra)

C. Peek (Xem đỉnh)

D. Search (Tìm kiếm)

17. Trong cấu trúc dữ liệu đồ thị (Graph), thuật ngữ 'đỉnh' (vertex) còn được gọi là gì?

A. Cạnh (Edge)

B. Nút (Node)

C. Đường đi (Path)

D. Chu trình (Cycle)

18. Trong ngữ cảnh của thuật toán, 'tham lam' (greedy) nghĩa là gì?

A. Luôn chọn phương án tốt nhất tại mỗi bước hiện tại với hy vọng đạt được kết quả tối ưu toàn cục

B. Luôn cố gắng tìm kiếm tất cả các giải pháp khả thi trước khi đưa ra quyết định

C. Luôn chọn phương án ngẫu nhiên

D. Luôn chọn phương án phức tạp nhất để đảm bảo tính chính xác

19. Trong bảng băm (Hash Table), 'xung đột' (collision) 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ố (index)

C. Khi cố gắng truy cập một chỉ số không hợp lệ

D. Khi xóa một phần tử khỏi bảng băm

20. Ứng dụng phổ biến nhất của hàng đợi ưu tiên (Priority Queue) là gì?

A. Quản lý bộ nhớ

B. Lập lịch công việc trong hệ điều hành

C. Tìm kiếm tuần tự trong mảng

D. Đảo ngược chuỗi ký tự

21. Trong ngôn ngữ lập trình, 'con trỏ' (pointer) có vai trò gì liên quan đến cấu trúc dữ liệu?

A. Tính toán địa chỉ bộ nhớ của biến

B. Lưu trữ giá trị của biến

C. Liên kết các nút trong các cấu trúc dữ liệu động như danh sách liên kết và cây

D. Kiểm soát luồng thực thi của chương trình

22. Ưu điểm chính của việc sử dụng cây AVL (AVL Tree) so với cây nhị phân tìm kiếm thông thường là gì?

A. Thời gian tìm kiếm trung bình nhanh hơn

B. Luôn đảm bảo cây cân bằng, giúp duy trì độ phức tạp thời gian O(log n) cho các thao tác tìm kiếm, chèn, xóa trong trường hợp xấu nhất

C. Dễ cài đặt hơn

D. Sử dụng ít bộ nhớ hơn

23. Độ 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à bao nhiêu?

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

24. Trong thuật toán Dijkstra, mục đích chính là tìm kiếm cái gì?

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

B. Đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm

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

D. Tất cả các đường đi có thể giữa hai đỉnh

25. Trong cây đỏ-đen (Red-Black Tree), quy tắc nào sau đây KHÔNG đúng?

A. Mỗi nút có màu đỏ hoặc đen

B. Nút gốc luôn có màu đen

C. Tất cả các đường đi từ một nút đến các nút lá (NIL) của nó đều chứa cùng số lượng nút đen

D. Nút con của một nút đỏ có thể là đỏ hoặc đen

26. Độ phức tạp không gian (space complexity) của thuật toán sắp xếp trộn (Merge Sort) chủ yếu đến từ đâu?

A. Các phép so sánh phần tử

B. Việc sử dụng đệ quy

C. Mảng tạm thời được sử dụng trong quá trình trộn

D. Số lượng phần tử đầu vào

27. Phương pháp lập trình 'đệ quy' (recursion) hoạt động dựa trên nguyên tắc nào?

A. Chia nhỏ bài toán thành các bài toán con có kích thước lớn hơn

B. Chia nhỏ bài toán thành các bài toán con tương tự nhưng có kích thước nhỏ hơn, và gọi lại chính hàm để giải các bài toán con đó

C. Giải bài toán bằng cách lặp đi lặp lại một khối lệnh cho đến khi đạt điều kiện dừng

D. Sử dụng cấu trúc dữ liệu mảng để lưu trữ và truy xuất dữ liệu

28. 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. Bubble Sort (Sắp xếp nổi bọt)

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

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

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

29. Trong đồ thị vô hướng (undirected graph), bậc của một đỉnh (degree of a vertex) là gì?

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

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

C. Số lượng cạnh liên kết với đỉnh đó

D. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác

30. Trong thuật toán sắp xếp nhanh (Quick Sort), việc chọn phần tử chốt (pivot) ảnh hưởng như thế nào đến hiệu suất của thuật toán?

A. Không ảnh hưởng gì

B. Chọn phần tử chốt tốt sẽ giúp giảm độ phức tạp không gian

C. Chọn phần tử chốt tốt (ví dụ như phần tử trung vị) giúp thuật toán đạt hiệu suất O(n log n) trung bình; chọn phần tử chốt kém (ví dụ như phần tử nhỏ nhất hoặc lớn nhất trong mảng đã sắp xếp) có thể dẫn đến trường hợp xấu nhất O(n^2)

D. Chọn phần tử chốt tốt luôn đảm bảo độ phức tạp thời gian O(n log n) trong mọi trường hợp