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 của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

1. AO(1)
2. BO(n log n)
3. CO(log n)
4. DO(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(log n)
2. BO(n²)
3. CO(n)
4. DO(n log 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 tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
3. CThời gian nó mất trên một máy tính chậm
4. DThời gian nó mất trên đầu vào nhỏ nhất

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

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AThứ tự tô-pô trong mọi đồ thị
2. BĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
3. CCây khung nhỏ nhất
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phá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 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 ngắn nhất trước
3. CChọn hoạt động bắt đầu sớm nhất
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

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

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

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. AMảng có truy cập O(n)
2. BHàm băm chậm
3. CCác khóa phải được sắp xếp trước
4. DNhiều khóa có thể va chạm vào cùng một ngăn