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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DSắp xếp vun đống

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

1. ANó 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
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
4. DNó 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

Ghi nhớ (memoisation) là gì?

1. AGiải phóng bộ nhớ sau khi một hàm trả về
2. BLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
3. CTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
4. DViết chú thích bên cạnh từng dòng mã

Độ 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(n)
2. BO(2ⁿ)
3. CO(log n)
4. DO(n²)

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

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

Công thức truy hồi T(n) = 2T(n − 1) + O(1) có nghiệm là gì?

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

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

1. ABài toán dừng là bất khả quyết định
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. DP không bằng NP

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 quy dẫn về một bài toán trong P, và X thuộc NP
2. BX thuộc P, và X quy dẫn về SAT
3. CX không có thuật toán đa thức, và X quyết định được
4. DX 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