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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BMảng chỉ được chứa số dương
3. CMảng phải được sắp xếp
4. DĐộ dài mảng phải là lũy thừa của hai

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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. BSắp xếp trộn
3. CSắp xếp chèn
4. DQuicksort

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(k n log n)
2. BO(nk)
3. CO(n + k)
4. DO(n log n + k log n)

Quy hoạch động hữu ích khi một bài toán có:

1. AChỉ các đầu vào ngẫu nhiên
2. BMột vòng lặp duy nhất
3. CCác bài toán con chồng lặp và cấu trúc con tối ưu
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

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 1,000
2. BKhoảng 500,000
3. CKhoảng 100
4. DKhoảng 20

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. AKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
2. BKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
3. CCó, nhưng chỉ với mảng ngắn hơn 100
4. DCó, nên cận dưới là sai

Cận nào là đúng cho log(n!)?

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