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 xấu nhất của sắp xếp chèn là gì?

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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ADòng đầu tiên của hàm
2. BTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
3. CLời gọi dùng nhiều bộ nhớ nhất
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BVét cạn
3. CLựa chọn tham lam
4. DChia để trị

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

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

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
2. BQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
3. CChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
4. DChứng minh X kiểm chứng được trong thời gian đa thức

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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