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

Big O của 3n² + 5n + 2 là gì?

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

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

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

1. ATrườ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
2. BDòng đầu tiên của hàm
3. CLời gọi dùng nhiều bộ nhớ nhất
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

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

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

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

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. 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. DNên tránh các vòng lặp

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
2. BCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
3. CCác bài toán có thể giải song song
4. DCác bài toán cần thời gian hàm mũ trên mọi máy tính