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

Sắp xếp chọn hoạt động như thế nào?

1. ANó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
4. DNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự

Thuật toán vét cạn là gì?

1. AThuật toán luôn dùng đệ quy
2. BThuật toán thử mọi lời giải ứng viên có thể
3. CThuật toán đoán một đáp án ngẫu nhiên
4. DThuật toán chạy trên nhiều bộ xử lý

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. BSắp xếp nổi bọt
3. CSắp xếp trộn
4. DQuicksort

Độ 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 log n)
3. CO(n)
4. DO(n³)

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

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 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ũ
2. BBà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
3. CBà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
4. DCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toá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(log n) và không gian O(n)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(2ⁿ) và không gian O(1)
4. DThời gian O(n) và không gian O(n)