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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ATuyến tính
2. BLogarit
3. CHằng số
4. DBậc hai

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

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

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BHoàn toàn không có bài toán con, nên có thể giải trong một bước
3. CChỉ các đầu vào ngẫu nhiên
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

1. AO(n log n)
2. BO(n²)
3. CO(n)
4. DO(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ó tự động trả về 0
2. BNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
3. CTrì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
4. DNó chạy trong thời gian O(1)

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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

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

1. AThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
2. BNằ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
3. CKhông thể giải được
4. DGiải được trong thời gian đa thức