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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n / 2
2. BKhoảng n
3. CKhoảng n²
4. DKhoảng log₂ n

Độ 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)

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A2 giây
2. B8 giây
3. C1 giây
4. D4 giây

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

Độ 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(2^m+n)
3. CO(mn)
4. DO(m + n)

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BChỉ các đầu vào ngẫu nhiên
3. CCác bài toán con chồng lặp và cấu trúc con tối ưu
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
2. BBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
3. CBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
4. DCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán

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