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. BChia để trị
3. CLựa chọn tham lam
4. DVét cạn

Độ phức tạp không gian đo lường:

1. AKích thước vật lý của máy tính
2. BLượng bộ nhớ một thuật toán cần khi đầu vào tăng
3. CSố dòng mã
4. DDung lượng đĩa của tệp chương trình sau khi được biên dịch

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Độ 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(n)
2. BO(log n)
3. CO(1)
4. DO(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 √n
2. BKhoảng log₂ n
3. CKhoảng n
4. DKhoảng n / 2

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. ATuyến tính
2. BHằng số
3. CHàm mũ
4. DLogarit

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ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(2^n²)

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

1. AΘ(n²)
2. BΘ(n log² n)
3. CΘ(n)
4. DΘ(n log n)