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 của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
4. DCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử

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

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

Đệ 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 / 2
3. CKhoảng n
4. DKhoảng √n

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. AChỉ dùng đệ quy ở phía bên trái
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. DLuôn chọn phần tử đầu tiên

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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