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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. Bo (little o)
3. CΘ (Big Theta)
4. DO (Big O)

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng đã được sắp xếp
2. BMột mảng có độ dài 2
3. CMột mảng có thứ tự ngẫu nhiên
4. DMột mảng mà các phần tử đều khác nhau

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
2. BBài toán có thể giải trong thời gian hằng số
3. CMọi bài toán con đều có cùng kích thước
4. DBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó

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

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

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. BSắp xếp đầu vào trước khi chạy quicksort
3. CChọn pivot đồng đều ngẫu nhiên
4. DLuôn chọn phần tử đầu tiên

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AFloyd–Warshall
2. BThuật toán Dijkstra
3. CThuật toán Kruskal
4. DThuật toán Prim bắt đầu từ một nút