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 trong trường hợp xấu nhất của sắp xếp trộn là gì?

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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A8 giây
2. B1 giây
3. C4 giây
4. D2 giây

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. CGiải phóng bộ nhớ sau khi một hàm trả về
4. DLư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ớ

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

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

1. AO(n³)
2. BO(n²)
3. CO(n)
4. DO(n log 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. BSắp xếp trộn đã là O(n)
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DCá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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ATìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
2. BCác phép so sánh trên nút danh sách liên kết chậm hơn
3. CDanh sách liên kết không thể được sắp xếp
4. DĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. AMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP
2. BBài toán dừng trở nên quyết định được
3. CChỉ bài toán đó chuyển vào P
4. DMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính