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

Ghi nhớ (memoisation) là gì?

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

Đệ quy là gì?

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

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

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

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 20
2. BKhoảng 1,000
3. CKhoảng 500,000
4. DKhoảng 100

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n³)
2. BΘ(n^{log₂ 3}), khoảng n^1,585
3. CΘ(n log n)
4. DΘ(n²)

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ASố âm không thể lưu trong hàng đợi ưu tiên
2. BMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
3. CNó chỉ hoạt động trên đồ thị vô hướng
4. DNó rơi vào vòng lặp vô hạn ở mọi cạnh âm