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 một máy tính chậm
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 tối đa nó mất trên mọi đầu vào kích thước n
4. DThời gian nó mất trên đầu vào nhỏ nhất

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
3. CKhoảng n / 2
4. DKhoảng log₂ n

Thuật toán là gì?

1. AMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
2. BMột cấu trúc dữ liệu lưu trữ các số
3. CMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
4. DBất kỳ chương trình máy tính nào có giao diện đồ họa

Độ 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)

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

1. AΩ(n²)
2. BΩ(n log n)
3. CΩ(n)
4. DΩ(log 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(nk)
3. CO(n log n + k log n)
4. DO(n + k)

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

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

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

1. AO(n!)
2. BO(2^n²)
3. CO(n³)
4. DO(n² 2ⁿ)