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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ATrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
2. BLời gọi dùng nhiều bộ nhớ nhất
3. CTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
4. DDòng đầu tiên của hàm

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp chèn
2. BSắp xếp nổi bọt
3. CSắp xếp trộn
4. DQuicksort

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Đệ 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

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. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. ABài toán dừng trở nên quyết định được
2. BMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP
3. CMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính
4. DChỉ bài toán đó chuyển vào P

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
3. CKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn
4. DCó, vì cả hai đều là hàm mũ