Phiếu bài tập Thuật toán và độ phức tạp có đáp á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 / 2
3. CKhoảng log₂ n
4. DKhoảng 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(n log n)
3. CO(n²)
4. DO(log n)

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
2. BChi phí kỳ vọng trên các đầu vào ngẫu nhiên
3. CChi phí của một thuật toán trên đầu vào tốt nhất
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động bắt đầu sớm nhất
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích

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

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n²)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n² log n)
4. DΘ(n³)

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AFloyd–Warshall
2. BThuật toán Dijkstra
3. CThuật toán Prim bắt đầu từ một nút
4. DThuật toán Kruskal