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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Omega
2. BBig O
3. CBig Theta
4. DLittle omega

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng nhanh hơn g một cách nghiêm ngặt
2. Bf luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
3. Cf tăng chậm hơn g một cách nghiêm ngặt
4. Df tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

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í của một thuật toán trên đầu vào tốt nhất
3. CChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

Một thuật toán tham lam:

1. AChỉ dùng đệ quy
2. BThử mọi lời giải có thể
3. CLuôn cho lời giải tối ưu
4. DĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước

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ị đầy đủ
4. DĐồ thị vô hướng

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
2. BViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp
3. CQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
4. DViệc chọn chỉ có thể thực hiện trong O(n²)