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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên một máy tính chậm
2. BThời gian tối đa nó mất trên mọi đầu vào kích thước n
3. CThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
4. DThời gian nó mất trên đầu vào nhỏ nhất

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ó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
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ó chia mảng làm đôi rồi trộn lại

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

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. ATìm kiếm theo chiều sâu
2. BThuật toán Dijkstra
3. CThuật toán Kruskal
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

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ó độ dài 2
2. BMột mảng đã được sắp xếp
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

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n), vì mọi hàm đều là little-o của chính nó
2. Bn = o(n²), nhưng n không phải o(n)
3. C2n = o(n), vì 2n tăng chậm
4. Dn² = o(n)

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. ACó, nhưng chỉ với mảng ngắn hơn 100
2. BCó, nên cận dưới là sai
3. CKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
4. DKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào