Ôn tập lí thuyết CTDL

Multiple Choice

1. Câu hỏi: Một danh sách liên kết đơn có thể mô tả bằng kiểu dữ liệu nào trong C++?

• A. Array

• B. Pointer

• C. Class

• D. Structure

Multiple Choice

2. Câu hỏi: Trong một cây nhị phân, nút con trái luôn có giá trị nhỏ hơn nút cha trong cây nào?

• A. Cây nhị phân tìm kiếm

• B. Cây nhị phân đầy đủ

• C. Cây nhị phân hoàn chỉnh

• D. Cây AVL

Multiple Choice

3. Câu hỏi: Đặc điểm nào sau đây là đúng đối với thuật toán tìm kiếm nhị phân?

• A. Dùng cho danh sách chưa được sắp xếp

• B. Tìm kiếm trong danh sách theo cách chia đôi danh sách thành các phần

• C. Thực hiện tìm kiếm theo cách tuyến tính

• D. Sử dụng đệ quy cho việc duyệt qua các phần tử

Multiple Choice

4. Câu hỏi: Một trong các đặc điểm của mảng động là gì?

• A. Kích thước cố định khi khởi tạo

• B. Kích thước có thể thay đổi trong quá trình chạy chương trình

• C. Mảng động chỉ chứa các giá trị số nguyên

• D. Mảng động chỉ có thể chứa một kiểu dữ liệu

Multiple Choice

5. Câu hỏi: Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là gì trong trường hợp xấu nhất?

• A. O(n log n)

• B. O(n)

• C. O(n^2)

• D. O(log n)

Multiple Choice

6. Câu hỏi: Trong cấu trúc dữ liệu "Hàng đợi (Queue)", thao tác "enqueue" là gì?

• A. Loại bỏ phần tử ở đầu hàng đợi

• B. Thêm phần tử vào cuối hàng đợi

• C. Xóa phần tử cuối cùng khỏi hàng đợi

• D. Thêm phần tử vào đầu hàng đợi

Multiple Choice

7. Câu hỏi: Cấu trúc dữ liệu nào sau đây là một cây nhị phân đặc biệt mà trong đó, chiều cao của hai cây con của mọi nút cha chênh lệch nhau tối đa 1?

• A. Cây nhị phân tìm kiếm

• B. Cây AVL

• C. Cây nhị phân hoàn chỉnh

• D. Cây đỏ đen

Multiple Choice

8. Câu hỏi: Thuật toán Dijkstra được sử dụng để làm gì?

• A. Sắp xếp mảng

• B. Tìm kiếm phần tử trong cây

• C. Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm

• D. Tìm kiếm nhị phân trong mảng

Multiple Choice

9. Câu hỏi: Khi nào ta sử dụng cấu trúc dữ liệu "Cây đỏ đen"?

• A. Khi cần giữ trật tự phần tử trong cây nhưng không yêu cầu sự cân bằng hoàn hảo.

• B. Khi cần cây nhị phân cân bằng mà mỗi thao tác có độ phức tạp thời gian O(log n).

• C. Khi chỉ cần cây nhị phân tìm kiếm không cần tối ưu về độ cao.

• D. Khi cần xây dựng cây nhị phân đầy đủ.

Multiple Choice

10. Câu hỏi: Trong một mảng liên kết (Linked List), thao tác "thêm một phần tử vào cuối danh sách" yêu cầu thời gian là bao lâu?

• A. O(1)

• B. O(n)

• C. O(log n)
  

• D. O(n^2)

Multiple Choice

11. Câu hỏi: Một ưu điểm của cây nhị phân tìm kiếm (Binary Search Tree - BST) là gì?

• A. Thời gian tìm kiếm luôn là O(n).

• B. Việc chèn và xóa phần tử có độ phức tạp là O(log n) trong trường hợp tốt nhất và O(n) trong trường hợp xấu nhất.

• C. BST luôn là cây cân bằng.

• D. Cây không có bất kỳ phần tử nào lớn hơn nút cha.

Multiple Choice

12. Câu hỏi: Đặc điểm nào sau đây là đúng đối với thuật toán Quick Sort?

• A. Luôn có độ phức tạp thời gian O(n^2).

• B. Là thuật toán sắp xếp chậm hơn so với Merge Sort trong mọi trường hợp.

• C. Được sử dụng phổ biến do có độ phức tạp thời gian trung bình là O(n log n).

• D. Không sử dụng phân chia dữ liệu (divide and conquer).

Multiple Choice

13. Câu hỏi: Cây nhị phân nào sau đây luôn được duy trì trong trạng thái cân bằng (không có sự chênh lệch về độ cao giữa hai cây con của mỗi nút) trong mọi thao tác chèn và xóa?

• A. Cây AVL

• B. Cây nhị phân tìm kiếm

• C. Cây đỏ đen

• D. Cây nhị phân hoàn chỉnh

Multiple Choice

14. Câu hỏi: Cấu trúc dữ liệu nào được sử dụng để lưu trữ biểu thức hậu tố (Postfix)?

• A. Hàng đợi

• B. Mảng

• C. Ngăn xếp

• D. Cây nhị phân

Multiple Choice

15. Câu hỏi: Thuật toán sắp xếp nào dưới đây có độ phức tạp tốt nhất là O(n log n)?

• A. Bubble Sort

• B. Selection Sort

• C. Merge Sort

• D. Insertion Sort

Multiple Choice

16. Câu hỏi: Đặc điểm nào của danh sách liên kết (Linked List) là khác biệt so với mảng (Array)?

• A. Các phần tử của danh sách liên kết luôn được lưu trữ liên tiếp trong bộ nhớ.

• B. Các phần tử của danh sách liên kết không thể thay đổi kích thước.

• C. Các phần tử của danh sách liên kết có thể được thêm hoặc xóa dễ dàng mà không cần thay đổi các phần tử khác.

• D. Danh sách liên kết có thể thực hiện các phép toán tìm kiếm nhanh hơn so với mảng.

Multiple Choice

17. Câu hỏi: Một đặc điểm của "Cây nhị phân hoàn chỉnh" là gì?

• A. Mỗi nút trong cây có hai con.

• B. Cây phải là cây nhị phân tìm kiếm.

• C. Tất cả các nút phải được điền vào, trừ các nút ở tầng cuối cùng, và các nút cuối cùng phải được điền từ trái sang phải.

• D. Cây phải có chiều cao tối đa bằng log(n).

Multiple Choice

18. Câu hỏi: Trong cấu trúc dữ liệu "Cây nhị phân", nếu một nút không có con trái hoặc con phải, nó được gọi là gì?

• A. Nút gốc

• B. Nút lá

• C. Nút cha

• D. Nút anh em

Multiple Choice

19. Câu hỏi: Trong cấu trúc dữ liệu "Mảng", độ phức tạp thời gian của thao tác truy cập phần tử tại vị trí bất kỳ là bao nhiêu?

• A. O(n)

• B. O(1)

• C. O(log n)

• D. O(n^2)

Multiple Choice

20. Câu hỏi: Một đặc điểm của "Danh sách liên kết đôi (Doubly Linked List)" là gì?

• A. Mỗi phần tử chỉ có một liên kết tới phần tử kế tiếp.

• B. Mỗi phần tử có hai liên kết: một tới phần tử trước và một tới phần tử sau.

• C. Không thể duyệt danh sách từ cuối đến đầu.

• D. Danh sách không thể bị thay đổi kích thước.

Multiple Choice

21. Câu hỏi: Đối với thuật toán sắp xếp "Selection Sort", độ phức tạp thời gian trong trường hợp tốt nhất là gì?

• A. O(n log n)

• B. O(n)

• C. O(n^2)

• D. O(log n)

Multiple Choice

22. Câu hỏi: Độ phức tạp của phép toán "chèn phần tử vào danh sách liên kết" trong trường hợp bình thường là bao nhiêu?

