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

1. Trong thuật toán Quick Sort, việc lựa chọn phần tử chốt (pivot) có ảnh hưởng lớn đến hiệu suất của thuật toán. Cách chọn pivot nào sau đây thường cho hiệu suất tốt trong trường hợp trung bình?

A. Chọn phần tử đầu tiên của mảng.

B. Chọn phần tử cuối cùng của mảng.

C. Chọn phần tử ngẫu nhiên.

D. Chọn phần tử lớn nhất của mảng.

2. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông, vô hướng và có trọng số là gì?

A. Một cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.

B. Một cây bao gồm một phần các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.

C. Một cây bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.

D. Một đồ thị con liên thông không chứa chu trình.

3. Ưu điểm chính của 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 khi số lượng phần tử không cố định.

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

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

4. Trong cấu trúc dữ liệu mảng (Array), thao tác nào sau đây có độ phức tạp thời gian trung bình là O(1)?

A. Tìm kiếm một phần tử cụ thể.

B. Chèn một phần tử vào cuối mảng.

C. Xóa một phần tử ở đầu mảng.

D. Sắp xếp mảng.

5. Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác tìm kiếm một nút có giá trị cụ thể có độ phức tạp thời gian tốt nhất là bao nhiêu?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

6. Trong thuật toán Kruskal để tìm cây khung nhỏ nhất (MST), tiêu chí nào sau đây được sử dụng để chọn cạnh thêm vào MST?

A. Chọn cạnh có trọng số lớn nhất mà không tạo thành chu trình.

B. Chọn cạnh có trọng số nhỏ nhất mà không tạo thành chu trình.

C. Chọn cạnh kết nối đỉnh gần nhất với MST hiện tại.

D. Chọn cạnh bất kỳ chưa được xét.

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

8. Độ 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à O(n). Trường hợp nào dẫn đến độ phức tạp này?

A. Mảng đầu vào được sắp xếp ngược.

B. Mảng đầu vào đã được sắp xếp.

C. Mảng đầu vào chứa nhiều phần tử trùng lặp.

D. Mảng đầu vào có kích thước lớn.

9. Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là O(n). Điều này chủ yếu là do đâu?

A. Việc so sánh các phần tử.

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

C. Việc tạo ra mảng tạm để trộn.

D. Việc hoán đổi các phần tử tại chỗ.

10. Giải thuật nào sau đây là ví dụ của thuật toán tham lam (Greedy Algorithm)?

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

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

C. Thuật toán Dijkstra

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

11. Trong cây nhị phân hoàn chỉnh (Complete Binary Tree), chiều cao của cây có quan hệ như thế nào với số lượng nút (n)?

A. Chiều cao tỉ lệ thuận với n.

B. Chiều cao tỉ lệ nghịch với n.

C. Chiều cao tỉ lệ với logarit cơ số 2 của n.

D. Chiều cao không phụ thuộc vào n.

12. 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ây thư mục trong hệ điều hành?

A. Mảng (Array)

B. Hàng đợi (Queue)

C. Cây (Tree)

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

13. Trong kỹ thuật lập trình động (Dynamic Programming), nguyên tắc `tối ưu chồng lấp` (overlapping subproblems) nghĩa là gì?

A. Bài toán lớn có thể được chia thành các bài toán con độc lập.

B. Các bài toán con được giải quyết một lần và kết quả được lưu trữ để tái sử dụng.

C. Việc giải một bài toán con không ảnh hưởng đến việc giải các bài toán con khác.

D. Kết quả của bài toán con lớn hơn có thể được suy ra từ kết quả của bài toán con nhỏ hơn.

14. Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình trong đồ thị có hướng?

A. Thuật toán Dijkstra

B. Thuật toán Kruskal

C. Tìm kiếm theo chiều sâu (DFS)

D. Tìm kiếm theo chiều rộng (BFS)

