Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 08
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật 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 (best-case time complexity) để 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 cân bằng (AVL tree). Chiều cao tối đa của cây AVL với N nút được giới hạn bởi:
- A. O(N)
- B. O(log N)
- C. O(N log N)
- D. O(N^2)
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à 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 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 5: Trong biểu diễn đồ thị bằng danh sách kề (Adjacency List), cấu trúc dữ liệu nào thường được sử dụng để lưu trữ danh sách các đỉnh kề của mỗi đỉnh?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Ngăn xếp (Stack)
- D. Hàng đợi (Queue)
Câu 6: Giải thuật nào sau đây là một ví dụ của chiến lược "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 trộn (Merge Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 7: Để duyệt đồ thị theo chiều rộng (Breadth-First Search - BFS), 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. Ngăn xếp (Stack)
- C. Cây nhị phân (Binary Tree)
- D. Danh sách liên kết (Linked List)
Câu 8: Xét đ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
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 nội suy (Interpolation Search)
- C. Tìm kiếm theo chiều rộng (Breadth-First Search)
- D. Tìm kiếm tuyến tính (Linear Search)
Câu 9: Trong các thuật toán sắp xếp, thuật toán nào có độ phức tạp thời gian trường hợp xấu nhất (worst-case time complexity) là O(n^2)?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp trộn (Merge Sort)
- C. Sắp xếp nhanh (Quick Sort)
- D. Sắp xếp vun đống (Heap Sort)
Câu 10: Cấu trúc dữ liệu nào phù hợp nhất để 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. Đống (Heap)
- D. Cây nhị phân tìm kiếm (Binary Search Tree)
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 là phù hợp nhất?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Cây nhị phân (Binary Tree)
- D. Danh sách liên kết (Linked List)
Câu 12: Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào trong đồ thị?
- A. Tìm cây khung nhỏ nhất (Minimum Spanning Tree)
- B. Tìm luồng cực đại (Maximum Flow)
- C. Tìm đường đi ngắn nhất (Shortest Path)
- D. Tìm chu trình Hamilton (Hamiltonian Cycle)
Câu 13: Trong các phép toán trên danh sách liên kết đơn (Singly Linked List), phép toán nào có độ phức tạp thời gian O(1)?
- A. Tìm kiếm một phần tử
- B. Thêm một phần tử vào đầu danh sách
- C. Xóa một phần tử ở cuối danh sách
- D. Đảo ngược danh sách
Câu 14: Hàm băm (Hash function) tốt cần có thuộc tính nào sau đây để giảm thiểu xung đột (collision)?
- A. Tính toán chậm
- B. Luôn tạo ra giá trị băm giống nhau cho các khóa khác nhau
- C. Giá trị băm luôn là số nguyên tố
- D. Phân phối đều các khóa trong bảng băm
Câu 15: Độ phức tạp không gian (space complexity) 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 16: Cho một mảng số nguyên chưa sắp xếp. Giải thuật nào sau đây hiệu quả nhất để tìm phần tử lớn thứ k trong mảng?
- A. Sắp xếp toàn bộ mảng và chọn phần tử thứ k
- B. QuickSelect
- C. Tìm kiếm tuyến tính
- D. Tìm kiếm nhị phân
Câu 17: Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt bộ nhớ cache (cache memory) trong hệ thống máy tính?
- A. Mảng (Array)
- B. Cây nhị phân tìm kiếm (Binary Search Tree)
- C. Hàng đợi (Queue)
- D. Bảng băm (Hash Map)
Câu 18: Trong thuật toán Kruskal để tìm cây khung nhỏ nhất (Minimum Spanning Tree), chúng ta sử dụng cấu trúc dữ liệu nào để kiểm tra chu trình khi thêm cạnh?
- A. Hàng đợi (Queue)
- B. Ngăn xếp (Stack)
- C. Tập hợp rời nhau (Disjoint Set/Union-Find)
- D. Danh sách liên kết (Linked List)
Câu 19: Cho một cây nhị phân tìm kiếm (BST). Thao tác nào sau đây có thể làm mất tính chất BST của cây?
- A. Tìm kiếm một nút
- B. Chèn một nút mới
- C. Xóa một nút lá
- D. Thay đổi khóa của một nút bất kỳ
Câu 20: Giải thuật Floyd-Warshall đượ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 giữa tất cả các cặp đỉnh
- B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh khác
- C. Tìm cây khung nhỏ nhất
- D. Tìm luồng cực đại
Câu 21: Trong kỹ thuật lập trình động (Dynamic Programming), nguyên tắc "tính toán và lưu trữ kết quả" (memoization) nhằm mục đích chính là gì?
- A. Giảm độ phức tạp không gian
- B. Tăng tốc độ thực thi bằng cách tránh tính toán lại
- C. Đơn giản hóa mã nguồn
- D. Cải thiện khả năng đọc hiểu của code
Câu 22: Độ 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) với phương pháp giải quyết xung đột bằng danh sách liên kết (separate chaining) là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 23: 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 đơn (Singly Linked List)
- B. Danh sách liên kết đôi (Doubly Linked List)
- C. Mảng (Array)
- D. Hàng đợi (Queue)
Câu 24: Cho một mảng đã sắp xếp. Thuật toán nào sau đây hiệu quả nhất để kiểm tra xem một giá trị cụ thể có tồn tại trong mảng hay không?
- A. Tìm kiếm tuyến tính (Linear Search)
- B. Tìm kiếm theo chiều rộng (Breadth-First Search)
- C. Tìm kiếm theo chiều sâu (Depth-First Search)
- D. Tìm kiếm nhị phân (Binary Search)
Câu 25: Trong cây đỏ-đen (Red-Black Tree), thuộc tính nào sau đây luôn được duy trì để đảm bảo tính cân bằng của cây?
- A. Tất cả các nút đều có màu đỏ
- B. Mọi đường đi từ gốc đến nút lá đều chứa số lượng nút đen như nhau
- C. Chiều cao của cây luôn là số nguyên tố
- D. Nút gốc luôn có màu đỏ
Câu 26: Để thực hiện duyệt cây theo thứ tự sau (post-order traversal) trong cây nhị phân, thứ tự truy cập các nút là:
- A. Nút gốc -> Con trái -> Con phải
- B. Con trái -> Nút gốc -> Con phải
- C. Con trái -> Con phải -> Nút gốc
- D. Ngẫu nhiên
Câu 27: Trong thuật toán Prim để tìm cây khung nhỏ nhất (Minimum Spanning Tree), chúng ta bắt đầu từ một đỉnh tùy ý và lặp đi lặp lại việc chọn cạnh có trọng số nhỏ nhất kết nối cây hiện tại với một đỉnh chưa thuộc cây. Chiến lược này là:
- A. Tham lam (Greedy)
- B. Chia để trị (Divide and Conquer)
- C. Lập trình động (Dynamic Programming)
- D. Quay lui (Backtracking)
Câu 28: Giả sử bạn có một mảng gồm n phần tử. Bạn muốn sắp xếp mảng này bằng thuật toán sắp xếp chèn (Insertion Sort). Trong trường hợp mảng đã được sắp xếp ngược (giảm dần), độ phức tạp thời gian của Insertion Sort sẽ là:
- A. O(1)
- B. O(n log n)
- C. O(n^2)
- D. O(log n)
Câu 29: Trong cây Trie (cây tiền tố), cấu trúc dữ liệu này được tối ưu hóa cho thao tác nào?
- A. Sắp xếp số
- B. Tìm kiếm tiền tố của chuỗi
- C. Tìm đường đi ngắn nhất trong đồ thị
- D. Nén dữ liệu
Câu 30: Bạn cần lưu trữ dữ liệu về các sản phẩm trong một cửa hàng, với yêu cầu tìm kiếm sản phẩm nhanh chóng theo mã sản phẩm (là chuỗi ký tự). Cấu trúc dữ liệu nào sau đây là phù hợp nhất?
- 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. Bảng băm (Hash Table)
