Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 04
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 04 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. Danh sách liên kết (Linked List)
- C. Ngăn xếp (Stack)
- D. Cây nhị phân (Binary Tree)
Câu 2: Độ 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 là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 3: Cho đoạn mã giả sau:
```
function Process(array A):
n = length(A)
for i from 1 to n-1:
for j from 1 to n-i:
if A[j] > A[j+1]:
swap(A[j], A[j+1])
return A
```
Đoạn mã trên mô tả thuật toán sắp xếp nào?
- A. Sắp xếp chèn (Insertion Sort)
- B. Sắp xếp nổi bọt (Bubble Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nhanh (Quick Sort)
Câu 4: Ưu điểm chính của danh sách liên kết so với mảng là gì?
- A. Truy cập phần tử nhanh hơn
- B. Sử dụng bộ nhớ hiệu quả hơn khi biết trước kích thước
- C. Dễ dàng cài đặt hơn
- D. Kích thước có thể thay đổi động trong quá trình thực thi
Câu 5: Để duyệt cây theo thứ tự trước (pre-order traversal), thứ tự các bước thực hiện đúng là:
- A. Nút gốc -> Cây con trái -> Cây con phải
- B. Cây con trái -> Nút gốc -> Cây con phải
- C. Cây con trái -> Cây con phải -> Nút gốc
- D. Cây con phải -> Nút gốc -> Cây con trái
Câu 6: Giải thuật nào sau đây 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 chọn (Selection Sort)
- C. Sắp xếp trộn (Merge Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 7: Trong cấu trúc dữ liệu đồ thị, thuật toán BFS (Breadth-First Search) thường được sử dụng để:
- A. Tìm đường đi dài nhất giữa hai đỉnh
- B. Tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị không trọng số
- C. Phát hiện chu trình âm trong đồ thị
- D. Sắp xếp các đỉnh của đồ thị theo thứ tự topo
Câu 8: Hash table (bảng băm) sử dụng hàm băm để làm gì?
- A. Mã hóa dữ liệu trước khi lưu trữ
- B. Sắp xếp dữ liệu trong bảng
- C. Ánh xạ khóa thành chỉ số trong bảng
- D. Nén dữ liệu để tiết kiệm không gian
Câu 9: Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn 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. Ngăn xếp (Stack)
- D. Cây (Tree)
Câu 10: Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?
- 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. Heap Sort
Câu 11: Để 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 được sử dụng hiệu quả nhất?
- A. Hàng đợi (Queue)
- B. Danh sách liên kết (Linked List)
- C. Ngăn xếp (Stack)
- D. Cây nhị phân tìm kiếm (Binary Search Tree)
Câu 12: Trong thuật toán Quick Sort, kỹ thuật "chia để trị" (divide and conquer) được thể hiện qua việc:
- A. Lặp qua từng phần tử để so sánh
- B. Phân hoạch mảng thành các mảng con nhỏ hơn và sắp xếp chúng
- C. Chọn phần tử nhỏ nhất và đưa về đầu mảng
- D. Đổi chỗ các phần tử không đúng vị trí
Câu 13: Khi nào nên sử dụng danh sách liên kết đôi (doubly linked list) thay vì danh sách liên kết đơn (singly linked list)?
- A. Khi cần truy cập phần tử ngẫu nhiên nhanh hơn
- B. Khi cần tiết kiệm bộ nhớ
- C. Khi chỉ cần duyệt danh sách theo một chiều
- D. Khi cần duyệt danh sách theo cả hai chiều (tiến và lùi)
Câu 14: Trong cây nhị phân tìm kiếm (BST), thao tác tìm kiếm phần tử có độ phức tạp trung bình là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n^2)
Câu 15: Cho một hàng đợi (queue) rỗng. Thực hiện các thao tác sau: enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4), dequeue(). Hỏi sau các thao tác trên, phần tử nào sẽ ở đầu hàng đợi?
Câu 16: Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào trong đồ thị?
- A. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh khác
- B. Tìm đường đi dài nhất giữa hai đỉnh
- C. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)
- D. Kiểm tra tính liên thông của đồ thị
Câu 17: Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 18: Trong cây AVL, khi cây trở nên mất cân bằng, phép xoay cây (tree rotation) được sử dụng để:
- A. Tăng tốc độ tìm kiếm
- B. Khôi phục lại tính cân bằng của cây
- C. Giảm độ cao của cây
- D. Sắp xếp các nút trong cây
Câu 19: 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 (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 (Cây куча)
Câu 20: Cho một mảng chưa sắp xếp. Để tìm phần tử lớn thứ k, thuật toán nào sau đây thường có hiệu suất tốt nhất trong thực tế?
- A. Sắp xếp toàn bộ mảng và chọn phần tử thứ k
- B. Duyệt mảng k lần để tìm phần tử lớn nhất
- C. Quickselect (dựa trên Quick Sort)
- D. Merge Sort và chọn phần tử thứ k
Câu 21: Trong ngữ cảnh thuật toán, "tham lam" (greedy) nghĩa là gì?
- A. Luôn tìm kiếm tất cả các giải pháp có thể
- B. Đưa ra lựa chọn tối ưu nhất tại mỗi bước hiện tại
- C. Chia bài toán thành các bài toán con và giải chúng
- D. Lặp lại các bước cho đến khi đạt được kết quả
Câu 22: Để lưu trữ ma trận thưa (sparse matrix) một cách hiệu quả, cấu trúc dữ liệu nào sau đây thường được ưu tiên?
- A. Mảng hai chiều thông thường
- B. Cây nhị phân
- C. Danh sách liên kết hoặc mảng thưa (sparse array)
- D. Bảng băm
Câu 23: Trong thuật toán DFS (Depth-First Search) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh cần duyệt tiếp theo?
- 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 tìm kiếm (Binary Search Tree)
Câu 24: Độ phức tạp thời gian của phép toán chèn một phần tử vào đầu danh sách liên kết đơn là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 25: Cho một cây nhị phân đầy đủ (complete binary tree) có chiều cao h. Số nút tối đa mà cây có thể chứa là:
- A. h
- B. 2^h
- C. 2^(h+1) - 1
- D. h * 2
Câu 26: Trong thuật toán tìm kiếm nhị phân, điều kiện tiên quyết để thuật toán hoạt động đúng là gì?
- A. Dữ liệu phải là số nguyên
- B. Dữ liệu không được chứa phần tử trùng lặp
- C. Kích thước dữ liệu phải nhỏ
- D. Dữ liệu phải được sắp xếp
Câu 27: Phương pháp "quy hoạch động" (dynamic programming) thường được áp dụng để giải quyết các bài toán có tính chất:
- A. Bài toán có không gian nghiệm lớn và cần tìm kiếm ngẫu nhiên
- B. Bài toán có cấu trúc con tối ưu và các bài toán con chồng lấp
- C. Bài toán yêu cầu độ phức tạp thời gian tuyến tính
- D. Bài toán có thể chia nhỏ thành các bài toán con độc lập
Câu 28: Trong cây đỏ-đen (red-black tree), một loại cây nhị phân tự cân bằng, các nút được tô màu đỏ hoặc đen để đảm bảo:
- A. Tăng tốc độ truy cập nút đỏ
- B. Phân biệt nút lá và nút gốc
- C. Đảm bảo cây luôn cân bằng tương đối
- D. Giảm dung lượng lưu trữ của cây
Câu 29: Hàm băm tốt cần có tính chất nào sau đây để giảm thiểu xung đột?
- A. Tính toán nhanh
- B. Dễ cài đặt
- C. Tạo ra giá trị băm duy nhất cho mỗi khóa
- D. Phân phối đều các khóa vào các ô của bảng băm
Câu 30: Cho một đồ thị có hướng. Thuật toán topo sort (sắp xếp topo) được sử dụng để làm gì?
- A. Tạo ra một thứ tự tuyến tính của các đỉnh sao cho các cạnh đi từ trái sang phải
- B. Tìm chu trình trong đồ thị
- C. Tìm đường đi ngắn nhất trong đồ thị có hướng
- D. Phân hoạch đồ thị thành các thành phần liên thông mạnh
