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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
3. CNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
4. DNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự

Thuật toán là gì?

1. AMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột cấu trúc dữ liệu lưu trữ các số
4. DMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. AQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
2. BCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DSắp xếp trộn đã là O(n)

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc P, và X quy dẫn về SAT
2. BX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
3. CX không có thuật toán đa thức, và X quyết định được
4. DX quy dẫn về một bài toán trong P, và X thuộc NP

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. Bn² = o(n)
3. Cn = o(n), vì mọi hàm đều là little-o của chính nó
4. D2n = o(n), vì 2n tăng chậm