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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
2. BThời gian trên loại máy tính phổ biến nhất
3. CThời gian cho một đầu vào có độ dài trung bình
4. DThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n

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 đoán một đáp án ngẫu nhiên
3. CThuật toán luôn dùng đệ quy
4. DThuật toán thử mọi lời giải ứng viên có thể

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 3 đồng; tối ưu là 2

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BThuật toán Dijkstra
3. CThuật toán Kruskal
4. DTìm kiếm theo chiều sâu

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

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó 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
3. CNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
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

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

1. ACác bài toán cần thời gian hàm mũ trên mọi máy tính
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 quyết định giải được bằng thuật toán tất định trong thời gian đa thức
4. DCác bài toán có thể giải song song

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