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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên một máy tính chậm
2. BThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
3. CThời gian tối đa nó mất trên mọi đầu vào kích thước n
4. DThời gian nó mất trên đầu vào nhỏ nhất

Thuật toán là gì?

1. ABất kỳ chương trình máy tính nào có giao diện đồ họa
2. BMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
3. CMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
4. DMột cấu trúc dữ liệu lưu trữ các số

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

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

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BKhông, vì n³ nhỏ hơn n² khi n lớn
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng mà các phần tử đều khác nhau
2. BMột mảng có độ dài 2
3. CMột mảng đã được sắp xếp
4. DMột mảng có thứ tự ngẫu nhiên

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(2ⁿ) và không gian O(1)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(log n) và không gian O(n)

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

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