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 của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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

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

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

1. AThờ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
2. BGiá 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
3. CThời gian cho một đầu vào có độ dài trung bình
4. DThời gian trên loại máy tính phổ biến nhất

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng √n
2. BKhoảng log₂ n
3. CKhoảng n
4. DKhoảng n / 2

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BQuicksort (phiên bản tại chỗ điển hình)
3. CSắp xếp trộn
4. DSắp xếp chọn (phiên bản điển hình)

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

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó kiểm tra xem có cạnh nào có trọng số âm không
2. BSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
3. CNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách
4. DNó đếm các chu trình bằng tìm kiếm theo chiều sâu