Quiz Cấu Trúc Dữ Liệu

Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính trong mảng có n phần tử là gì?

• O(1)

• O(log n)

• O(n)

• O(n²)

Big O notation được sử dụng để mô tả điều gì?

• Độ chính xác của thuật toán

• Giới hạn trên của độ phức tạp thuật toán

• Số lượng biến trong chương trình

• Kích thước bộ nhớ cần thiết

Thuật toán nào có độ phức tạp O(log n)?

• Tìm kiếm tuyến tính

• Tìm kiếm nhị phân

• Sắp xếp nổi bọt

• Sắp xếp chọn

Độ phức tạp không gian của một mảng có n phần tử là:

• O(n)

• O(log n)

• O(1)

• O(n²)

Cho đoạn code sau, độ phức tạp thời gian là gì?
"""
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
sum += arr[i][j];
"""

• O(n)

• O(log n)

• O(n²)

• O(2n)

Ký hiệu Ω (Omega) trong phân tích độ phức tạp biểu thị:

• Độ phức tạp trung bình

• Giới hạn dưới của độ phức tạp

• Giới hạn trên của độ phức tạp

• Độ phức tạp trong trường hợp xấu nhất

Thuật toán Quick Sort có độ phức tạp trung bình là:

• O(n)

• O(n log n)

• O(n²)

• O(log n)

Cho thuật toán có độ phức tạp T(n) = 3n² + 2n + 1, Big O là:

• O(3n²)

• O(n²)

• O(2n)

• O(1)

Độ phức tạp thời gian của việc truy cập một phần tử trong mảng theo chỉ số là:

• O(1)

• O(n)

• O(log n)

• O(n²)

Trong phân tích độ phức tạp, trường hợp nào được quan tâm nhiều nhất?

• Trường hợp tốt nhất

• Trường hợp trung bình

• Trường hợp xấu nhất

• Tất cả đều quan trọng như nhau