ý tưởng phương pháp sắp xếp vun đống (Heap sort) là:
A. Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại phần tử gốc ra khỏi cây đưa vào dãy sắp xếp.
B. 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.
C. Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
D. Tạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).
Giải bởi Vietjack
Chọn đáp án A
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?
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 F(v: integer)
Begin n:=n+1;
a[n]:=v;
upheap(n); end;
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;
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à:
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ị"?
