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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

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

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

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

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

1. AO(1)
2. BO(log 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 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
2. BChọn hoạt động bắt đầu sớm nhất
3. CChọ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
4. DChọn hoạt động ngắn nhất trước

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

1. AO(n²)
2. BO(n log n)
3. CO(log n)
4. DO(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) log V)
2. BO(V × E)
3. CO(V³)
4. DO(V + E)

Định lý Cook–Levin đã thiết lập điều gì?

1. AP không bằng NP
2. BBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
3. CMọi bài toán NP đều giải được trong thời gian hàm mũ
4. DBài toán dừng là bất khả quyết định