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

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BSắp xếp, tìm kiếm, trả về
3. CĐọc, tính toán, ghi
4. DĐoán, kiểm tra, lặp lại

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n
2. BKhoảng n²
3. CKhoảng n / 2
4. DKhoảng log₂ n

Thuật toán vét cạn là gì?

1. AThuật toán luôn dùng đệ quy
2. BThuật toán đoán một đáp án ngẫu nhiên
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán chạy trên nhiều bộ xử lý

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Độ 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. CLogarit
4. DTuyến tính

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. ACó, nên cận dưới là sai
2. BKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
3. CKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
4. DCó, nhưng chỉ với mảng ngắn hơn 100

Cận nào là đúng cho log(n!)?

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n)