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

Đệ quy là gì?

1. AMột hàm gọi chính nó trên các đầu vào nhỏ hơn
2. BMột phương pháp sắp xếp
3. CMột vòng lặp không bao giờ kết thúc
4. DMột loại cấu trúc dữ liệu

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AHàm mũ
2. BTuyến tính
3. CĐa thức
4. DLogarit

Thời gian chạy nào sau đây là đa thức?

1. AO(2ⁿ)
2. BO(n!)
3. CO(n³)
4. DO(nⁿ)

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động bắt đầu sớm nhất

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

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

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
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ì n³ nhỏ hơn n² khi n lớn

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V + E)
2. BO((V + E) log V)
3. CO(V × E)
4. DO(V³)

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

1. AGiải được trong thời gian đa thứ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. CKhông thể giải đượ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