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 vòng lặp không bao giờ kết thúc
4. DMột loại cấu trúc dữ liệu

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BĐoán, kiểm tra, lặp lại
3. CSắp xếp, tìm kiếm, trả về
4. DĐọc, tính toán, ghi

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 chèn
2. BQuicksort
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(n²)
2. BO(dn log k)
3. CO(n log n)
4. DO(d(n + k))

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

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

1. AKhô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
2. BMọi chương trình cuối cùng đều dừng
3. CNên tránh các vòng lặp
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

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACả hai biến thể
2. BCái túi phân số, trong đó các món có thể bị chia nhỏ
3. CKhông biến thể nào
4. DBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên