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

Ghi nhớ (memoisation) là gì?

1. ATự độ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
2. BViết chú thích bên cạnh từng dòng mã
3. CLư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ớ
4. DGiải phóng bộ nhớ sau khi một hàm trả về

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

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

Thuật toán vét cạn là gì?

1. AThuật toán đoán một đáp án ngẫu nhiên
2. BThuật toán thử mọi lời giải ứng viên có thể
3. CThuật toán luôn dùng đệ quy
4. DThuật toán chạy trên nhiều bộ xử lý

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
3. CSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
4. DCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử

Một thuật toán tham lam:

1. AĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
2. BThử mọi lời giải có thể
3. CLuôn cho lời giải tối ưu
4. DChỉ dùng đệ quy

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
2. BNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
3. CNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
4. DNó xóa cạnh đắt nhất cho đến khi không còn chu trình

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. AKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
2. BCó, nên cận dưới là sai
3. CKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
4. DCó, nhưng chỉ với mảng ngắn hơn 100

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(log n) mỗi lần tăng
2. BO(n) mỗi lần tăng
3. CO(n log n) mỗi lần tăng
4. DO(1) mỗi lần tăng