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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
2. BGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
3. CThời gian trên loại máy tính phổ biến nhất
4. DThời gian cho một đầu vào có độ dài trung bình

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(E log V)
2. BO(V²)
3. CO(V × E)
4. DO(V + E)

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 3 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 4 đồng; tối ưu là 3

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

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn)
4. DO(mn log n)

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị có hướng không chu trình
2. BĐồ thị đầy đủ
3. CĐồ thị có trọng số âm
4. DĐồ thị vô hướng

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