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

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

1. Af 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
2. Bf 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
3. Cf tăng nhanh hơn g một cách nghiêm ngặt
4. Df tăng chậm hơn g một cách nghiêm ngặt

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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
2. BThời gian cho một đầu vào có độ dài trung bình
3. CThời gian trên loại máy tính phổ biến nhất
4. DThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp trộn
2. BSắp xếp vun đống
3. CSắp xếp chọn (phiên bản điển hình)
4. DQuicksort (phiên bản tại chỗ điển hình)

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

1. AO(n)
2. BO(n³)
3. CO(n²)
4. DO(n log 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 log₂ n
2. BKhoảng n / 2
3. CKhoảng √n
4. DKhoảng n

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. AThỏa mãn mạch
2. B2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
3. C3-SAT, trong đó mỗi mệnh đề có đúng ba literal
4. DSAT tổng quát trên các công thức dạng chuẩn tắc hội

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

1. AΘ(n log² n)
2. BΘ(n log n)
3. CΘ(n)
4. DΘ(n²)