Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 05
Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Cấu Trúc Dữ Liệu Và Giải Thuật - Đề 05 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: Cho một mảng đã được sắp xếp tăng dần. Giải thuật nào sau đây có độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử cụ thể trong mả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 nhị phân (Binary Search)
- D. Tìm kiếm theo chiều sâu (Depth-First Search)
Câu 2: Cấu trúc dữ liệu nào sau đây 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 3: Để duyệt một cây nhị phân theo thứ tự trước (pre-order traversal), bạn cần thực hiện các bước nào theo thứ tự đúng?
- A. Thăm nút gốc, duyệt cây con trái, duyệt cây con phải
- B. Duyệt cây con trái, thăm nút gốc, duyệt cây con phải
- C. Duyệt cây con trái, duyệt cây con phải, thăm nút gốc
- D. Thăm nút gốc, duyệt cây con phải, duyệt cây con trái
Câu 4: Giải thuật 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 các mảng 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 chọn (Selection Sort)
- D. Sắp xếp nhanh (Quick Sort)
Câu 5: Trong cấu trúc dữ liệu đồ thị, 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 Prim
- B. Thuật toán Dijkstra
- C. Thuật toán Kruskal
- D. Thuật toán Floyd-Warshall
Câu 6: Ưu điểm chính của việc sử dụng danh sách liên kết so với mảng là gì?
- A. Truy cập phần tử ngẫu nhiên nhanh hơn
- B. Sử dụng bộ nhớ hiệu quả hơn khi số lượng phần tử cố định
- C. Kích thước có thể thay đổi động trong quá trình thực thi
- D. Tìm kiếm phần tử nhanh hơn trong danh sách đã sắp xếp
Câu 7: Độ phức tạp thời gian tốt nhất, trung bình và xấu nhất của thuật toán sắp xếp chèn (Insertion Sort) lần lượt là:
- A. O(n^2), O(n^2), O(n^2)
- B. O(n), O(n^2), O(n^2)
- C. O(log n), O(n log n), O(n^2)
- D. O(n), O(n log n), O(n log n)
Câu 8: 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. Mảng (Array)
- B. Hàng đợi (Queue)
- C. Cây (Tree)
- D. Đồ thị (Graph)
Câu 9: Thuật toán nào sau đây là một ví dụ của phương pháp "chia để trị" (divide and conquer)?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp chèn (Insertion Sort)
- C. Tìm kiếm tuyến tính (Linear Search)
- D. Sắp xếp trộn (Merge Sort)
Câu 10: Trong 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. Tìm kiếm một phần tử
- B. Duyệt cây theo thứ tự trước
- C. Tìm phần tử lớn nhất
- D. Xóa nút gốc
Câu 11: Xét 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 tìm kiếm theo chiều sâu (DFS)
- C. Thuật toán Kruskal
- D. Thuật toán tìm kiếm theo chiều rộng (BFS)
Câu 12: Để kiểm tra một biểu thức số học (ví dụ: (a+b)*c ) có hợp lệ về dấu ngoặc 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. Danh sách liên kết (Linked List)
- D. Cây nhị phân (Binary Tree)
Câu 13: 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ác giá trị băm giống nhau cho các khóa khác nhau
- B. Dễ dàng đảo ngược để tìm lại khóa gốc
- C. Chỉ tạo ra một số lượng nhỏ các giá trị băm
- D. Phân bố đều các khóa vào các ô băm khác nhau
Câu 14: 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. Max Heap (Heap cực đại)
- B. Min Heap (Heap cực tiểu)
- C. Cả Max Heap và Min Heap đều được
- D. Không sử dụng Heap
Câu 15: Khi nào thì thuật toán tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất?
- A. Khi mảng có kích thước nhỏ
- B. Khi phần tử cần tìm nằm ở đầu mảng
- C. Khi mảng đã được sắp xếp
- D. Khi mảng chứa nhiều phần tử trùng lặp
Câu 16: Cho một cây AVL. Điều gì luôn đúng với mọi nút trong cây AVL?
- A. Mỗi nút có tối đa 2 con
- B. Độ cao của cây con trái và cây con phải của mỗi nút chênh lệch nhau không quá 1
- C. Tất cả các nút lá đều ở cùng một mức
- D. Giá trị của nút con trái luôn nhỏ hơn giá trị của nút cha
Câu 17: Để 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?
- A. Mảng (Array)
- B. Danh sách liên kết (Linked List)
- C. Cây nhị phân tìm kiếm (BST)
- D. Heap (Heap)
Câu 18: 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. Số lượng đỉnh của đồ thị
- B. Mức độ kết nối của đồ thị
- C. Tổng số đỉnh và cạnh của đồ thị
- D. Trọng số của các cạnh (nếu có)
Câu 19: Thuật toán nào sau đây có thể được sử dụng để phát hiện chu trình trong một đồ thị có hướng?
- A. Tìm kiếm theo chiều sâu (DFS)
- B. Tìm kiếm theo chiều rộng (BFS)
- C. Thuật toán Dijkstra
- D. Thuật toán Prim
Câu 20: Trong bảng băm, kỹ thuật "separate chaining" (danh sách liên kết riêng rẽ) được sử dụng để giải quyết vấn đề gì?
- A. Tăng tốc độ tìm kiếm
- B. Xử lý xung đột băm
- C. Giảm bộ nhớ sử dụng
- D. Sắp xếp các phần tử trong bảng băm
Câu 21: Cho đoạn mã giả sau:
`function TimKiem(mang A, gia_tri x):
for i from 1 to length(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
- B. Tìm kiếm theo chiều rộng
- C. Tìm kiếm tuyến tính
- D. Tìm kiếm theo chiều sâu
Câu 22: Để đảo ngược một danh sách liên kết đơn, phương pháp nào sau đây hiệu quả nhất về mặt thời gian và không gian?
- A. Sử dụng mảng phụ trợ để lưu trữ các phần tử rồi đảo ngược
- B. Đệ quy
- C. Sao chép danh sách sang một danh sách liên kết mới theo thứ tự ngược lại
- D. Lặp và thay đổi con trỏ của các nút
Câu 23: Trong thuật toán tô màu đồ thị (graph coloring), mục tiêu chính là gì?
- A. Tìm đường đi ngắn nhất giữa các đỉnh
- B. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau nào có cùng màu và sử dụng ít màu nhất
- C. Phân loại các đỉnh vào các nhóm khác nhau
- D. Tìm chu trình Hamilton trong đồ thị
Câu 24: Cho một cây nhị phân đầy đủ (complete 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. 2^h
- C. 2^(h+1) - 1
- D. h^2
Câu 25: Trong thuật toán Floyd-Warshall, ma trận nào được sử dụng để lưu trữ khoảng cách ngắn nhất giữa tất cả các cặp đỉnh?
- A. Ma trận kề (Adjacency matrix)
- B. Ma trận trọng số (Weight matrix)
- C. Ma trận đường đi (Path matrix)
- D. Ma trận khoảng cách (Distance matrix)
Câu 26: Để thực hiện duyệt theo chiều rộng (BFS) trên đồ thị, 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. Mảng (Array)
- D. Danh sách liên kết (Linked List)
Câu 27: Độ 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 28: Trong cây đỏ-đen (red-black tree), thuộc tính nào sau đây không phải là thuộc tính của cây đỏ-đen?
- A. Mỗi nút là màu đỏ hoặc màu đen.
- B. Nút gốc luôn là màu đen.
- C. Mọi đường đi từ một nút đến các nút lá con cháu của nó đều chứa cùng số nút đen.
- D. Nút lá luôn là màu đỏ.
Câu 29: Cho một mảng số nguyên chưa sắp xếp. Yêu cầu tìm phần tử lớn thứ k trong mảng. Giải thuật nào sau đây có độ phức tạp thời gian trung bình tốt nhất để giải quyết vấn đề này?
- A. QuickSelect
- B. Sắp xếp toàn bộ mảng rồi lấy phần tử thứ k
- C. Tìm kiếm tuyến tính k lần
- D. Sử dụng Heap Sort
Câu 30: Xét bài toán "Cái túi" (Knapsack problem) phiên bản 0/1. Phương pháp nào sau đây thường được sử dụng để giải bài toán này một cách tối ưu?
- A. Thuật toán tham lam (Greedy algorithm)
- B. Quy hoạch động (Dynamic Programming)
- C. Tìm kiếm theo chiều sâu (DFS)
- D. Tìm kiếm theo chiều rộng (BFS)
