ý tưởng phương pháp sắp xếp chèn (insertion sort) là:
A. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.
B. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba...
C. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống.
D. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Giải bởi Vietjack
Chọn đáp án C
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau
lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ năm là:
Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F
Begin a[0]:=- ∞; for i:=2 to n do
begin x:=a[i]; j:=i-1;
while x<="" br="">begin a*[j+1]:=a*[j]; j:=j-1; end; a[j+1]:=x;
end;
End;
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau
lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ chín là:
Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F(a, t, s);
Begin B:= true;
if twhile b do begin
i:=i+1; while a[i]<=key do i:=i+1; j:=j -1; while a[j]>=key do j:=j-1;
if i<="" br="">begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end
else b:=false; end;
tg:=a[t]; a[t]:=a[j]; a[j]:=tg; call F(a, t,j-1);
cal F(a, j+1,s); end;
End;
Cho dãy số : 3 1 6 0 5 4 8 2 9 7 và các bước sắp xếp sau:
Bước 1: 1 3 6 0 5 4 8 2 9 7
Bước 2: 1 3 6 0 5 4 8 2 9 7
Bước 3: 1 3 6 0 5 4 8 2 9 7
Bước 4: 0 1 3 5 6 4 8 2 9 7
Bước 5: 0 1 3 5 6 4 8 2 9 7
Bước 6: 0 1 3 5 6 2 4 8 9 7
Bước 7: 0 1 3 5 6 2 4 8 7 9
Bước 8: 0 1 3 5 6 2 4 7 8 9
Bước 9: 0 1 2 3 4 5 6 7 8 9
Các bước trên dựa theo giải thuật sắp xếp nào?
Cho dãy số "3 1 6 0 5 4 8 2 9 7" và các bước sắp xếp sau:
Bước 1: (0 1 2) 3 (5 4 8 6 9 7)
Bước 2: 0 (1 2) 3 (5 4 8 6 9 7)
Bước 3: 0 1 (2) 3 (5 4 8 6 9 7)
Bước 4: 0 1 2 3 (5 4 8 6 9 7)
Bước 5: 0 1 2 3 (4) 5 (8 6 9 7)
Bước 6: 0 1 2 3 4 5 (8 6 9 7)
Bước 7: 0 1 2 3 4 5 (7 6) 8 (9)
Bước 8: 0 1 2 3 4 5 (6) 7 8 (9)
Bước 9: 0 1 2 3 4 5 6 7 8 (9)
Bước 10: 0 1 2 3 4 5 6 7 8 9
Các bước trên dựa theo giải thuật sắp xếp nào?
Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống? Procedure F(v: integer)
Begin n:=n+1;
a[n]:=v;
upheap(n); end;
Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt (Bubble sort)
sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 7 1 9 2 5 3 6 8}. Dãy số thu được sau lần lặp thứ ba là:
Cho dãy số {3 1 6 0 5 4 8 2 9 7}. áp dụng phương pháp sắp xếp nhanh (Quick sort)
sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số thu được sau lần lặp thứ bốn là:
Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống? Procedure Downheap(k:integer)
Label 0; Begin v:=a[k];
While k<= n div 2 do begin j:=k*2;
if a[j]if v>=a[j] then goto 0; a[k]:=a[j]; k:=j;
end;
0: a[k]:=v;
End;
Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp "Chia để trị"?
Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F
Begin
For i:=1 to (n-1) do
For j:=n downto (i+1) do
if a[j] < a[j-1] then
begin tg:=a[j]; a[j]:=a[j-1]; a[j-1]:=tg; end; End;
