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

1. Trong tình huống nào thì cấu trúc dữ liệu ngăn xếp (Stack) được sử dụng phù hợp nhất?

A. Xử lý các tác vụ theo thứ tự ưu tiên

B. Quản lý các kết nối mạng

C. Kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức

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

2. Sự khác biệt chính giữa thuật toán duyệt đồ thị theo chiều rộng (BFS) và chiều sâu (DFS) là gì?

A. BFS sử dụng ngăn xếp, DFS sử dụng hàng đợi

B. BFS duyệt các đỉnh gần nguồn trước, DFS duyệt sâu xuống một nhánh trước khi sang nhánh khác

C. BFS nhanh hơn DFS

D. DFS luôn tìm đường đi ngắn nhất, BFS thì không

3. Thuật toán sắp xếp nào sau đây thường có độ phức tạp thời gian trung bình tốt nhất trong thực tế?

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

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

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

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

4. Cấu trúc dữ liệu Trie (cây tiền tố) thường được sử dụng chủ yếu cho ứng dụng nào?

A. Sắp xếp dữ liệu số

B. Lưu trữ và tìm kiếm chuỗi (ví dụ: gợi ý từ khóa, kiểm tra chính tả)

C. Nén dữ liệu văn bản

D. Biểu diễn đồ thị

5. Cấu trúc dữ liệu nào thường được sử dụng để hiện thực hàng đợi ưu tiên (priority queue)?

A. Mảng (Array)

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

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

D. Heap (Đống)

6. Trong tình huống nào thì cấu trúc dữ liệu hàng đợi (Queue) được sử dụng phù hợp nhất?

A. Đảo ngược thứ tự các phần tử

B. Mô phỏng hàng đợi chờ trong hệ thống (ví dụ: in ấn, xử lý yêu cầu)

C. Tìm kiếm theo chiều sâu trong đồ thị

D. Lưu trữ dữ liệu phân cấp

7. Độ phức tạp thời gian tốt nhất (best-case) để tìm kiếm một phần tử trong một mảng đã được 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(log n)

C. O(1)

D. O(n^2)

8. Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất là bao nhiêu?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

9. Hiện tượng `xung đột` (collision) trong bảng băm xảy ra khi nào?

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 truy xuất một khóa không tồn tại trong bảng

D. Khi hàm băm không hiệu quả

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. Ngăn xếp (Stack)

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

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

11. Cấu trúc dữ liệu Heap (đống) thường được sử dụng chủ yếu cho mục đích nào?

A. Lưu trữ dữ liệu có thứ tự tuyến tính

B. Hiện thực hàng đợi ưu tiên và thuật toán sắp xếp Heap Sort

C. Tìm kiếm nhanh trong dữ liệu lớn

D. Quản lý bộ nhớ động

12. Trong đệ quy (recursion), `trường hợp cơ sở` (base case) có vai trò gì?

A. Tăng hiệu suất của hàm đệ quy

B. Ngăn chặn đệ quy vô hạn và xác định điểm dừng của quá trình đệ quy

C. Xử lý lỗi trong quá trình đệ quy

D. Lưu trữ kết quả trung gian của đệ quy

13. Mục đích chính của kỹ thuật lập trình động (Dynamic Programming) là gì?

A. Tăng tốc độ thực thi chương trình bằng cách sử dụng đa luồng

B. Giải quyết các bài toán tối ưu bằng cách lưu trữ và tái sử dụng kết quả của các bài toán con

C. Giảm thiểu việc sử dụng bộ nhớ

D. Đơn giản hóa mã nguồn chương trình

14. Thuật toán sắp xếp nào sau đây được coi là `ổn định` (stable)?

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

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

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

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

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

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

16. Trong ngữ cảnh cấu trúc dữ liệu, thuật ngữ nào mô tả một phương pháp tổ chức và lưu trữ dữ liệu sao cho có thể truy cập và sử dụng chúng một cách hiệu quả?

A. Giải thuật

B. Biến

C. Cấu trúc dữ liệu

D. Hàm

17. Nguyên tắc chính của phương pháp thiết kế giải thuật `Chia để trị` (Divide and Conquer) là gì?

A. Giải quyết bài toán lớn bằng cách lặp đi lặp lại một thao tác đơn giản

B. Chia bài toán lớn thành các bài toán con nhỏ hơn, giải quyết chúng độc lập, rồi kết hợp kết quả

C. Tìm kiếm giải pháp tối ưu bằng cách thử tất cả các khả năng

D. Tiếp cận bài toán một cách tuần tự từ đầu đến cuối

