Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

1. AO(n)
2. BO(1)
3. CO(n log n)
4. DO(log n)

log₂ 1024 bằng bao nhiêu?

1. A10
2. B12
3. C512
4. D32

Big O của 3n² + 5n + 2 là gì?

1. AO(5n)
2. BO(3n²)
3. CO(n²)
4. DO(n³)

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

1. AO(n³)
2. BO(n² log n)
3. CO(n²)
4. DO(n)

Phân tích khấu hao đo lường điều gì?

1. AChi phí kỳ vọng trên các đầu vào ngẫu nhiên
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí của một thuật toán trên đầu vào tốt nhất

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
2. BThứ tự tô-pô trong mọi đồ thị
3. CCây khung nhỏ nhất
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. ANhiều khóa có thể va chạm vào cùng một ngăn
2. BCác khóa phải được sắp xếp trước
3. CMảng có truy cập O(n)
4. DHàm băm chậm

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ATối đa log n lần giá trị nhỏ nhất
2. BKhông rõ chất lượng so với tối ưu
3. CCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
4. DLuôn là một phủ đỉnh nhỏ nhất