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 đầu vào nhỏ nhất
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 một máy tính chậm

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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

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

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n / 2
2. BKhoảng n
3. CKhoảng log₂ n
4. DKhoảng √n

Một bài toán là NP-đầy đủ nếu nó:

1. AGiải được trong thời gian đa thức
2. BThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
3. CNằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
4. DKhông thể giải được

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(n log n) mỗi lần tăng
2. BO(log n) mỗi lần tăng
3. CO(1) mỗi lần tăng
4. DO(n) mỗi lần tăng