Select the most correct statement:
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "In all cases the selection sort is O(n^2).". Sắp xếp chọn luôn chạy hai vòng lặp lồng cố định: lượt thứ i quét toàn bộ phần chưa sắp để tìm phần tử nhỏ nhất, nên số phép so sánh là n−1 cộng n−2 cộng tiếp tới 1, bằng n(n−1)/2 bất kể dữ liệu ra sao. Nó không có cơ chế nào phát hiện mảng đã sắp để dừng sớm, vì phải quét hết mới biết đâu là nhỏ nhất; số phép đổi chỗ thì ít, chỉ cỡ n, nhưng phép so sánh mới chi phối chi phí. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(n)." mô tả sắp xếp nổi bọt có cờ kiểm tra hoán vị, loại dừng ngay khi một lượt không đổi gì, hoặc sắp xếp chèn trên mảng đã sắp. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(nlog n)." gán cho trường hợp tốt mức chi phí của sắp xếp trộn hay sắp xếp nhanh, hai thuật toán chia để trị. Phương án "In the average case the selection sort is O(n^2), in the best case it is O(nlog n)." đúng ở phần trung bình nhưng vẫn gán sai cho trường hợp tốt, vốn cũng là n(n−1)/2 phép so sánh.
Cùng phần 6
Select the most correct statement about the complexity of bubble sortCó lời giảiCâu hỏiThe following is the main part of insertion sort pseudocode:
for i := 1 to n-1
insert a[i] into sorted sublist {a[0],...,a[i-1]}
so that the sortedness is still kept.
end for
Select the most correct solution:
Consider the list of ten integers below:
16, 5, 2, 11, 10, 8, 12, 3, 8, 6
What is the list after the FIRST TWO steps of insertion sort? (sorting from smallest to largest).Có lời giảiCâu hỏiThe following is the main part of bubble sort pseudocode:
do
swapped := false
for i := 0 to n-2
if a[i] > a[i+1] then
swap(a[i],a[i+1])
swapped := true
end if
end for
while swapped
Consider the list of ten integers below:
5, 3, 9, 10, 1, 8, 0, 2, 6, 4
What is the list after the FIRST iteration (for i = 0 to n-2) in a bubble sort? (sorting from smallest to largest).Có lời giảiCâu hỏiCả 20 câu của chủ đề20 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây