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 tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. ALogarit
2. BTuyến tính
3. CĐa thức
4. DHàm mũ

Đệ quy là gì?

1. AMột hàm gọi chính nó trên các đầu vào nhỏ hơn
2. BMột vòng lặp không bao giờ kết thúc
3. CMột loại cấu trúc dữ liệu
4. DMột phương pháp sắp xếp

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

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BQuicksort (phiên bản tại chỗ điển hình)
3. CSắp xếp trộn
4. DSắp xếp chọn (phiên bản điển hình)

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

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BCó, vì cả hai đều là hàm mũ
3. CCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
4. DKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn