Soal Algoritma dan Struktur Data (2006)

Soal Algoritma dan Struktur Data PRA S2 UGM

(catatan Marinus Ign J. Lamabelawa)

{Soal PRA 7 Agustus 2006}

1. Tersedia array A dengan panjang 100. Buatlah function rekursif untuk menghitung partial-sum-array(PSA) dari A. PSA(i) adalah jumlah nilai elemen A[1] s.d. A[i]. Contoh :

2. Function berikut adalah function untuk menukar urutan karakter menjadi selang seling, urutan ganjil dahulu kemudian urutan genap. Misal st bernilai ‘ABCDEFG’ maka hasil dari procedure ini adalah ‘ACEGBDF’. Ubahlah function tersebut menjadi rekursif;

Function tukarurutan(st : string):string;

Var i : integer;

h1,h2 : string;

begin

i:=1; h1:=’ ’; h2:=’ ‘;

while (i <= length(st) ) do begin

h1:=h1 + st[i];

if ( i <>

i := i + 2;

end;

Result :=h1 + h2;

end;

3. Tulis fungsi dalam Pascal untuk menentukan apakah suatu pohon adalah :

   1. Pohon biner complete

   2. Pohon biner almost complete

4. Data 19, 11, 13, 2, 9, 50, 7, 1, 18, 27 ingin dimasukan dalam pohon AVL. Tunjukan dengan ilustrasi pertumbuhan pohon AVL yang awalnya kosong dan gambarkan juga proses rotasinya.

5. Gambarkan graph berarah G dengan kriteria sbb :

• 5 vertkes = A,B,C,D,E

• 8 edge

• Tidak ada loop

1. Gambarkan minimum spanning tree dari G

2. Berikan bobot pada setiap edge dan terapkan algoritma Dijkstra untuk mencari lintasan terpendek dari Vertkes A.

Silahkan didiskusikan....