Tugas Pertemuan 13

Multiple Choice

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

Essay

1. Cari Bobot Pohon rentang minimum dari graf dibawah ini dengan :
   a. Algoritma Prim
   b. Algoritma Kruskal
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   Jawab : 
   
   a.  Algoritma Prim
   
   
   Maka Bobotnya = 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140
   
   

   b. Algoritma Kruskal
   
   Sisi-sisi diurut menaik :
   
   

   Sisi	(1,2)	(2,3)	(2,6)	(3,5)	(5,7)	(4,7)	(4,8)	(5,8)	(3,4)	(4,5)	(6,7)	(1,4)	(2,5)	(5,6)	(7,8	(1,7)
   Bobot	5	10	15	20	25	30	35	40	45	50	55	60	65	70	75	80

   
   
   
   Maka Bobotnya = 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140
   
   
   
2. Terminologi Pohon
   Graf : 
   
   
   a. Anak dan Orang tua
   Contoh : 
   -  Simpul B,C,dan D merupakan anak dari simpul A
   -  Simpul E merupakan anak dari simpul B
   -  Simpul F dan G merupakan anak dari simpul C
   -  Simpul H,I,dan J merupakan anak dari simpul D
   -  Simpul E merupakan orang tua dari simpul K dan L
   -  Simpul Q merupakan orang tua dari simpul R dan S
   
   b. Lintasan (Path)
   Contoh : 
   -  Lintasan dari simpul A ke K adalah A,B,E,K dengan panjang lintasan ada 3
   -  Lintasan dari simpul A ke S adalah A,D,J,Q,S dengan panjang lintasan ada 4
   
   c. Keturunan (Descendant) dan Leluhur (Ancestor)
   Contoh : 
   -  Simpul B adalah leluhur dari simpul K 
   -  Simpul K adalah keturunan dari simpul B
   -  Simpul J adalah leluhur dari simpul S 
   -  Simpul S adalah keturunan dari simpul J
   
   d. Saudara kandung (Sibling)
   Contoh : 
   -  Simpul B,C,dan D adalah saudara kandung dengan orang tua yang sama yaitu simpul A
   -  Simpul H,I,dan J adalah saudara kandung dengan orang tua yang sama yaitu simpul D
   -  Simpul M dan N adalah saudara kandung dengan orang tua  yang sama yaitu simpul F
   -  Simpul R dan S adalah saudara kandung dengan orang tua yang sama yaitu simpul Q
   
   e. Upapohon (Subtree)
   Contoh : 
   -  V' = {J,P,Q,R,S}
      E' = {(J,P),(J,Q),(Q,R),(Q,S)}
       dengan J adalah simpul akar
   
   f. Derajat (Degree)
   Contoh : 
   -  Derajat simpul A : 3
   -  Derajat simpul B : 1
   -  Derajat simpul D : 3
   -  Derajat simpul F : 2
   
   g. Daun (Leaf)
   Contoh :
   -  Simpul K,L,M,N,O,P,R,S merupakan daun (leaf)
   
   h. Simpul Dalam (Internal nodes)
   Contoh : 
   -  Simpul A,B,C,D,E,F,G,J,Q merupakan simpul dalam (internal nodes)
   
   i. Aras (Level) atau tingkat
   
   
   j. Tinggi (Height) atau Kedalaman (Depth)
   Contoh : 
   -  Tinggi atau kedalaman pada pohon di atas adalah 4
   
   h. Pohon Ekspresi (expression tree)
   Contoh : 
   -  Ekspresi dari ((a + b) * (c - d)) / (e * (f + g)) adalah 
   
   
   -  Mencari nilai evaluasi dari pohon ekspresi
   

   
   
   i. Pohon keputusan (decision tree)
   Contoh : 
   
   
   j. Kode Huffman (Huffman code)
   Contoh : 
   -  Buat Kode Huffman dari "DISKRIT"
      memori yang dipakai sebesar 7 x 8 = 56 bit (7 byte)
   
   

   Huruf	Frekuensi
   D	1
   S	1
   K	1
   R	1
   T	1
   I	2

   
   
   
   
   Tabel dari kode Huffman :
   

   
   

   Huruf	Kode Huffman
   D	110
   S	111
   K	00
   R	010
   T	011
   I	10

   
   Sehingga kode Huffman untuk "DISKRIT" adalah 110101110001010011
   Dengan kode Huffman , memori yang dipakai sebesar 18 bit
   
   i. Kode Prefiks (Prefix code)
   Contoh : 
   -  
   
   
   Kode Prefiks : / * + a b - c d * e + f g