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 trong trường hợp xấu nhất của sắp xếp chèn là gì?

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

Thuật toán là gì?

1. AMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
4. DMột cấu trúc dữ liệu lưu trữ các số

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ALogarit
2. BBậc hai
3. CHằng số
4. DTuyến tính

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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