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

Đệ quy là gì?

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

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(n²)
3. CO(log n)
4. DO(1)

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp vun đống
3. CSắp xếp trộn
4. DSắp xếp nổi bọt

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

Bài toán dừng cho thấy rằng:

1. ANên tránh các vòng lặp
2. BKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
3. CMọi chương trình cuối cùng đều dừng
4. DMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng

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ọn pivot đồng đều ngẫu nhiên
2. BChỉ dùng đệ quy ở phía bên trái
3. CLuôn chọn phần tử đầu tiên
4. DSắp xếp đầu vào trước khi chạy quicksort