• A. O(1)

• B. O(n)

• C. O(log n)

• D. O(n^2)

Multiple Choice

23. Câu hỏi: Thuật toán sắp xếp nào dưới đây có độ phức tạp tốt nhất là O(n log n) và độ phức tạp xấu nhất là O(n^2)?

• A. Merge Sort

• B. Quick Sort

• C. Heap Sort

• D. Bubble Sort

Multiple Choice

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

• A. Merge Sort

• B. Quick Sort

• C. Insertion Sort

• D. Bubble Sort

Multiple Choice

25. Câu hỏi: Cấu trúc dữ liệu "Cây đỏ đen" có bao nhiêu thuộc tính đặc biệt?

• A. 3

• B. 4

• C. 5

• D. 6

Multiple Choice

26. Câu hỏi: Cấu trúc dữ liệu nào thường được sử dụng để mô hình hóa các mối quan hệ trong đồ thị?

• A. Danh sách liên kết

• B. Mảng

• C. Cây

• D. Ma trận kề

Multiple Choice

27. Câu hỏi: Phép toán "pop" trong cấu trúc dữ liệu ngăn xếp (Stack) thực hiện thao tác gì?

• A. Thêm phần tử vào cuối ngăn xếp

• B. Loại bỏ phần tử ở cuối ngăn xếp

• C. Lấy phần tử ở đầu ngăn xếp

• D. Đổi vị trí các phần tử trong ngăn xếp

Multiple Choice

28. Câu hỏi: Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) trong trường hợp xấu nhất là gì?

• A. O(1)

• B. O(n)

• C. O(log n)

• D. O(n log n)

Multiple Choice

29. Câu hỏi: Cây nhị phân nào dưới đây có thể có độ cao chênh lệch giữa các cây con của nút cha là tối đa 1?

• A. Cây nhị phân tìm kiếm

• B. Cây AVL

• C. Cây đỏ đen

• D. Cây nhị phân hoàn chỉnh

Multiple Choice

30. Câu hỏi: Cấu trúc dữ liệu "Hàng đợi" (Queue) có thể được triển khai bằng cấu trúc dữ liệu nào?

• A. Mảng

• B. Danh sách liên kết

• C. Ngăn xếp

• D. Cả A và B

Multiple Choice

31. Câu hỏi: Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào trong đồ thị?

• A. Tìm kiếm theo chiều rộng

• B. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại

• C. Tìm chu trình Euler trong đồ thị

• D. Tìm kiếm theo chiều sâu

Multiple Choice

32. Câu hỏi: Cấu trúc liệu nào được sử dụng để thực hiện thuật toán tìm kiếm nhị phân?

• A. Danh sách liên kết

• B. Cây nhị phân tìm kiếm

• C. Mảng đã được sắp xếp

• D. Cây nhị phân hoàn chỉnh

Multiple Choice

33. Câu hỏi: Thuật toán nào dưới đây không phải là thuật toán sắp xếp so sánh?

• A. Merge Sort

• B. Quick Sort

• C. Bubble Sort

• D. Counting Sort

Multiple Choice

34. Câu hỏi: Trong thuật toán Merge Sort, phép chia mảng được thực hiện như thế nào?

• A. Chia mảng thành 2 phần, sau đó sắp xếp từng phần và hợp nhất lại.

• B. Chia mảng thành nhiều phần nhỏ và thực hiện sắp xếp cho từng phần

• C. Mảng được chia liên tục cho đến khi chỉ còn 1 phần tử.

• D. Chia mảng thành phần lớn và phần nhỏ, thực hiện sắp xếp và ghép lại.

Multiple Choice

35. Câu hỏi: Trong cấu trúc dữ liệu "Cây nhị phân tìm kiếm", các phần tử con trái của một nút luôn có giá trị như thế nào?

• A. Lớn hơn nút cha

• B. Nhỏ hơn nút cha

• C. Bằng nút cha

• D. Không có quy định