Tugas Matematika Informatika 4

Soal-Soal Tree

Gambar 1 

1. Dari gambar 1 berikut yang merupakan tree adalah …
a. G1 dan G3 
b. G3 dan G4 
c. G2 dan G4 
d. G1 dan G2
Jawaban : D 
Penjelasan : Disebut tree karena setiap komponen dalam graph terhubung dengan lintasan tunggal dan tidak mengandung sirkuit yaitu G1 dan G2, sedangkan G3 mengandung sirkuit yaitu pada titik adf dan G4 merupakan forest karena mengandung dua tree.

Gambar 2
 

2. Dari gambar 2 berikut yang merupakan spanning tree dari graf G adalah … 
a. T1,T2 
b. T3,T4 
c. T1,T3,T4 
d. Benar semua 
Jawaban : D 
Penjelasan : Spanning tree memiliki lintasan tunggal dan tidak mengandung sirkuit dan dari gambar tersebut semuanya merupakan spanning tree. 

Gambar 3

3. Total bobot dari spanning tree berikut adalah … (gambar 3)
a. 24
b. 20
c. 15
d. 30
Jawaban : A
Penjelasan : 

Terlihat bahwa spanning tree tersebut mempunyai total bobot 2 + 3 + 4 + 4 + 4 + 4 + 3 = 24

Gambar 4

4. Yang merupakan parent dan child pada pohon diatas adalah … (gambar 4)
a. Parent : b Child : a c d 
b. Parent : a Child : b c d 
c. Parent : k Child : g d a 
d. Parent : b Child : h I j
Jawaban : B

Penjelasan : Parent merupakan komponen yang berada diatas child dan child merupakan cabang dari parent tersebut sehingga dari pilihan diatas yang benar adalah a sebagai parent dan b c d sebagai child karena merupakan cabang dari a.

5. Simpul yang berderajat 2 adalah simpul … (gambar 4)
a. b, k
b. d, g
c. c, f, h, I, j, l, m
d. a, e
Jawaban : A
Penjelasan : Derajat sebuah simpul adalah jumlah anak pada simpul tersebut sehingga simpul yang memiliki anak 2 adalah b dan k.

6. Tinggi atau kedalaman pohon tersebut adalah … (gambar 4)
a. 3
b. 4
c. 5
d. 6
Jawaban : B
Penjelasan : Level maksimum dari suatu pohon disebut tinggi atau kedalaman pohon. Level pohon tersebut adalah 0 sampai 4 sehingga level maksimumnya adalah 4.

Gambar 5

7. Infix dari gambar 5 adalah …
a. b / c + a * d – e * f
b. d – e * f * b / c + a
c. a + b / c * d – e * f
d. d – e * f * a + b / cJawaban : CPenjelasan : Urutan infix adalah operand operator operand dan cara menentukan infix adalah melihat dari letaknya dalam pohon yaitu kiri tengah kanan.

8. Prefix dari gambar 5 adalah … 
a. * + a / b c – d * e f 
b. + a / b c * – d * e f 
c. * – d * e f + a / b c 
d. – d * e f * + a / b c 
Jawaban : A 
Penjelasan : Urutan prefix adalah operator operand operand dan cara menentukan prefix adalah melihat dari letaknya dalam pohon yaitu tengah kiri kanan.

9. Postfix dari gambar 5 adalah … 
a. d e f * + a b c / * - 
b. a b c / + d e f * * - 
c. d e f * + a b c / – * 
d. a b c / + d e f * – * 
Jawaban : D 
Penjelasan : Urutan postfix adalah operand operand operator dan cara menentukan postfix adalah melihat dari letaknya dalam pohon yaitu kiri tengah kanan.

10. Berikut ini merupakan sifat tree, kecuali … 
a. graf tak berarah yang terhubung 
b. graf berarah yang terhubung 
c. tidak memiliki sirkuit 
d. lintasan tunggal 
Jawaban : B 
Penjelasan : Tree merupakan graf tidak berarah sehingga jawaban B salah.