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 của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Độ 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(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

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

1. ABig O
2. BBig Theta
3. CLittle omega
4. DBig Omega

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(d(n + k))
2. BO(n²)
3. CO(n log n)
4. DO(dn log k)

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 log n)
2. BΩ(n)
3. CΩ(n²)
4. DΩ(log n)

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó chạy trong thời gian O(1)
2. BNó tự động trả về 0
3. CNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
4. DTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn

Bài toán dừng cho thấy rằng:

1. ANên tránh các vòng lặp
2. BKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
3. CMọi chương trình cuối cùng đều dừng
4. DMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
2. BVì nó chỉ hoạt động khi W = 0
3. CW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
4. DVì n luôn nhỏ