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

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

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

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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BLittle omega
3. CBig Omega
4. DBig Theta

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

1. AO(V × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V³ × E)

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
2. BNó xóa cạnh đắt nhất cho đến khi không còn chu trình
3. CNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
4. DNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng

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

Công thức truy hồi T(n) = 2T(n/2) + n log n có nghiệm là gì?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n log² n)
4. DΘ(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 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
2. BCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
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. DBà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