Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 03
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 03 bao gồm nhiều câu hỏi hay, bám sát chương trình. Cùng làm bài tập trắc nghiệm ngay.
Câu 1: Trong các cấu trúc dữ liệu sau, cấu trúc 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)
Câu 2: Xét đoạn mã giả sau:
```
function Process(queue):
while queue is not empty:
item = dequeue(queue)
print(item)
if item is a list:
for sub_item in item:
enqueue(queue, sub_item)
```
Nếu `queue` ban đầu chứa `[1, [2, 3], 4, [5]]`, đầu ra của `Process(queue)` sẽ là gì?
- A. 1 2 3 4 5
- B. 1 [2, 3] 4 [5]
- C. 1 2 3 4 5
- D. 5 4 3 2 1
Câu 3: Độ phức tạp thời gian tốt nhất để 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 (Binary Search) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 4: Trong các thuật toán sắp xếp sau, thuật toán nào có độ phức tạp thời gian trung bình là O(n log n)?
- A. Sắp xếp chèn (Insertion 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 (Selection Sort)
Câu 5: Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn mối quan hệ thứ bậc, 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)
Câu 6: Thao tác nào sau đây không phải là thao tác cơ bản trên một Stack?
- A. PUSH (Thêm phần tử vào đỉnh)
- B. POP (Lấy phần tử ra khỏi đỉnh)
- C. PEEK (Xem phần tử ở đỉnh)
- D. SEARCH (Tìm kiếm phần tử)
Câu 7: Ư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ử nhanh hơn bằng chỉ số
- B. Kích thước có thể thay đổi động trong quá trình thực thi
- C. Sử dụng bộ nhớ hiệu quả hơn cho dữ liệu có kích thước cố định
- D. Dễ dàng cài đặt và quản lý hơn
Câu 8: Trong thuật toán sắp xếp nhanh (Quick Sort), kỹ thuật phân hoạch (partitioning) đóng vai trò quan trọng. Mục đích chính của phân hoạch là gì?
- A. Sắp xếp toàn bộ mảng thành thứ tự tăng dần
- B. Tìm phần tử nhỏ nhất và lớn nhất trong mảng
- C. Chọn một phần tử chốt và chia mảng thành hai phần, một phần nhỏ hơn chốt và một phần lớn hơn chốt
- D. Đảo ngược thứ tự các phần tử trong mảng
Câu 9: Để kiểm tra xem một biểu thức ngoặc có hợp lệ hay không (ví dụ: `( [ { } ] )` là hợp lệ, `( [ ) ]` là không hợp lệ), cấu trúc dữ liệu nào sau đây được sử dụng hiệu quả nhất?
- A. Ngăn xếp (Stack)
- B. Hàng đợi (Queue)
- C. Mảng (Array)
- D. Danh sách liên kết (Linked List)
Câu 10: Giải thuật nào sau đây minh họa rõ nhất kỹ thuật "chia để trị" (Divide and Conquer)?
- A. Sắp xếp chèn (Insertion 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 (Selection Sort)
Câu 11: Độ phức tạp không gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n^2)
Câu 12: Hoạt động nào sau đây sử dụng hàng đợi (Queue) một cách hiệu quả nhất?
- A. Tính giai thừa của một số
- B. Duyệt cây theo chiều sâu (Depth-First Search)
- C. Quản lý hàng đợi in ấn trong máy tính
- D. Tìm kiếm nhị phân trong mảng đã sắp xếp
Câu 13: 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 (Preorder Traversal)
- B. Tìm kiếm một nút
- C. Duyệt cây theo thứ tự sau (Postorder Traversal)
- D. Duyệt cây theo chiều rộng (Breadth-First Traversal)
Câu 14: Giải thuật sắp xếp nào sau đây không ổn định (unstable sorting algorithm)?
- A. Sắp xếp chèn (Insertion Sort)
- B. Sắp xếp trộn (Merge Sort)
- C. Sắp xếp nhanh (Quick Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 15: Để biểu diễn một đồ thị (Graph), cấu trúc dữ liệu nào sau đây thường được sử dụng?
- A. Mảng một chiều
- B. Hàng đợi
- C. Ngăn xếp
- D. Danh sách kề (Adjacency List)
Câu 16: Trong thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS) trên đồ thị, cấu trúc dữ liệu nào được sử dụng để quản lý các đỉnh sẽ được duyệt?
- A. Ngăn xếp (Stack)
- B. Hàng đợi (Queue)
- C. Mảng (Array)
- D. Cây nhị phân (Binary Tree)
Câu 17: Hàm băm (Hash function) lý tưởng nên có thuộc tính nào sau đây?
- A. Luôn tạo ra cùng một giá trị băm cho các khóa khác nhau
- B. Tạo ra giá trị băm có thể đoán trước được
- C. Phân phối đều các khóa vào các ô băm khác nhau
- D. Tính toán giá trị băm rất phức tạp và tốn thời gian
Câu 18: Xung đột (collision) trong bảng băm (Hash Table) xảy ra khi nào?
- A. Hai khóa khác nhau được băm vào cùng một vị trí
- B. Bảng băm đã đầy
- C. Khóa không tồn tại trong bảng băm
- D. Hàm băm không hợp lệ
Câu 19: Giải thuật nào sau đây có độ phức tạp thời gian trung bình tốt nhất để tìm kiếm trong một bảng băm?
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 20: Cây khung tối thiểu (Minimum Spanning Tree - MST) của một đồ thị vô hướng, liên thông, có trọng số là gì?
- A. Đồ thị con liên thông chứa tất cả các đỉnh của đồ thị gốc
- B. Cây con của đồ thị gốc chứa tất cả các đỉnh
- C. Đồ thị con liên thông có số cạnh ít nhất
- D. Cây con liên thông chứa tất cả các đỉnh và có tổng trọng số các cạnh nhỏ nhất
Câu 21: 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. Sắp xếp các đỉnh của đồ thị
- C. Tìm cây khung tối thiểu (Minimum Spanning Tree)
- D. Tìm chu trình Euler trong đồ thị
Câu 22: Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào?
- A. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh còn lại trong đồ thị
- B. Tìm cây khung tối thiểu
- C. Tìm chu trình Hamilton
- D. Sắp xếp các cạnh của đồ thị
Câu 23: Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) trong trường hợp xấu nhất là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n^2)
Câu 24: Trong cấu trúc dữ liệu cây nhị phân (Binary Tree), duyệt theo thứ tự giữa (inorder traversal) thường được sử dụng để làm gì?
- A. Sao chép cấu trúc cây
- B. Duyệt các nút theo thứ tự tăng dần trong cây nhị phân tìm kiếm
- C. Tính chiều cao của cây
- D. Xóa tất cả các nút lá của cây
Câu 25: Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên đến các phần tử với độ phức tạp thời gian O(1)?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Hàng đợi (Queue)
- D. Ngăn xếp (Stack)
Câu 26: Phương pháp xử lý xung đột nào sau đây thường được sử dụng trong bảng băm?
- A. Sắp xếp lại bảng băm
- B. Xóa các phần tử gây xung đột
- C. Dây chuyền tách rời (Separate Chaining)
- D. Thay đổi hàm băm
Câu 27: Trong thuật toán sắp xếp trộn (Merge Sort), thao tác trộn (merge) hai mảng con đã sắp xếp có độ phức tạp thời gian là bao nhiêu?
- A. O(log n)
- B. O(n log n)
- C. O(n)
- D. O(n^2)
Câu 28: Cấu trúc dữ liệu nào sau đây phù hợp nhất để cài đặt thuật toán ưu tiên công việc (priority scheduling) trong hệ điều hành?
- A. Hàng đợi thông thường (Queue)
- B. Ngăn xếp (Stack)
- C. Danh sách liên kết (Linked List)
- D. Hàng đợi ưu tiên (Priority Queue)
Câu 29: Để duyệt đồ thị theo chiều sâu (Depth-First Search - DFS), cấu trúc dữ liệu nào sau đây được sử dụng để quản lý các đỉnh sẽ được duyệt?
- A. Ngăn xếp (Stack)
- B. Hàng đợi (Queue)
- C. Mảng (Array)
- D. Cây nhị phân (Binary Tree)
Câu 30: Cho một mảng số nguyên chưa sắp xếp. Giải thuật sắp xếp nào sau đây có hiệu suất tốt nhất trong trường hợp mảng gần như đã được sắp xếp?
- A. Sắp xếp nhanh (Quick Sort)
- B. Sắp xếp chèn (Insertion Sort)
- C. Sắp xếp trộn (Merge Sort)
- D. Sắp xếp chọn (Selection Sort)
