Độ phức tạp thời gian trung bình của thuật toán QuickSort là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(log n)

Trong thuật toán sắp xếp trộn (merge sort), giai đoạn nào chiếm phần lớn thời gian thực hiện?

• A. Giai đoạn chia mảng thành các mảng con.
• B. Giai đoạn so sánh các phần tử.
• C. Giai đoạn trộn (merge) các mảng con đã sắp xếp.
• D. Giai đoạn khởi tạo mảng.

Độ phức tạp thời gian của thao tác tìm kiếm trong cây tìm kiếm nhị phân (BST) lệch (skewed tree) là bao nhiêu?

• A. O(log n)
• B. O(n)
• C. O(1)
• D. O(n log n)

Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất?

• A. Merge Sort
• B. QuickSort
• C. Heap Sort
• D. Insertion Sort

Trong thuật toán tô màu đồ thị (graph coloring), mục tiêu là gì?

• A. Tìm đường đi ngắn nhất giữa hai đỉnh.
• B. Tìm cây khung nhỏ nhất.
• C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau có cùng màu.
• D. Tìm chu trình Hamilton.

Trong biểu đồ (graph), thuật toán nào sau đây được sử dụng để tìm chu trình Euler?

• A. Thuật toán Dijkstra
• B. Thuật toán Kruskal
• C. Thuật toán Fleury
• D. Thuật toán Prim

Trong thuật toán Floyd-Warshall, mục đích chính là gì?

• A. Tìm đường đi ngắn nhất giữa hai đỉnh cụ thể.
• B. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị.
• C. Tìm cây khung nhỏ nhất của đồ thị.
• D. Tìm chu trình Euler trong đồ thị.

Ưu điểm chính của cây tìm kiếm nhị phân cân bằng (ví dụ: AVL tree, Red-Black tree) so với cây tìm kiếm nhị phân thông thường là gì?

• A. Đơn giản hơn trong việc cài đặt.
• B. Tiêu thụ ít bộ nhớ hơn.
• C. Đảm bảo thời gian tìm kiếm, chèn, xóa là O(log n) trong trường hợp xấu nhất.
• D. Cho phép duyệt cây theo thứ tự ngược.

Trong biểu đồ có hướng (directed graph), thành phần liên thông mạnh (strongly connected component) là gì?

• A. Một tập hợp các đỉnh mà không có đường đi giữa chúng.
• B. Một tập hợp các đỉnh mà có đường đi từ mọi đỉnh đến mọi đỉnh khác trong tập hợp.
• C. Một tập hợp các đỉnh mà có đường đi từ một đỉnh đến tất cả các đỉnh khác trong đồ thị.
• D. Một tập hợp các đỉnh mà tất cả đều có bậc vào và bậc ra bằng nhau.

Loại đồ thị nào sau đây có thể được biểu diễn bằng ma trận kề (adjacency matrix) một cách hiệu quả nhất?

• A. Đồ thị thưa (sparse graph)
• B. Đồ thị dày (dense graph)
• C. Cây (tree)
• D. Danh sách liên kết (linked list)

Khi nào thì thuật toán Bubble Sort hoạt động hiệu quả nhất?

• A. Khi dữ liệu đã được sắp xếp gần như hoàn chỉnh.
• B. Khi dữ liệu hoàn toàn ngẫu nhiên.
• C. Khi dữ liệu được sắp xếp theo thứ tự ngược.
• D. Bubble Sort không bao giờ hoạt động hiệu quả.

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

• A. Hiệu của chiều cao cây con trái và chiều cao cây con phải.
• B. Tổng của chiều cao cây con trái và chiều cao cây con phải.
• C. Tích của chiều cao cây con trái và chiều cao cây con phải.
• D. Thương của chiều cao cây con trái và chiều cao cây con phải.

Khi nào nên sử dụng thuật toán tìm kiếm theo chiều sâu (depth-first search) thay vì tìm kiếm theo chiều rộng (breadth-first search)?

• A. Khi cần tìm đường đi ngắn nhất.
• B. Khi không gian tìm kiếm rất rộng và có thể có đường đi dài.
• C. Khi cần duyệt tất cả các đỉnh trong đồ thị.
• D. Khi biết trước đích đến nằm gần đỉnh xuất phát.

Khi nào nên sử dụng danh sách liên kết đơn (singly linked list) thay vì mảng (array)?

• A. Khi cần truy cập ngẫu nhiên đến các phần tử.
• B. Khi biết trước kích thước của dữ liệu.
• C. Khi cần chèn hoặc xóa phần tử ở giữa danh sách một cách hiệu quả.
• D. Khi cần tiết kiệm bộ nhớ.

Trong cây đỏ-đen (Red-Black tree), một nút có thể có bao nhiêu màu?

• A. Một màu (đen)
• B. Hai màu (đỏ hoặc đen)
• C. Ba màu (đỏ, đen, hoặc xám)
• D. Vô số màu

