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

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BĐoán, kiểm tra, lặp lại
3. CSắp xếp, tìm kiếm, trả về
4. DĐọc, tính toán, ghi

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó luôn mất đúng một giây
2. BNó chỉ có thể chạy một lần
3. CThời gian chạy của nó không tăng theo kích thước đầu vào
4. DNó xử lý đúng một phần tử mỗi giây thời gian chạy

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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CMột thứ tự tô-pô trong O(V²)
4. DMột cây khung nhỏ nhất trong O(E log V)

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à 2
2. BTham lam dùng 4 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 2 đồng; tối ưu là 2

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

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

Cận nào là đúng cho log(n!)?

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

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. AKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
2. BKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
3. CCó, nên cận dưới là sai
4. DCó, nhưng chỉ với mảng ngắn hơn 100