Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 10
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 10 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 tìm kiếm (Binary Search 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 (Binary Search) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 3: Xét đoạn mã giả sau:
```
function Process(arr):
n = length(arr)
for i from 1 to n:
for j from 1 to n:
print(arr[i] + arr[j])
```
Độ phức tạp thời gian của thuật toán `Process` là bao nhiêu?
- A. O(n)
- B. O(n log n)
- C. O(n^2)
- D. O(2^n)
Câu 4: Ư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 thông qua chỉ số
- B. Sử dụng bộ nhớ hiệu quả hơn cho dữ liệu tĩnh
- C. Dễ dàng cài đặt và quản lý hơn
- D. Kích thước có thể thay đổi động trong quá trình thực thi
Câu 5: 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) và thường được coi là hiệu quả nhất trong thực tế cho dữ liệu lớ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)
Câu 6: Cấu trúc dữ liệu nào 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. Hàng đợi (Queue)
- B. Cây (Tree)
- C. Ngăn xếp (Stack)
- D. Mảng băm (Hash Table)
Câu 7: Trong thuật toán sắp xếp trộn (Merge Sort), giai đoạn "trộn" (merge) hai mảng con đã sắp xếp có vai trò gì?
- A. Chia mảng ban đầu thành các mảng con
- B. So sánh các phần tử trong mảng con
- C. Kết hợp hai mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp
- D. Chọn phần tửPivot để phân vùng mảng
Câu 8: Cấu trúc dữ liệu hàng đợi (Queue) thường được ứng dụng trong trường hợp nào sau đây?
- A. Xử lý các yêu cầu theo thứ tự đến, ví dụ như hàng đợi in ấn
- B. Quản lý lịch sử các thao tác để hoàn tác (undo)
- C. Tìm kiếm đường đi trong đồ thị theo chiều sâu
- D. Lưu trữ dữ liệu có tính phân cấp
Câu 9: Giải thuật tìm kiếm theo chiều rộng (Breadth-First Search - BFS) thường sử dụng cấu trúc dữ liệu nào để quản lý các đỉnh sẽ được duyệt?
- A. Ngăn xếp (Stack)
- B. Cây nhị phân (Binary Tree)
- C. Danh sách liên kết (Linked List)
- D. Hàng đợi (Queue)
Câu 10: Hàm băm (Hash function) lý tưởng nên có thuộc tính nào để giảm thiểu xung đột (collision) trong bảng băm (Hash table)?
- A. Tính toán nhanh chóng
- B. Phân bố đều các khóa băm trong bảng
- C. Tạo ra giá trị băm duy nhất cho mỗi khóa
- D. Dễ dàng đảo ngược để khôi phục khóa gốc
Câu 11: Để kiểm tra xem một chuỗi 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. Ngăn xếp (Stack)
- B. Hàng đợi (Queue)
- C. Cây nhị phân tìm kiếm (Binary Search Tree)
- D. Mảng băm (Hash Table)
Câu 12: Trong cây nhị phân tìm kiếm (Binary Search Tree - BST), 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 (Pre-order traversal)
- B. Duyệt cây theo thứ tự sau (Post-order traversal)
- C. Tìm kiếm một nút (Search)
- D. Duyệt cây theo chiều rộng (Breadth-first traversal)
Câu 13: Thuật toán 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. 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 trộn (Merge Sort)
Câu 14: Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên (random access) đến các phần tử với độ phức tạp thời gian O(1)?
- A. Danh sách liên kết (Linked List)
- B. Mảng (Array)
- C. Hàng đợi (Queue)
- D. Ngăn xếp (Stack)
Câu 15: Trong thuật toán Dijkstra, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách từ đỉnh nguồn đến các đỉnh khác và ưu tiên chọn đỉnh có khoảng cách nhỏ nhất?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Hàng đợi ưu tiên (Priority Queue) hoặc Heap
- D. Mảng (Array)
Câu 16: Cho một mảng số nguyên chưa sắp xếp: [5, 2, 8, 1, 9, 4, 7]. Sau khi thực hiện một bước sắp xếp chèn (Insertion Sort) đầu tiên, mảng sẽ trở thành:
- A. [2, 5, 8, 1, 9, 4, 7]
- B. [2, 5, 8, 1, 9, 4, 7]
- C. [5, 2, 1, 8, 9, 4, 7]
- D. [1, 2, 5, 8, 9, 4, 7]
Câu 17: Để duyệt cây theo thứ tự giữa (In-order traversal) trong cây nhị phân tìm kiếm (BST), thứ tự các bước thực hiện là:
- A. Nút gốc -> Cây con trái -> Cây con phải
- B. Cây con phải -> Nút gốc -> Cây con trái
- C. Nút gốc -> Cây con phải -> Cây con trái
- D. Cây con trái -> Nút gốc -> Cây con phải
Câu 18: Độ 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 19: Trong danh sách liên kết đôi (Doubly Linked List), mỗi nút chứa bao nhiêu con trỏ liên kết?
- A. Một
- B. Hai
- C. Ba
- D. Không có con trỏ nào
Câu 20: Giải thuật tìm kiếm theo chiều sâu (Depth-First Search - DFS) thường được sử dụng để giải quyết các bài toán nào sau đây?
- A. Tìm đường đi ngắn nhất giữa hai đỉnh
- B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)
- C. Tìm kiếm trong không gian trạng thái rộng lớn theo chiều rộng
- D. Kiểm tra tính liên thông của đồ thị
Câu 21: Trong lập trình đệ quy, điều kiện dừng (base case) có vai trò gì?
- A. Tăng hiệu suất của giải thuật
- B. Đảm bảo giải thuật luôn trả về kết quả đúng
- C. Ngăn chặn đệ quy vô hạn và đảm bảo giải thuật kết thúc
- D. Đơn giản hóa mã nguồn
Câu 22: 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. Heap (Cây nhị phân Heap)
- C. Danh sách liên kết (Linked List)
- D. Ngăn xếp (Stack)
Câu 23: Cho một cây nhị phân đầy đủ (Full Binary Tree) có chiều cao h. Số lượng nút tối đa mà cây có thể chứa là bao nhiêu?
- A. h
- B. 2h
- C. h^2
- D. 2^(h+1) - 1
Câu 24: Trong thuật toán Quick Sort, kỹ thuật "phân vùng" (partitioning) có mục đích chính là gì?
- A. Trộn hai mảng con đã sắp xếp
- B. Chia mảng thành hai mảng con sao cho các phần tử nhỏ hơn pivot ở một bên và lớn hơn ở bên còn lại
- C. Tìm phần tử nhỏ nhất và lớn nhất trong mảng
- D. Hoán đổi các cặp phần tử liền kề
Câu 25: Để tìm kiếm một phần tử trong mảng chưa sắp xếp, thuật toán nào sau đây có độ phức tạp thời gian trung bình tốt nhất?
- A. Tìm kiếm tuyến tính (Linear Search)
- B. Tìm kiếm nhị phân (Binary Search)
- C. Tìm kiếm theo chiều rộng (BFS)
- D. Tìm kiếm theo chiều sâu (DFS)
Câu 26: Khi nào thì việc sử dụng bảng băm (Hash Table) trở nên kém hiệu quả nhất?
- A. Khi số lượng phần tử trong bảng rất nhỏ
- B. Khi hàm băm phân bố đều các khóa
- C. Khi có quá nhiều xung đột băm (hash collisions)
- D. Khi kích thước bảng băm được thiết kế tối ưu
Câu 27: Cho đồ thị vô hướng G = (V, E). Để kiểm tra xem có tồn tại đường đi giữa hai đỉnh u và v, thuật toán nào sau đây là phù hợp nhất?
- A. Thuật toán sắp xếp tô pô (Topological Sort)
- B. Thuật toán tìm kiếm theo chiều rộng (BFS) hoặc chiều sâu (DFS)
- C. Thuật toán Dijkstra
- D. Thuật toán Prim
Câu 28: Trong cây AVL, thao tác "xoay cây" (tree rotation) được sử dụng để làm gì?
- A. Tìm kiếm một nút nhanh hơn
- B. Xóa một nút hiệu quả hơn
- C. Chèn một nút vào vị trí thích hợp
- D. Duy trì tính cân bằng của cây sau khi chèn hoặc xóa nút
Câu 29: Phương pháp "chia để trị" (Divide and Conquer) là cơ sở của thuật toán sắp xếp nào sau đây?
- 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) và Sắp xếp nhanh (Quick Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 30: Để biểu diễn một đồ thị có số lượng cạnh ít hơn nhiều so với số lượng đỉnh bình phương (đồ thị thưa), cấu trúc dữ liệu nào sau đây là hiệu quả nhất về mặt bộ nhớ?
- A. Danh sách kề (Adjacency List)
- B. Ma trận kề (Adjacency Matrix)
- C. Mảng (Array)
- D. Tập hợp (Set)