Trong thuật toán sắp xếp vun đống (heap sort), thao tác 'vun đống' (heapify) có tác dụng gì?

• A. Sắp xếp các phần tử trong mảng theo thứ tự tăng dần.
• B. Đảm bảo rằng cây nhị phân thỏa mãn tính chất của heap.
• C. Chia mảng thành các mảng con.
• D. Tìm phần tử lớn nhất trong mảng.

Trong cây B, bậc của cây (order) được định nghĩa là gì?

• A. Số lượng nút tối thiểu trong cây.
• B. Số lượng nút tối đa trong cây.
• C. Số lượng con tối đa mà một nút có thể có.
• D. Chiều cao của cây.

Cấu trúc dữ liệu nào sau đây 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. Heap
• D. Cây tìm kiếm nhị phân (binary search tree)

Trong thuật toán Prim để tìm cây khung nhỏ nhất, cấu trúc dữ liệu nào sau đây thường được sử dụng để lưu trữ các đỉnh chưa được thêm vào cây khung?

• A. Hàng đợi (queue)
• B. Ngăn xếp (stack)
• C. Hàng đợi ưu tiên (priority queue)
• D. Danh sách liên kết (linked list)

Thuật toán nào sau đây được sử dụng để tìm kiếm một phần tử trong mảng đã được sắp xếp?

• 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)

Ưu điểm của việc sử dụng bảng băm (hash table) so với mảng (array) là gì?

• A. Bảng băm luôn sử dụng ít bộ nhớ hơn mảng.
• B. Bảng băm cho phép truy cập các phần tử trong thời gian O(1) trung bình, trong khi mảng cần O(n) trong trường hợp xấu nhất.
• C. Bảng băm cho phép lưu trữ dữ liệu theo thứ tự.
• D. Bảng băm không cần phải xác định kích thước trước.

Trong thuật toán A* tìm đường đi, hàm heuristic (h(n)) được sử dụng để làm gì?

• A. Ước tính chi phí từ đỉnh hiện tại đến đỉnh đích.
• B. Tính chi phí thực tế từ đỉnh bắt đầu đến đỉnh hiện tại.
• C. Lưu trữ các đỉnh đã được duyệt.
• D. Đảm bảo rằng thuật toán luôn tìm thấy đường đi ngắn nhất.

Thuật toán sắp xếp nào sau đây là một thuật toán sắp xếp tại chỗ (in-place sorting algorithm)?

• A. Merge Sort
• B. QuickSort
• C. Counting Sort
• D. Radix Sort

Trong thuật toán Kruskal để tìm cây khung nhỏ nhất, bước nào sau đây được thực hiện?

• A. Chọn cạnh có trọng số lớn nhất và thêm vào cây khung.
• B. Chọn cạnh có trọng số nhỏ nhất và thêm vào cây khung nếu nó không tạo thành chu trình.
• C. Loại bỏ tất cả các cạnh có trọng số âm.
• D. Chọn một đỉnh ngẫu nhiên và thêm tất cả các cạnh kề với đỉnh đó vào cây khung.

Thuật toán tìm kiếm nào sau đây có độ phức tạp thời gian O(1) trong trường hợp tốt nhất?

• 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 (breadth-first search)
• D. Tìm kiếm bằng hàm băm (hashing)

Khi nào nên sử dụng cây Trie (prefix tree)?

• A. Khi cần lưu trữ và tìm kiếm các số nguyên.
• B. Khi cần lưu trữ và tìm kiếm các chuỗi ký tự với tiền tố chung.
• C. Khi cần sắp xếp dữ liệu.
• D. Khi cần biểu diễn mối quan hệ giữa các đối tượng.

Trong cây quyết định (decision tree), mục đích của việc tỉa cây (pruning) là gì?

• A. Tăng độ chính xác của cây.
• B. Giảm kích thước của cây và tránh overfitting.
• C. Tăng tốc độ xây dựng cây.
• D. Đơn giản hóa việc biểu diễn cây.

Cấu trúc dữ liệu nào sau đây tuân theo nguyên tắc LIFO (Last In, First Out)?

• A. Hàng đợi (Queue)
• B. Hàng đợi ưu tiên (Priority Queue)
• C. Ngăn xếp (Stack)
• D. Danh sách liên kết (Linked List)

Khi sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm, cấu trúc dữ liệu nào thường được sử dụng để lưu trữ khoảng cách ước tính từ đỉnh nguồn đến các đỉnh khác?

• A. Hàng đợi (queue)
• B. Ngăn xếp (stack)
• C. Hàng đợi ưu tiên (priority queue)
• D. Danh sách liên kết (linked list)

Cấu trúc dữ liệu nào sau đây phù hợp nhất để kiểm tra xem một chuỗi có phải là palindrome hay không?

• A. Hàng đợi (Queue)
• B. Ngăn xếp (Stack)
• C. Cây (Tree)
• D. Đồ thị (Graph)