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

Đệ quy là gì?

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

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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BBig Theta
3. CLittle omega
4. DBig Omega

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

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có thể giải trong thời gian hằng số
2. BMọi bài toán con đều có cùng kích thước
3. CBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
4. DMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BSắp xếp đầu vào trước khi chạy quicksort
3. CChọn pivot đồng đều ngẫu nhiên
4. DChỉ dùng đệ quy ở phía bên trái

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

1. AO(n³)
2. BO(n² 2ⁿ)
3. CO(2^n²)
4. DO(n!)