Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 09
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 09 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: Để thêm một phần tử vào cuối hàng đợi, thao tác nào sau đây được sử dụng?
- A. Pop
- B. Push
- C. Enqueue
- D. Dequeue
Câu 3: 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. Sắp xếp trộn (Merge Sort)
- B. Sắp xếp nổi bọt (Bubble Sort)
- C. Sắp xếp chèn (Insertion Sort)
- D. Sắp xếp chọn (Selection Sort)
Câu 4: Trong cây nhị phân tìm kiếm (BST), thao tác tìm kiếm một nút có giá trị X có độ phức tạp thời gian tốt nhất là bao nhiêu?
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(1)
Câu 5: Ư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
Câu 6: 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 nổi bọt (Bubble Sort)
- C. Sắp xếp nhanh (Quick Sort)
- D. Sắp xếp chọn (Selection Sort)
Câu 7: Độ phức tạp thời gian O(n^2) thường gặp ở thuật toán sắp xếp nào?
- A. Sắp xếp trộn (Merge Sort)
- B. Sắp xếp nổi bọt (Bubble Sort)
- C. Sắp xếp nhanh (Quick Sort)
- D. Sắp xếp Heap (Heap Sort)
Câu 8: Trong biểu diễn đồ thị, cấu trúc dữ liệu nào hiệu quả nhất để kiểm tra xem có cạnh nối giữa hai đỉnh u và v hay không?
- A. Ma trận kề (Adjacency Matrix)
- B. Danh sách kề (Adjacency List)
- C. Danh sách cạnh (Edge List)
- D. Mảng các đỉnh (Vertex Array)
Câu 9: Giải thuật duyệt đồ thị theo chiều rộng (BFS) sử dụng cấu trúc dữ liệu nào?
- A. Ngăn xếp (Stack)
- B. Cây nhị phân (Binary Tree)
- C. Hàng đợi (Queue)
- D. Danh sách liên kết (Linked List)
Câu 10: Hàm đệ quy tính giai thừa có điều kiện dừng là gì?
- A. n > 0
- B. n < 0
- C. n != 1
- D. n = 0 hoặc n = 1
Câu 11: Trong danh sách liên kết kép, 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 12: Cấu trúc dữ liệu nào sau đây phù hợp nhất để quản lý lịch sử truy cập web (back/forward)?
- A. Ngăn xếp (Stack)
- B. Hàng đợi (Queue)
- C. Cây nhị phân (Binary Tree)
- D. Mảng (Array)
Câu 13: Tìm kiếm nhị phân (Binary Search) yêu cầu dữ liệu phải được sắp xếp như thế nào?
- A. Sắp xếp ngẫu nhiên
- B. Không cần sắp xếp
- C. Sắp xếp tăng dần hoặc giảm dần
- D. Sắp xếp theo nhóm
Câu 14: Heap (vùng nhớ Heap) thường được sử dụng cho mục đích gì trong lập trình?
- A. Lưu trữ biến cục bộ
- B. Lưu trữ mã chương trình
- C. Quản lý ngăn xếp hàm gọi
- D. Cấp phát bộ nhớ động (dynamic memory allocation)
Câu 15: Trong thuật toán sắp xếp Heap Sort, cấu trúc dữ liệu Heap được sử dụng là loại Heap nào?
- A. Min-Heap
- B. Max-Heap
- C. Binary Search Tree
- D. AVL Tree
Câu 16: Độ phức tạp không gian của thuật toán sắp xếp trộn (Merge Sort) là bao nhiêu?
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 17: Cây AVL là loại cây nhị phân tìm kiếm tự cân bằng nào?
- A. Cây nhị phân tìm kiếm (Binary Search Tree)
- B. Cây khung nhỏ nhất (Minimum Spanning Tree)
- C. Cây quyết định (Decision Tree)
- D. Cây Trie (Prefix Tree)
Câu 18: Giải thuật duyệt cây nhị phân nào cho phép in ra các nút theo thứ tự tăng dần trong cây nhị phân tìm kiếm?
- A. Preorder
- B. Inorder
- C. Postorder
- D. Level order
Câu 19: Trong đồ thị vô hướng liên thông, cây khung nhỏ nhất (MST) là gì?
- A. Đồ thị con chứa tất cả các đỉnh và ít cạnh nhất
- B. Đường đi ngắn nhất giữa hai đỉnh bất kỳ
- C. Chu trình Euler đi qua tất cả các cạnh
- D. Cây con liên thông tất cả các đỉnh với tổng trọng số cạnh nhỏ nhất
Câu 20: Thuật toán Dijkstra dùng để giải bài toán nào?
- A. Tìm cây khung nhỏ nhất (MST)
- B. Duyệt đồ thị theo chiều rộng (BFS)
- C. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh khác trong đồ thị có trọng số không âm
- D. Tìm chu trình Hamilton
Câu 21: Để 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 phù hợp 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 (Binary Tree)
Câu 22: Trong thuật toán tìm kiếm theo chiều sâu (DFS), thứ tự duyệt các đỉnh được xác định bởi cấu trúc dữ liệu nào?
- A. Hàng đợi (Queue)
- B. Danh sách liên kết (Linked List)
- C. Cây nhị phân (Binary Tree)
- D. Ngăn xếp (Stack)
Câu 23: Giả sử bạn có một mảng đã sắp xếp. Thuật toán tìm kiếm nào hiệu quả nhất để tìm một phần tử trong mảng đó?
- 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 24: Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp chèn (Insertion Sort) là bao nhiêu?
- A. O(n)
- B. O(log n)
- C. O(n log n)
- D. O(n^2)
Câu 25: Trong cấu trúc dữ liệu đồ thị, chu trình (cycle) là gì?
- A. Đường đi ngắn nhất giữa hai đỉnh
- B. Tập hợp các đỉnh và cạnh liên thông
- C. Đường đi bắt đầu và kết thúc tại cùng một đỉnh
- D. Cây con bao phủ tất cả các đỉnh
Câu 26: 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 O(1)?
- A. Danh sách liên kết đơn (Singly Linked List)
- B. Danh sách liên kết kép (Doubly Linked List)
- C. Hàng đợi (Queue)
- D. Mảng (Array)
Câu 27: Giải thuật sắp xếp nào sau đây thường có hiệu suất tốt nhất trong thực tế, mặc dù độ phức tạp trung bình và xấu nhất đều là O(n log n)?
- A. Sắp xếp trộn (Merge Sort)
- B. Sắp xếp nhanh (Quick Sort)
- C. Sắp xếp Heap (Heap Sort)
- D. Sắp xếp chèn (Insertion Sort)
Câu 28: 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. h
- B. 2^h
- C. 2^(h+1) - 1
- D. h^2
Câu 29: Ứng dụng nào sau đây KHÔNG phải là ứng dụng phổ biến của hàng đợi (Queue)?
- A. Xử lý hàng đợi in ấn (Print queue)
- B. Lập lịch CPU (CPU scheduling)
- C. Duyệt đồ thị theo chiều rộng (BFS)
- D. Quản lý ngăn xếp hàm gọi (Function call stack management)
Câu 30: Cho đoạn mã giả sau: `function TimKiem(mang, phan_tu_can_tim): for i from 0 to length(mang) - 1: if mang[i] == phan_tu_can_tim: return true; return false;` Đoạn mã này mô tả thuật toán tìm kiếm nào?
- 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 nội suy (Interpolation Search)
- D. Tìm kiếm theo hàm băm (Hash Search)
