Latihan Pertemuan 13
A. Pilihan Ganda
1. Graf tak berarah terhubung yang tidak mengandung sirkuit disebut…….
a. Pohon
b. Binary
c. Akar
d. Level
e. Anak
2. Sisi pada pohon rentang disebut dengan……
a. Tali hubung
b. Cabang
c. akar
d. Rank
e. Upapohon
3. Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah…….
a. Algoritma Prim
b. Algoritma Kruskal
c. Traveling Salesman
d. a dan c benar
e. a dan b benar
4. Di bawah ini yang bukan terminologi pohon adalah……
a. Anak
b. Lintasan
c. Sirkuit
d. Derajat
e. Daun
5. Pohon biner dengan daun berupa operand dan simpul dalam berupa operator disebut dengan pohon………
a. Keputusan
b. Huffman
c. Prefiks
d. Ekspresi
e. Pencarian biner
B. Esai
1. Buat pohon rentang minimum berdasarkan
a) Algoritma prim
total bobot minimum : 2 + 3 + 4 + 5 + 12 + 16
= 42
b)Algoritma kruskal
Sisi diurut dari terkecil :
Total bobot minimum : 3 + 4 + 4 + 5 + 5
= 21
2. Buatlah gambar teminologi pohon :
1) Anak dan orang tua
B dan c adalah anak dari simpul a, dimana a adalah orang tua mereka. D,e,f,g adalah anak dari b, dimana b adalah orang tua mereka.
2) Lintasan
Lintasan dari a ke j adalah a,b,d,j dengan panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan k-1 ada 3.
3) Keturunan dan Leluhur
B adalah leluhur simpul d, dan d adalah keturunan b.
4) Saudara Kandung
-Simpul k,l merupakan saudara kandung karena orang tua mereka sama, yaitu simpul e.
- Simpul n,o merupakan sauara kandung karena orang tua mereka sama, yaitu simpul g.
5) Upa pohon
6) Derajat
Derajat a adalah 2, derajat b adalah 4, derajat c adalah 2.
Derajat maksimum dari sebuah simpul merupakan derajat pohon itu sendiri. Pohon pada gambar berderajat 4.
7) Daun
h ,i ,j,k,l,m,n,dan o adalah daun.
8) Simpul dalam
b,c,d,e,f,dan g adalah simpul dalam.
9) Aras
10) Tinggi atau kedalaman.
Tinggi atau kedalamannya adalah 3.
11) Pohon ekspresi
(a + b) * (c/(d + e))
= (6 + 4) * (9/(1 + 2))
= 10 * (9/3)
= 10 * 3
= 30
12) Pohon keputusan
13) Kode Huffman
String AABABCCDABCD
14) Kode Prefiks
Kode prefiks = (“AB + BC”)
Anggota kelompok ;
Ø Chika Adelia (12190217)
Ø Kenny Agusti Leobardo Boyani (12190210)
