Olimpiade Sains Kota (OSK) 2015 - Komputer, Nomor 37–38
Deskripsi Untuk Soal Nomor 37 dan 38
Perhatikan potongan program berikut:
var
data : array[1..11] of integer = (3,9,2,6,1,4,7,8,5,10,0);
procedure kambing2(m : integer);
begin
if (m<=5) then
begin
kambing2(m*2);
kambing2(m*2+1);
write(data[m], ' ');
end;
end;37.
Jika dilakukan pemanggilan kambing2(1), maka output yang dihasilkan adalah:
a. 3
b. 3 9 2 6 1 4 7 8 5 10
c. 3 9 6 8 5 1 10 2 4 7
d. 8 5 6 10 1 9 4 7 2 3
e. 8 6 5 9 10 1 3 4 2 7
38.
Agar output yang dihasilkan terurut menaik setelah pemanggilan kambing2(1), maka array data
harus berisi:
a. (3,9,2,6,1,4,7,8,5,10)
b. (10,6,9,3,5,7,8,1,2,4)
c. (1,2,8,3,6,9,10,4,5,7)
d. (7,4,2,1,3,6,5,9,8,10)
e. (1,2,3,4,5,6,7,8,9,10)
1 jawaban
Rakha K.K.11 tahun lalu
0
Pemanggilan kambing(m*2) dan kambing(m*2+1) akan membangun pohon rekursi yang menyerupai binary tree, kira-kira seperti ini:
Pemanggilan dengan urutan tersebut (visit kiri, visit kanan, kemudian baru tulis data di node tersebut) disebut juga Post-order tree traversal, bisa dibaca di Wikipedia. Urutan visit post-order pada array tersebut (menurut node-nya) yaitu: 8,9,4,10,11,5,2,6,7,3,1.
TAPI, karena ada if (m<=5), yang akan tercetak hanya nilai-nilai dengan indeks <= 5. Urutannya menjadi : 4, 5, 2, 3, 1. Sudah jelas tidak ada jawabannya, maka anggap saja m<=5 diganti dengan m<=10, hanya indeks ke 11 yang hilang, 8,9,4,10,5,2,6,7,3,1.
-
Urutan post-order yang tadi ganti dengan nilainya: 8 5 6 10 1 9 4 7 2 3. (D)
- Agar terurut menaik (1 2 3 dst..), maka kita ganti indeks ke 8 menjadi 1, indeks ke 9 menjadi 2, dst. pada urutan visit tadi: (10,6,9,3,5,7,8,1,2,4) (B)
Abdullah Azzam Azhar10 tahun lalu
gambarnya tolong diupload lagi
Ani Yaa7 tahun lalu
kak, minta tolong gambarnya di upload lagi, kak
makasii, kak
Masuk untuk menulis jawaban
I want to be master cyber
kapan kita gunakan post order, kapan kita gunakan in- order, dan kapan kita gunakan pre-order ?