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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên đầu vào nhỏ nhất
2. BThời gian tối đa nó mất trên mọi đầu vào kích thước n
3. CThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
4. DThời gian nó mất trên một máy tính chậm

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 log n)
3. CO(n²)
4. DO(k log 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(log n)
3. CO(n²)
4. DO(n log n)

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 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
2. BChọ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
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động bắt đầu sớm nhất

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

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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ACác phép so sánh trên nút danh sách liên kết chậm hơn
2. BĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
3. CDanh sách liên kết không thể được sắp xếp
4. DTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. BChúng tăng với cùng tốc độ
3. Cn! là O(n²)
4. Dn! tăng nhanh hơn 2ⁿ