Đề 6 – Bài tập, đề thi trắc nghiệm online Cấu trúc dữ liệu và giải thuật

1. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian trung bình và xấu nhất đều là O(n^2)?

A. Quick Sort

B. Merge Sort

C. Bubble Sort

D. Heap Sort

2. 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 cây khung nhỏ nhất

C. Tìm luồng cực đại trong mạng

D. Tìm chu trình Euler

3. Hash Table (bảng băm) sử dụng hàm băm để làm gì?

A. Sắp xếp dữ liệu

B. Tìm kiếm dữ liệu tuần tự

C. Ánh xạ khóa (key) tới vị trí trong bảng

D. Nén dữ liệu

4. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian ổn định (stable)?

A. Quick Sort

B. Heap Sort

C. Selection Sort

D. Merge Sort

5. Giải thuật nào sau đây thường được sử dụng để duyệt đồ thị theo chiều rộng?

A. Depth-First Search (DFS)

B. Breadth-First Search (BFS)

C. Binary Search

D. Linear Search

6. Giải thuật duyệt đồ thị DFS thường sử dụng cấu trúc dữ liệu nào để hỗ trợ?

A. Queue

B. Stack

C. Heap

D. Array

7. Trong cây nhị phân, chiều cao của cây được định nghĩa là gì?

A. Số lượng nút trên cây

B. Số lượng cạnh trên đường đi dài nhất từ nút gốc đến nút lá

C. Số lượng mức của cây

D. Tổng số nút trên tất cả các mức

8. Heap (đống) là một dạng đặc biệt của cây nhị phân nào?

A. Cây nhị phân tìm kiếm (BST)

B. Cây nhị phân hoàn chỉnh (Complete Binary Tree)

C. Cây AVL

D. Cây đỏ đen (Red-Black Tree)

9. Abstract Data Type (ADT) là gì?

A. Một kiểu dữ liệu cụ thể được cài đặt bằng ngôn ngữ lập trình

B. Một mô hình toán học trừu tượng cho các kiểu dữ liệu cùng với các thao tác trên chúng

C. Một cấu trúc dữ liệu vật lý trong bộ nhớ máy tính

D. Một thuật toán cụ thể để sắp xếp dữ liệu

10. Giải thuật nào sau đây là giải thuật chia để trị (Divide and Conquer)?

A. Insertion Sort

B. Bubble Sort

C. Merge Sort

D. Selection Sort

11. Giải thuật Dijkstra thường đượ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 từ một đỉnh nguồn đến tất cả các đỉnh khác

B. Tìm chu trình Hamilton

C. Tìm cây khung nhỏ nhất

D. Kiểm tra tính liên thông của đồ thị

12. Trong cây nhị phân tìm kiếm (BST), thao tác tìm kiếm 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 log n)

D. O(1)

13. Trong thuật toán Kruskal, cấu trúc dữ liệu nào được sử dụng hiệu quả để kiểm tra và hợp nhất các tập hợp rời nhau (disjoint sets)?

A. Stack

B. Queue

C. Disjoint Set Union (DSU)

D. Hash Table

14. Hash collision (xung đột băm) xảy ra khi nào?

A. Khi bảng băm đầy

B. Khi hai khóa khác nhau được hàm băm ánh xạ đến cùng một vị trí

C. Khi tìm kiếm một khóa không có trong bảng băm

D. Khi xóa một phần tử khỏi bảng băm

15. Thuật toán tìm kiếm nào sau đây hiệu quả nhất trên mảng đã được sắp xếp?

A. Linear Search

B. Binary Search

C. Breadth-First Search

D. Depth-First Search

16. Khi nào nên sử dụng cấu trúc dữ liệu Queue thay vì Stack?

A. Khi cần truy cập phần tử cuối cùng được thêm vào đầu tiên

B. Khi cần quản lý công việc theo thứ tự ưu tiên

C. Khi cần xử lý các tác vụ theo thứ tự đến trước phục vụ trước

D. Khi cần tìm kiếm phần tử nhanh chóng

17. Trong cây nhị phân tìm kiếm, thao tác nào sau đây có thể làm thay đổi cấu trúc cây đáng kể và có thể cần cân bằng lại cây?

A. Tìm kiếm

B. Chèn nút

C. Duyệt cây

D. Xem nút gốc

18. Trong cây nhị phân cân bằng (ví dụ AVL tree), 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ữ

B. Tăng tốc độ truy cập tuần tự

C. Đảm bảo độ phức tạp thời gian tìm kiếm, chèn, xóa là O(log n)

D. Đơn giản hóa thuật toán duyệt cây

19. Trong cây AVL, hệ số cân bằng (balance factor) của một nút được tính như thế nào?

A. Hiệu số giữa chiều cao của cây con trái và cây con phải

B. Tổng chiều cao của cây con trái và cây con phải

C. Tích chiều cao của cây con trái và cây con phải

D. Thương chiều cao của cây con trái và cây con phải

20. Trong cấu trúc dữ liệu Stack, thao tác nào sau đây **KHÔNG** phải là thao tác cơ bản?

A. Push

B. Pop

C. Peek

D. Search

21. Thuật toán sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất từ phần chưa sắp xếp và đưa về đầu?

A. Insertion Sort

B. Bubble Sort

C. Selection Sort

D. Merge Sort

22. Cấu trúc dữ liệu nào sau đây thường được sử dụng để cài đặt hàng đợi ưu tiên (Priority Queue)?

A. Stack

B. Queue

C. Heap

D. Linked List

23. Ư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. Sử dụng bộ nhớ hiệu quả hơn khi kích thước cố định

C. Dễ dàng chèn và xóa phần tử ở đầu hoặc giữa danh sách

D. Tìm kiếm phần tử nhanh hơn

24. Trong đồ thị vô hướng, bậc của một đỉnh (degree) là gì?

A. Số lượng đỉnh kề với đỉnh đó

B. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác

C. Số cạnh liên thuộc với đỉnh đó

D. Tổng trọng số của các cạnh liên thuộc với đỉnh đó

25. Độ 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^2)

B. O(log n)

C. O(n log n)

D. O(n)

26. Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất, trung bình và xấu nhất đều là O(n log n)?

A. Quick Sort

B. Merge Sort

C. Insertion Sort

D. Bubble Sort

27. 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. Stack

B. Queue

C. Linked List

D. Tree

28. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là:

A. O(n^2)

B. O(log n)

C. O(n log n)

D. O(n)

29. Cấu trúc dữ liệu đồ thị (Graph) được sử dụng để mô hình hóa mối quan hệ giữa các đối tượng. Thành phần cơ bản của đồ thị bao gồm:

A. Node và Array

B. Vertex và Edge

C. Node và Pointer

D. Element và Index

30. Cấu trúc dữ liệu nào sau đây cho phép truy cập ngẫu nhiên (random access) các phần tử với độ phức tạp thời gian O(1)?

A. Linked List

B. Stack

C. Array

D. Queue