18. Hàm băm (hash function) trong bảng băm (hash table) có vai trò chính là gì?

A. Sắp xếp dữ liệu theo thứ tự

B. Chuyển đổi khóa (key) thành chỉ số (index) để lưu trữ dữ liệu

C. Mã hóa dữ liệu để bảo mật

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

19. Thuật toán sắp xếp nào sau đây là thuật toán sắp xếp `tại chỗ` (in-place)?

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

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

C. Sắp xếp đếm (Counting Sort)

D. Sắp xếp cơ số (Radix Sort)

20. Nếu cần tìm kiếm một phần tử cụ thể trong một mảng đã được sắp xếp, thuật toán nào sau đây sẽ hiệu quả nhất về mặt thời gian?

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

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

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

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

21. Ưu điểm chính của việc sử dụng danh sách liên kết so với mảng khi thực hiện thao tác chèn hoặc xóa phần tử ở giữa danh sách là gì?

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

B. Không cần dịch chuyển các phần tử khác

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

D. Dễ dàng triển khai hơn

22. Thuật toán tham lam (Greedy Algorithm) thường được sử dụng khi nào?

A. Khi cần tìm giải pháp chính xác cho mọi trường hợp

B. Khi có thể đạt được giải pháp tối ưu tổng thể bằng cách đưa ra lựa chọn tối ưu cục bộ tại mỗi bước

C. Khi bài toán có cấu trúc con tối ưu và chồng lấp

D. Khi cần sắp xếp dữ liệu một cách nhanh chóng

23. Trong danh sách liên kết đơn, mỗi nút (node) chứa ít nhất:

A. Dữ liệu và con trỏ đến nút tiếp theo

B. Chỉ dữ liệu

C. Chỉ con trỏ đến nút tiếp theo

D. Dữ liệu và con trỏ đến nút trước đó

24. Đặc điểm nào sau đây KHÔNG phải là một tiêu chí đánh giá một giải thuật tốt?

A. Tính đúng đắn (Correctness)

B. Tính hiệu quả (Efficiency) về thời gian và không gian

C. Tính dễ đọc và dễ bảo trì (Readability and Maintainability)

D. Tính phức tạp trong mã nguồn (Code Complexity)

25. Ưu điểm chính của việc sử dụng cây nhị phân tìm kiếm (Binary Search Tree - BST) là gì?

A. Duyệt cây nhanh hơn

B. Tìm kiếm, chèn và xóa phần tử có độ phức tạp trung bình là O(log n)

C. Luôn cân bằng, đảm bảo hiệu suất tốt nhất

D. Sử dụng ít bộ nhớ hơn so với các cấu trúc dữ liệu khác

26. Nhược điểm chính của đệ quy (recursion) so với vòng lặp (iteration) là gì?

A. Khó đọc và bảo trì hơn

B. Chậm hơn do chi phí gọi hàm và có thể gây tràn bộ nhớ ngăn xếp (stack overflow)

C. Chỉ áp dụng được cho một số bài toán nhất định

D. Tiêu thụ nhiều bộ nhớ hơn

27. Thứ tự duyệt cây nào sau đây KHÔNG phải là một phương pháp duyệt cây nhị phân phổ biến?

A. Duyệt tiền thứ tự (Pre-order)

B. Duyệt trung thứ tự (In-order)

C. Duyệt hậu thứ tự (Post-order)

D. Duyệt rộng theo chiều sâu (Depth-first breadth)

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

A. Một kiểu dữ liệu cơ bản được tích hợp sẵn trong ngôn ngữ lập trình

B. Một mô hình toán học cho các kiểu dữ liệu, định nghĩa các thao tác có thể thực hiện trên dữ liệu và tính chất của chúng, mà không chỉ rõ cách hiện thực

C. Một phương pháp để mã hóa dữ liệu

D. Một công cụ để tối ưu hóa bộ nhớ sử dụng

29. Thuật toán Dijkstra chủ yếu được sử dụng để giải quyết loại bài toán nào?

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

B. Tìm đườ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. Sắp xếp các đỉnh của đồ thị

D. Tìm chu trình Hamilton trong đồ thị

30. Độ phức tạp không gian (space complexity) của một thuật toán đo lường điều gì?

A. Thời gian cần thiết để thuật toán hoàn thành

B. Lượng bộ nhớ tối đa mà thuật toán sử dụng trong quá trình thực thi

C. Số lượng phép toán mà thuật toán thực hiện

D. Độ phức tạp của việc triển khai thuật toán