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

Thuật toán là gì?

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

Độ 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(1)
2. BO(log n)
3. CO(n)
4. DO(n log n)

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort 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 Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHàm mũ
2. BHằng số
3. CTuyến tính
4. DLogarit

Công thức truy hồi T(n) = T(n − 1) + O(1) có nghiệm là gì?

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

Độ 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 log n)
2. BO(n²)
3. CO(n)
4. DO(n √n)

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì n luôn nhỏ
2. BW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
3. CVì nó chỉ hoạt động khi W = 0
4. DVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào