Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 07
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 06 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 một hàm đệ quy, điều kiện dừng (base case) đóng vai tròCritical nào?
- A. Tăng hiệu suất của chương trình bằng cách tối ưu hóa các lời gọi hàm.
- B. Đảm bảo rằng hàm luôn trả về một giá trị hợp lệ, ngay cả khi đầu vào không hợp lệ.
- C. Ngăn chặn đệ quy vô hạn bằng cách xác định trường hợp mà hàm không tự gọi lại chính nó.
- D. Cho phép hàm đệ quy gọi các hàm khác để thực hiện các tác vụ phức tạp hơn.
Câu 2: Xét đoạn mã giả sau:
```
function tinh_toan(n):
if n <= 1 then return 1
else return n * tinh_toan(n-2)
```
Giá trị trả về của `tinh_toan(5)` là bao nhiêu?
- A. 5
- B. 15
- C. 120
- D. Không xác định
Câu 3: Độ phức tạp thời gian tốt nhất (best-case time complexity) của thuật toán tìm kiếm tuyến tính (linear search) trong một mảng có kích thước n là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n^2)
Câu 4: Trong cấu trúc dữ liệu Stack, thao tác nào sau đây tuân thủ nguyên tắc LIFO (Last In, First Out)?
- A. Enqueue (thêm vào cuối)
- B. Dequeue (lấy ra khỏi đầu)
- C. Tìm kiếm phần tử nhỏ nhất
- D. Pop (lấy ra từ đỉnh)
Câu 5: Ứng dụng phổ biến nhất của cấu trúc dữ liệu Queue (hàng đợi) là gì?
- A. Quản lý các lời gọi hàm đệ quy
- B. Xử lý các yêu cầu in ấn trong hệ thống máy tính
- C. Đảo ngược một chuỗi ký tự
- D. Tìm kiếm theo chiều sâu trên đồ thị
Câu 6: Phát biểu nào sau đây mô tả đúng nhất về cấu trúc dữ liệu Linked List (danh sách liên kết)?
- A. Các phần tử được lưu trữ liên tiếp trong bộ nhớ, cho phép truy cập ngẫu nhiên nhanh chóng.
- B. Kích thước cố định và không thể thay đổi sau khi khởi tạo.
- C. Các phần tử được liên kết với nhau thông qua con trỏ, cho phép chèn và xóa hiệu quả.
- D. Chỉ cho phép truy cập các phần tử từ đầu danh sách.
Câu 7: Để kiểm tra xem một biểu thức ngoặc có hợp lệ (ví dụ: `( [ { } ] )`) hay không, cấu trúc dữ liệu nào sau đây là phù hợp nhất?
- A. Stack
- B. Queue
- C. Array
- D. Linked List
Câu 8: 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
- B. Insertion Sort
- C. Merge Sort
- D. Selection Sort
Câu 9: Trong cây nhị phân tìm kiếm (Binary Search Tree), thao tác tìm kiếm một phần tử có độ phức tạp thời gian trung bình là bao nhiêu?
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 10: 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 qua danh sách, 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. Bubble Sort
- B. Quick Sort
- C. Merge Sort
- D. Insertion Sort
Câu 11: Để duyệt một cây nhị phân theo thứ tự trước (pre-order traversal), thứ tự truy cập các nút là:
- A. Trái - Phải - Gốc
- B. Gốc - Trái - Phải
- C. Trái - Gốc - Phải
- D. Phải - Trái - Gốc
Câu 12: Cấu trúc dữ liệu nào sau đây hiệu quả nhất cho việc biểu diễn mối quan hệ "nhiều-nhiều" giữa các đối tượng?
- A. Mảng
- B. Cây nhị phân
- C. Danh sách liên kết
- D. Đồ thị (Graph)
Câu 13: Trong thuật toán tìm kiếm theo chiều rộng (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 thăm?
- A. Stack
- B. Queue
- C. Mảng
- D. Cây nhị phân
Câu 14: Độ phức tạp không gian (space complexity) của thuật toán Merge Sort chủ yếu phụ thuộc vào yếu tố nào?
- A. Số lượng phép so sánh
- B. Số lần hoán đổi phần tử
- C. Không gian bộ nhớ tạm thời cần thiết để trộn các mảng con
- D. Kích thước đầu vào của mảng ban đầu
Câu 15: Ư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. Cho phép duyệt danh sách theo cả hai chiều (từ đầu đến cuối và ngược lại)
- C. Truy cập phần tử ngẫu nhiên nhanh hơn
- D. Chèn và xóa phần tử ở đầu danh sách nhanh hơn
Câu 16: Trong thuật toán Quick Sort, kỹ thuật "chia để trị" (divide and conquer) được thể hiện rõ nhất ở bước nào?
- A. Chọn phần tử trụ (pivot)
- B. So sánh các phần tử
- C. Phân vùng (partition) mảng thành các mảng con
- D. Hoán đổi các phần tử
Câu 17: Cây nào sau đây đảm bảo thời gian tìm kiếm, chèn và xóa trung bình là O(log n) trong trường hợp xấu nhất?
- A. Cây nhị phân tìm kiếm thông thường
- B. Cây tìm kiếm tuần tự
- C. Cây khung tối thiểu
- D. Cây AVL
Câu 18: Hàm băm (hash function) tốt cần có thuộc tính nào sau đây để giảm thiểu xung đột (collisions) trong bảng băm?
- A. Tính toán nhanh chóng
- B. Phân phối đều các khóa băm trên phạm vi bảng băm
- C. Dễ dàng đảo ngược để khôi phục khóa gốc
- D. Luôn tạo ra các giá trị băm duy nhất cho các khóa khác nhau
Câu 19: Trong đồ thị có trọng số, thuật toán Dijkstra được sử dụng để giải quyết vấn đề gì?
- A. Tìm chu trình Euler
- B. Tìm cây khung tối thiểu
- C. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác
- D. Phát hiện chu trình âm
Câu 20: Phương pháp xử lý xung đột nào sau đây sử dụng danh sách liên kết để lưu trữ các phần tử có cùng giá trị băm trong bảng băm?
- A. Chaining (dây chuyền)
- B. Linear Probing (thăm dò tuyến tính)
- C. Quadratic Probing (thăm dò bậc hai)
- D. Double Hashing (băm kép)
Câu 21: Cho một mảng đã được sắp xếp `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`. Sử dụng thuật toán tìm kiếm nhị phân để tìm kiếm số 23. Số lần so sánh cần thực hiện là bao nhiêu?
Câu 22: Thuật toán Prim và Kruskal đều được sử dụng để giải quyết bài toán nào trên đồ thị?
- A. Tìm đường đi ngắn nhất
- B. Tìm cây khung tối thiểu (Minimum Spanning Tree)
- C. Tìm luồng cực đại
- D. Tô màu đồ thị
Câu 23: Trong biểu diễn đồ thị bằng danh sách kề (adjacency list), bộ nhớ cần thiết để lưu trữ đồ thị có V đỉnh và E cạnh là bao nhiêu (theo ký hiệu Big O)?
- A. O(V^2)
- B. O(V)
- C. O(V + E)
- D. O(E)
Câu 24: Để sắp xếp một danh sách các số nguyên lớn, thuật toán sắp xếp nào sau đây thường hiệu quả hơn về mặt thời gian thực tế?
- A. Bubble Sort
- B. Insertion Sort
- C. Selection Sort
- D. Quick Sort
Câu 25: Cấu trúc dữ liệu nào sau đây cho phép truy cập phần tử ở vị trí bất kỳ trong thời gian O(1)?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Stack
- D. Queue
Câu 26: Trong cây nhị phân cân bằng hoàn hảo (perfectly balanced binary tree) với n nút, chiều cao của cây là bao nhiêu (theo ký hiệu Big O)?
- A. O(n)
- B. O(log n)
- C. O(sqrt(n))
- D. O(n log n)
Câu 27: Giải thuật nào sau đây là ví dụ của thuật toán "tham lam" (greedy algorithm)?
- A. Tìm kiếm nhị phân
- B. Sắp xếp trộn
- C. Thuật toán Kruskal tìm cây khung tối thiểu
- D. Quy hoạch động
Câu 28: Để biểu diễn mối quan hệ thứ bậc (ví dụ: cây gia phả, cấu trúc thư mục), cấu trúc dữ liệu nào sau đây phù hợp nhất?
- A. Queue
- B. Cây (Tree)
- C. Graph
- D. Linked List
Câu 29: Khi nào thì nên ưu tiên sử dụng thuật toán Insertion Sort thay vì Merge Sort?
- A. Khi dữ liệu đầu vào gần như đã được sắp xếp
- B. Khi cần độ phức tạp thời gian tốt nhất trong mọi trường hợp
- C. Khi không gian bộ nhớ là yếu tố hạn chế nghiêm trọng
- D. Khi kích thước dữ liệu đầu vào rất lớn
Câu 30: Trong lập trình động (dynamic programming), kỹ thuật "ghi nhớ" (memoization) được sử dụng để làm gì?
- A. Tăng độ phức tạp không gian của thuật toán
- B. Giảm độ phức tạp thời gian bằng cách tính toán lại các bài toán con
- C. Đảm bảo tính đúng đắn của thuật toán
- D. Giảm độ phức tạp thời gian 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 đã giải
