contoh soal dan pembahasan matif

CONTOH SOAL TREE

1.      

matif soal no1

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.

2.

matif soal no2

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.

3.

matif soal no3

Total bobot dari spanning tree berikut adalah … (gambar 3)

a. 24

b. 20

c. 15

d. 30

Jawaban : A

Penjelasan :

matif jawaban no3

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

(gambar1)

4.    Yang merupakan parent dan child pada pohon diatas adalah … (gambar 1)

      Jawaban : Parent : a                  Child : b c d 

      Penjelasan :

      Parent adalah predecessor langsung dari suatu node, Semua node kecuali ROOT pasti memiliki    1 PARENT yang unique.

Child adalah Successor langsung dari suatu node, semua node kecuali LEAF pasti memiliki 1     atau lebih CHILD.

5.     Tentukan pre order, in order dan post order pada tree dibawah ini :

Jawab :

Pre order    = A B W G H I P Q R S T Z C J K U V X D L E M N Y F O

In Order    = I H G P Q R S T Z A B W C J K U V X D L E M N Y F O

Post Order = I Z T S R Q P G W B X V U K N Y M L J O F E D C A

6.       Tentukan Leaf dari tree di bawah ini :

Jawab : A4, A5, A6

7.       Tentukan pre order, in order dan post order pada tree dibawah ini :

Jawab :

Pre order     = 1 2 3 4 5 6 7 8 9 10

In Order       = 7 6 8 9 10 1 4 5 3 2

Post Order  = 7 6 8 9 10 4 5 3 2 1

8.       Dari ke 3 Tree gabungkanlah menjadi binary tree :

                 

                                       

Jawab :

9.           Infix dari gambar di bawah ini adalah :

Jawab : d – e * f * a + b / c

10.          Postfix dari gambar dibawah ini adalah :

Jawab : a b c / + d e f * - *