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 nhị phân trên một mảng đã sắp xếp là gì?

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

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán thử mọi lời giải ứng viên có thể
3. CThuật toán luôn dùng đệ quy
4. DThuật toán đoán một đáp án ngẫu nhiên

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ALogarit luôn được làm tròn thành số nguyên
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DCơ số chỉ quan trọng với n nhỏ

Độ 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(n²)
3. CO(2ⁿ)
4. DO(log n)

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AChứng minh X kiểm chứng được trong thời gian đa thức
2. BQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
3. CChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
4. DQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức

Phát biểu nào về P và NP là đúng?

1. AMọi bài toán trong P cũng thuộc NP
2. BNP có nghĩa là "không đa thức"
3. CĐã được chứng minh rằng P ≠ NP
4. DCác bài toán NP không thể được kiểm chứng nhanh