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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp vun đống
2. BQuicksort
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

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

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

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị vô hướng
2. BĐồ thị đầy đủ
3. CĐồ thị có trọng số âm
4. DĐồ thị có hướng không chu trình

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(log n) mỗi lần tăng
2. BO(n log n) mỗi lần tăng
3. CO(n) mỗi lần tăng
4. DO(1) mỗi lần tăng