Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 01
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 01 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 (Binary Search) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 3: Cho 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ó giá trị cụ thể
Câu 4: 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 cho mảng lớ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 5: Trong cấu trúc dữ liệu đồ thị (Graph), thuật toán nào sau đây được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm?
- A. Thuật toán tìm kiếm theo chiều sâu (DFS)
- B. Thuật toán Dijkstra
- C. Thuật toán tìm kiếm theo chiều rộng (BFS)
- D. Thuật toán Prim
Câu 6: Ưu điểm chính của việc sử dụng 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. Sử dụng bộ nhớ hiệu quả hơn cho dữ liệu có kích thước cố định
- C. Chèn và xóa phần tử ở giữa danh sách hiệu quả hơn
- D. Dễ dàng cài đặt và quản lý bộ nhớ hơn
Câu 7: Để 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 là phù hợp nhất?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Cây nhị phân tìm kiếm (BST)
- D. Bảng băm (Hash Table)
Câu 8: 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. 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 9: 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 sau đây được sử dụng để quản lý các đỉnh sẽ được thăm?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Cây nhị phân tìm kiếm (BST)
- D. Danh sách liên kết (Linked List)
Câu 10: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp nhanh (Quick Sort) là:
- A. O(n)
- B. O(n log n)
- C. O(n^2)
- D. O(log n)
Câu 11: Cho đoạn mã giả sau:
```
function TimKiem(mang A, phan_tu x):
for i từ 1 đến độ_dài(A):
if A[i] == x:
return i
return -1
```
Đ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 (Binary Search)
- B. Tìm kiếm tuyến tính (Linear 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 12: 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. Danh sách liên kết đôi (Doubly Linked List)
- C. Hàng đợi (Queue)
- D. Mảng (Array)
Câu 13: Trong cây nhị phân tìm kiếm (BST), thứ tự duyệt nào sau đây sẽ cho ra các nút theo thứ tự tăng dần?
- A. Duyệt theo thứ tự trước (Pre-order traversal)
- B. Duyệt theo thứ tự sau (Post-order traversal)
- C. Duyệt theo thứ tự giữa (In-order traversal)
- D. Duyệt theo chiều rộng (Breadth-first traversal)
Câu 14: Hash Table (Bảng băm) thường được sử dụng để giải quyết vấn đề gì hiệu quả nhất?
- A. Tìm kiếm và truy xuất dữ liệu nhanh chóng theo khóa
- B. Sắp xếp dữ liệu theo thứ tự
- C. Lưu trữ dữ liệu có thứ tự phân cấp
- D. Quản lý dữ liệu có quan hệ tuyến tính
Câu 15: Thuật toán nào sau đây là một 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 trộn (Merge Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 16: Khi nào thì nên ưu tiên sử dụng thuật toán tìm kiếm nhị phân (Binary Search) thay vì tìm kiếm tuyến tính (Linear Search)?
- A. Khi kích thước dữ liệu nhỏ
- B. Khi dữ liệu thường xuyên được cập nhật
- C. Khi dữ liệu đã được sắp xếp
- D. Khi không gian bộ nhớ bị hạn chế
Câu 17: Cấu trúc dữ liệu nào sau đây phù hợp nhất để biểu diễn quan hệ "cha-con" trong một hệ thống phân cấp, ví dụ như cây thư mục trong hệ điều hành?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Hàng đợi (Queue)
- D. Cây (Tree)
Câu 18: Thuật toán Prim và Kruskal được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?
- A. Tìm đường đi ngắn nhất
- B. Tìm cây khung nhỏ nhất (MST)
- C. Duyệt đồ thị theo chiều sâu (DFS)
- D. Duyệt đồ thị theo chiều rộng (BFS)
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. Không có con trỏ nào
- C. Hai
- D. Tùy thuộc vào số lượng nút
Câu 20: Độ 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(n)
- C. O(log n)
- D. O(n log n)
Câu 21: 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 lượt sắp xếp nổi bọt (Bubble Sort), mảng sẽ trở thành:
- A. [1, 2, 4, 5, 7, 8, 9]
- B. [2, 5, 1, 8, 4, 7, 9]
- C. [2, 5, 1, 8, 4, 7, 9]
- D. [5, 2, 8, 1, 9, 4, 7]
Câu 22: Trong thuật toán Dijkstra, tập hợp nào sau đây lưu trữ các đỉnh mà đường đi ngắn nhất từ đỉnh nguồn đã được xác định?
- A. Hàng đợi ưu tiên chứa tất cả các đỉnh
- B. Ngăn xếp chứa các đỉnh đang xét
- C. Mảng chứa khoảng cách tạm thời đến các đỉnh
- D. Tập hợp các đỉnh đã được thăm
Câu 23: Hàm băm (Hash function) lý tưởng nên có đặc tính nào sau đây để giảm thiểu xung đột?
- A. Tính toán nhanh chóng nhưng dễ gây xung đột
- B. Phân phối đều các khóa trên bảng băm
- C. Luôn tạo ra các giá trị băm duy nhất cho mỗi khóa
- D. Phụ thuộc vào kích thước bảng băm
Câu 24: Để duyệt một cây nhị phân theo chiều sâu (Depth-First Traversal), cấu trúc dữ liệu nào sau đây thường được sử dụng một cách ngầm định (thông qua đệ quy) hoặc tường minh?
- 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 25: Trong thuật toán sắp xếp chèn (Insertion Sort), ở mỗi bước lặp, phần tử hiện tại được chèn vào vị trí thích hợp trong:
- A. Phần chưa sắp xếp của mảng
- B. Đầu mảng
- C. Phần đã được sắp xếp của mảng
- D. Cuối mảng
Câu 26: Một đồ thị vô hướng liên thông có 10 đỉnh. Số cạnh tối thiểu để đảm bảo đồ thị liên thông là:
Câu 27: Để cài đặ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 hiệu quả nhất?
- A. Mảng đã sắp xếp
- B. Danh sách liên kết
- C. Cây nhị phân tìm kiếm cân bằng
- D. Heap (Đống)
Câu 28: Giải thuật Floyd-Warshall được sử dụng để giải quyết bài toán nào?
- A. Tìm cây khung nhỏ nhất (MST)
- B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác
- C. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
- D. Duyệt đồ thị theo chiều rộng (BFS)
Câu 29: Trong cây nhị phân đầy đủ (Full Binary Tree) với chiều cao h, số lượng nút tối đa là bao nhiêu?
- A. 2^(h+1) - 1
- B. 2^h - 1
- C. 2^(h+1)
- D. 2^h
Câu 30: Khi phân tích độ phức tạp thuật toán, ký hiệu Big O (O-notation) thường mô tả điều gì?
- A. Thời gian thực hiện chính xác của thuật toán
- B. Không gian bộ nhớ tối thiểu cần thiết
- C. Thời gian thực hiện trung bình của thuật toán
- D. Tốc độ tăng trưởng của thời gian thực hiện hoặc không gian bộ nhớ theo kích thước đầu vào
