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

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

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

Độ phức tạp không gian đo lường:

1. AKích thước vật lý của máy tính
2. BLượng bộ nhớ một thuật toán cần khi đầu vào tăng
3. CSố dòng mã
4. DDung lượng đĩa của tệp chương trình sau khi được biên dịch

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Một thuật toán tham lam:

1. AChỉ dùng đệ quy
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CThử mọi lời giải có thể
4. DLuôn cho lời giải tối ưu

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì n³ nhỏ hơn n² khi n lớn
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CĐúng, nhưng chỉ khi n nhỏ hơn 100
4. DKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm

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

1. AKhông thể giải đượ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. CGiải được trong thời gian đa thức
4. DNằ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

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(n) mỗi lần tăng
4. DO(1) mỗi lần tăng