15. Giải thuật sắp xếp nào sau đây thường được sử dụng trong thư viện chuẩn của nhiều ngôn ngữ lập trình vì hiệu suất tốt trong thực 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)

16. Ưu điểm chính của việc sử dụng 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 (từ đầu đến cuối và ngược lại).

C. Chèn và xóa phần tử nhanh hơn.

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

17. Giải thuật sắp xếp nào sau đây có độ phức tạp thời gian trung bình tốt nhất 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 nhanh (Quick Sort)

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

18. Trong cấu trúc dữ liệu đồ thị (Graph), biểu diễn nào sau đây phù hợp nhất để kiểm tra nhanh chóng xem có cạnh nối giữa hai đỉnh bất kỳ hay không?

A. Danh sách cạnh (Edge List)

B. Danh sách kề (Adjacency List)

C. Ma trận kề (Adjacency Matrix)

D. Mảng các đỉnh (Vertex Array)

19. Khi nào thì nên sử dụng giải thuật tìm kiếm tuyến tính (Linear Search) thay vì tìm kiếm nhị phân (Binary Search)?

A. Khi dữ liệu đã được sắp xếp.

B. Khi dữ liệu có kích thước lớn.

C. Khi dữ liệu chưa được sắp xếp và kích thước nhỏ.

D. Khi cần tìm kiếm nhiều lần trên cùng một tập dữ liệu.

20. 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 khóa khác nhau được băm vào cùng một vị trí trong bảng.

C. Khi khóa cần tìm không có trong bảng.

D. Khi hàm băm trả về giá trị âm.

21. Trong thuật toán tìm kiếm nhị phân (Binary Search), dữ liệu đầu vào cần phải có đặc điểm gì?

A. Đã được sắp xếp.

B. Chứa các phần tử duy nhất.

C. Có kích thước nhỏ.

D. Là số nguyên.

22. Giải thuật nào sau đây thuộc loại `chia để trị` (Divide and Conquer)?

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

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

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

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

23. Giải thuật sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại việc so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự?

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

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

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

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

24. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa các đỉ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 tuyến tính (Linear Search)

C. Thuật toán Dijkstra

D. Thuật toán sắp xếp trộn (Merge Sort)

25. Ứng dụng nào sau đây sử dụng cấu trúc dữ liệu ngăn xếp (Stack) một cách điển hình?

A. Quản lý hàng đợi in.

B. Duyệt cây theo chiều rộng.

C. Tính toán biểu thức hậu tố (Postfix).

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

26. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt hàng đợi ưu tiên?

A. Mảng (Array)

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

C. Heap (Đống)

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

27. Khi nào thì thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS) được ưu tiên hơn thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) trong việc duyệt đồ thị?

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

B. Khi cần kiểm tra xem đồ thị có chu trình hay không.

C. Khi cần duyệt tất cả các đỉnh của đồ thị.

D. Khi cần tiết kiệm bộ nhớ.

28. Trong cấu trúc dữ liệu hàng đợi ưu tiên (Priority Queue), phần tử nào sẽ được lấy ra tiếp theo?

A. Phần tử được thêm vào đầu tiên.

B. Phần tử được thêm vào cuối cùng.

C. Phần tử có độ ưu tiên cao nhất.

D. Phần tử có độ ưu tiên thấp nhất.

29. Khi nào thì việc sử dụng bảng băm (Hash Table) hiệu quả hơn so với cây nhị phân tìm kiếm (Binary Search Tree) trong việc tìm kiếm, chèn và xóa phần tử?

A. Khi dữ liệu đã được sắp xếp.

B. Khi cần duyệt các phần tử theo thứ tự.

C. Khi số lượng phần tử rất lớn và cần tốc độ trung bình nhanh.

D. Khi cần tìm phần tử nhỏ nhất hoặc lớn nhất.

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

A. Ngăn xếp (Stack)

B. Hàng đợi (Queue)

C. Deque (Double-ended queue)

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