Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 02
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 02 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: Độ 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 TimKiem(mang A, gia_tri x):
for i from 1 to length(A) do
if A[i] == x then
return i
end if
end for
return -1
end function
```
Đoạn mã trên mô tả thuật toán tìm kiếm nào?
- A. Tìm kiếm nhị phân
- B. Tìm kiếm theo chiều rộng
- C. Tìm kiếm tuyến tính (Tuần tự)
- D. Tìm kiếm theo chiều sâu
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 cho dữ liệu tĩnh
- C. Dễ dàng cài đặt hơn
- D. Dễ dàng chèn và xóa phần tử ở vị trí bất kỳ
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ệ phân cấp, ví dụ như cây thư mục trong hệ điều hành?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Cây (Tree)
- D. Mảng băm (Hash Table)
Câu 6: 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à nhanh nhất trong thực tế cho mảng lớn?
- A. Sắp xếp chèn (Insertion Sort)
- B. Sắp xếp nhanh (Quick Sort)
- C. Sắp xếp nổi bọt (Bubble Sort)
- D. Sắp xếp chọn (Selection Sort)
Câu 7: Để kiểm tra xem một biểu thức ngoặc có hợp lệ hay không (ví dụ: `( [ { } ] )`), 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. Danh sách liên kết (Linked List)
- D. Cây nhị phân tìm kiếm (Binary Search Tree)
Câu 8: Trong một cây nhị phân tìm kiếm (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. Duyệt cây theo chiều rộng (Breadth-first traversal)
- D. Tìm kiếm một nút
Câu 9: Giải thuật nào sau đây là giải thuật tham lam (Greedy Algorithm)?
- A. Sắp xếp trộn (Merge Sort)
- B. Tìm kiếm nhị phân (Binary Search)
- C. Giải thuật Dijkstra
- D. Lập trình động (Dynamic Programming)
Câu 10: Hàm băm (Hash function) lý tưởng nên có tính chất nào sau đây để giảm thiểu xung đột?
- A. Luôn tạo ra cùng một giá trị băm cho các khóa khác nhau
- B. Phân phối đều các khóa vào các ô băm
- C. Dễ dàng đảo ngược để tìm lại khóa gốc
- D. Có độ phức tạp tính toán cao
Câu 11: Cho một mảng số nguyên chưa sắp xếp. Để tìm phần tử lớn thứ hai trong mảng, phương pháp hiệu quả nhất (về độ phức tạp thời gian) là gì?
- A. Sắp xếp mảng rồi lấy phần tử thứ hai từ cuối lên
- B. Sử dụng thuật toán sắp xếp nhanh và lấy phần tử thứ hai từ cuối lên
- C. Duyệt mảng nhiều lần để tìm phần tử lớn nhất rồi phần tử lớn thứ hai
- D. Duyệt mảng một lần và theo dõi hai giá trị lớn nhất
Câu 12: Cấu trúc dữ liệu nào sau đây hoạt động theo nguyên tắc FIFO (First 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 13: Độ 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 14: Để duyệt tất cả các đỉnh của một đồ thị, thuật toán nào sau đây thường được sử dụng?
- A. Tìm kiếm nhị phân (Binary Search)
- B. Tìm kiếm theo chiều sâu (DFS) hoặc tìm kiếm theo chiều rộng (BFS)
- C. Sắp xếp nhanh (Quick Sort)
- D. Giải thuật Dijkstra
Câu 15: Trong cây nhị phân cân bằng (ví dụ: cây AVL), mục đích của việc cân bằng cây là gì?
- A. Giảm độ phức tạp không gian lưu trữ cây
- B. Đơn giản hóa việc cài đặt các thao tác trên cây
- C. Đảm bảo độ phức tạp thời gian O(log n) cho các thao tác tìm kiếm, chèn, xóa
- D. Tăng tốc độ duyệt cây theo thứ tự trước, giữa, sau
Câu 16: Khi nào thì thuật toán sắp xếp chèn (Insertion Sort) hoạt động hiệu quả nhất?
- A. Khi mảng đã gần như được sắp xếp
- B. Khi mảng có kích thước rất lớn
- C. Khi cần sắp xếp mảng theo thứ tự ngược lại
- D. Không bao giờ, vì nó luôn chậm hơn các thuật toán khác
Câu 17: Để lưu trữ dữ liệu dạng key-value và cho phép tìm kiếm, chèn, xóa nhanh chóng (độ phức tạp trung bình O(1)), cấu trúc dữ liệu nào sau đây phù hợp nhất?
- A. Danh sách liên kết (Linked List)
- B. Cây nhị phân tìm kiếm (Binary Search Tree)
- C. Hàng đợi ưu tiên (Priority Queue)
- D. Bảng băm (Hash Table)
Câu 18: Thuật toán nào sau đây tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị có trọng số không âm?
- A. Thuật toán Kruskal
- B. Thuật toán Dijkstra
- C. Thuật toán Floyd-Warshall
- D. Thuật toán Ford-Bellman
Câu 19: Độ phức tạp thời gian trung bình của thao tác 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^2)
Câu 20: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt qua mảng, phần tử nào sẽ được đặt đúng vị trí cuối cùng (đã sắp xếp)?
- A. Phần tử nhỏ nhất
- B. Phần tử ở giữa
- C. Phần tử lớn nhất
- D. Không có phần tử nào được đặt đúng vị trí sau mỗi lần duyệt
Câu 21: Để biểu diễn một hàng đợi ưu tiên (Priority Queue), cấu trúc dữ liệu nào sau đây thường được sử dụng?
- A. Danh sách liên kết (Linked List)
- B. Heap (Cây nhị phân vun đống)
- C. Mảng băm (Hash Table)
- D. Cây nhị phân tìm kiếm (Binary Search Tree)
Câu 22: Giải thuật nào sau đây là ví dụ của kỹ thuật "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)
Câu 23: Trong biểu diễn đồ thị bằng danh sách kề (Adjacency List), bộ nhớ sử dụng phụ thuộc vào yếu tố nào?
- A. Chỉ số lượng đỉnh của đồ thị
- B. Kích thước dữ liệu của mỗi đỉnh
- C. Số lượng đỉnh và số lượng cạnh của đồ thị
- D. Độ phức tạp của thuật toán duyệt đồ thị
Câu 24: Để tìm kiếm một phần tử trong một mảng chưa được sắp xếp, thuật toán nào có độ phức tạp thời gian trung bình là O(n)?
- A. Tìm kiếm tuyến tính (Tuần tự)
- 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 25: Trong cây nhị phân tìm kiếm (BST), khi xóa một nút có hai con, nút nào thường được chọn để thay thế nút bị xóa?
- A. Nút gốc của cây
- B. Nút kế cận gần nhất (inorder successor hoặc predecessor)
- C. Nút lá bất kỳ
- D. Không cần thay thế, chỉ cần xóa nút
Câu 26: Cho một đồ thị vô hướng liên thông. Thuật toán nào sau đây tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST)?
- A. Thuật toán Dijkstra
- B. Thuật toán Floyd-Warshall
- C. Thuật toán Ford-Bellman
- D. Thuật toán Kruskal hoặc thuật toán Prim
Câu 27: Độ phức tạp thời gian trung bình của thao tác tìm kiếm trong bảng băm (Hash Table) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 28: Trong thuật toán sắp xếp nhanh (Quick Sort), yếu tố nào ảnh hưởng lớn nhất đến hiệu suất của thuật toán?
- A. Kích thước của mảng đầu vào
- B. Ngôn ngữ lập trình sử dụng
- C. Cách chọn phần tử chốt (pivot)
- D. Số lượng bộ nhớ cache của hệ thống
Câu 29: 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. Danh sách liên kết đơn (Singly Linked List)
- B. Mảng (Array)
- C. Hàng đợi (Queue)
- D. Ngăn xếp (Stack)
Câu 30: Để tìm chu trình Euler trong một đồ thị vô hướng liên thông, điều kiện cần và đủ là gì?
- A. Đồ thị phải là đồ thị đầy đủ
- B. Đồ thị phải là đồ thị có hướng
- C. Đồ thị không được chứa bất kỳ chu trình nào
- D. Tất cả các đỉnh của đồ thị phải có bậc chẵn
