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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AĐa thức
2. BTuyến tính
3. CHàm mũ
4. DLogarit

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ADòng đầu tiên của hàm
2. BTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
3. CTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
4. DLời gọi dùng nhiều bộ 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 ngôn ngữ lập trình được thiết kế để viết các công thức toán học
3. CMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
4. DMột cấu trúc dữ liệu lưu trữ các số

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CThử mọi lời giải có thể
4. DChỉ dùng đệ quy

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(m + n)
3. CO(mn)
4. DO(2^m+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 đã được sắp xếp
2. BMột mảng mà các phần tử đều khác nhau
3. CMột mảng có thứ tự ngẫu nhiên
4. DMột mảng có độ dài 2

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n² log n)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n³)
4. DΘ(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)