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 liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp vun đống
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

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

1. ABig O
2. BBig Theta
3. CBig Omega
4. DLittle omega

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. A4 giây
2. B8 giây
3. C2 giây
4. D1 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 log n)
3. CO(n)
4. DO(n³)

Phân tích khấu hao đo lường điều gì?

1. AChi phí kỳ vọng trên các đầu vào ngẫu nhiên
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí của một thuật toán trên đầu vào tốt nhất
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ATối đa log n lần giá trị nhỏ nhất
2. BLuôn là một phủ đỉnh nhỏ nhất
3. CCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
4. DKhông rõ chất lượng so với tối ưu