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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BVét cạn
3. CChia để trị
4. DLựa chọn tham lam

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. CViết chú thích bên cạnh từng dòng mã
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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp nổi bọt
2. BQuicksort
3. CSắp xếp trộn
4. DSắp xếp chè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)

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng log₂ n
2. BKhoảng n
3. CKhoảng n / 2
4. DKhoảng √n

Phát biểu nào về P và NP là đúng?

1. ANP có nghĩa là "không đa thức"
2. BĐã được chứng minh rằng P ≠ NP
3. CMọi bài toán trong P cũng thuộc NP
4. DCác bài toán NP không thể được kiểm chứng nhanh

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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