Contoh Soal
Graf & Analisis Algoritma
1. Orang yang dikenal sebagai bapak dari lahirnya (awal) teori graf adalah :
A. Solin dan Kruskal
- Hamilton
- Welch-Powell
- Leonhard Euler
2. Bila size dari suatu graf adalah n, maka jumlah derajat grafnya adalah :
A. 2n-1
- 2 (n-1)
C. 2n
- 2n+1
3. Pada pohon, simpul yang bukan merupakan akar dan berderajat simpul 1 adalah :
A. Cabang
B. Daun
C. Brother
D. Level
4. Suatu bentuk graf yang terbentuk karena penambahan sejumlah vertex baru terhadap graf asal disebut :
A. Isomorfis
B. Isograf
C. Homomorfis
D. Isographic
5. Suatu tree yang mempunyai cabang / anak selalu 2 disebut :
A. Unary tree
B. Binary tree
C. Union tree
D. Threenary Tree
6. Graf yang tidak memiliki self loop atau ruas sejajar disebut :
A. multigraf
B. graf sederhana
C. graf null
D. graf lengkap
7. Algoritma Welch-Powell digunakan untuk mencari :
A. Minimal Spanning Tree
B. Aliran Maksimal
C. Bilangan Kromatik
D. Jalur Terpendek
8. Perjalanan (walk) yang semua simpul dalam barisan berbeda adalah
A. jalur (path)
B. lintasan ( trail)
C. sirkuit (cycle)
D. diameter
9. Graf regular adalah graf yang memiliki :
A. gelung atau self-loop
B. ruas sejajar
C. derajat setiap simpulnya berbeda
D. derajat setiap simpulnya sama
|
Untuk soal no. 10 s/d 16, gunakan graf di bawah ini :
10. Order dan Size dari graf G1 adalah :
A. 4 dan 12
B. 12 dan 16
C. 12 dan 17
D. 16 dan 12
11. Derajat dari graf G1 adalah :
A. 12
B. 24
C. 32
D. 34
12. Bilangan Kromatik dari graf G1 adalah :
A. 2
B. 3
C. 4
D. 5
13. Pada pewarnaan graf G1, simpul yang boleh menggunakan warna yang sama adalah :
A. A dan L
B. A dan B
C. C dan H
D. B dan H
14. Jarak antara simpul A dan G pada graf G1 adalah :
A. 2
B. 3
C. 4
D. 5
15. Graf G1 mempunyai diameter :
A. 2
B. 3
C. 4
D. 5
16. Yang merupakan jalur (path) dalam graf G1 adalah :
A. A,B,C,H,A
B. E,D,K,J,C,D
C. A,L,K,F
D. A,H,C,J,F
17. Graf G2 berikut ini, mempunyai region sebanyak :
| |||||||||||||
A. 2
B. 3
C. 4
D. 5
18. Pembuatan jadwal kuliah pada suatu Perguruan Tinggi dapat diselesaikan dengan membawanya ke masalah graf, yakni masalah :
A. jalur terpendek
B. minimal spanning tree
C. pewarnaan graf
D. travelling salesman
19. Matriks adjasensi suatu graf bersifat :
A. simetris
B. refleksif
C. transitif
D. antisimetris
20. Pada graf berarah, simpul yang mempunyai derajat kedalam = 0 disebut :
A. muara
B. sumber
C. terpencil
D. artikulasi
21. Pada graf berarah, simpul yang mempunyai derajat keluar = 0 disebut :
A. muara
B. sumber
C. terpencil
D. artikulasi
22. Formula Euler untuk graf planar; dimana V adalah banyaknya simpul, E banyaknya ruas dan R banyaknya region, adalah :
A. V - R + E = 2
B. V - E + R = 2
C. V - E + 2 = R
D. V + E - R = -2
23. Yang bukan merupakan graf planar adalah :
A. graf kubus
B. graf segitiga
C. graf berbentuk pohon
D. graf lengkap dengan 5 simpul (K5)
24. Manakah dari pernyataan berikut yang paling benar ?
- Graf Regular juga merupakan Graf Lengkap
- Graf Lengkap juga merupakan Graf Regular
- Graf Bipartisi juga merupakan Graf Regular
- Graf Regular juga merupakan Graf Bipartisi
25. Bilangan Kromatik dari graf bipartisi adalah :
- 2
- 3
- 4
- 5
26. Suatu urutan dari barisan langkah-langkah guna menyelesaikan masalah disebut :
A. algoritma
B. semi algoritma
C. instruksi
D. semi instruksi
27. Suatu prosedur yang hanya akan berhenti jika menghasilkan penyelesaian yang diharapkan disebut :
A. algoritma
B. semi algoritma
C. instruksi
D. semi instruksi
28. Diagram alur dari proses penyelesaian masalah, yang paling benar adalah :
A. masalah ® semi algoritma ® model ® program ® eksekusi ® hasil
B. masalah ® model ® algoritma ® program ® eksekusi ® hasil
C. masalah ® algoritma ® model ® program ® eksekusi ® hasil
D. masalah ® program ® algoritma ® model ® eksekusi ® hasil
29. Penilaian dari suatu algoritma pertama kali dilihat dari :
A. efisiensi
B. efektivitas
C. terstruktur
D. ada output
30. Yang bukan termasuk kriteria dari suatu algoritma yang terbaik adalah :
A. efisiensi
B. terstruktur
C. berakhir
D. prosesnya cepat
31. Jika diketahui F(x) = 20 x7 + 12 x4 + 38 merupakan fungsi waktu tempuh, maka
A. F(x) = O(20 x7)
B. F(x) = 20 O(x7)
C. F(x) = O(x7 + x4)
D. F(x) = O(x7)
32. Bila terdapat 4 algoritma sorting (kita sebut algoritma A, B, C dan D), dimana algoritma A memiliki kompleksitas O(n2), algoritma B memiliki kompleksitas O(n3), algoritma C memiliki kompleksitas O(log n), dan algoritma D memiliki kompleksitas O(n), maka algoritma manakah dari keempat algoritma tersebut yang lebih baik ?
A. algoritma A
B. algoritma B
C. algoritma C
D. algoritma D
33. Diberikan sebuah algoritma sebagai berikut :
Set A[i,j], B[i,j], C[i,j] real
untuk i 1 s/d n kerjakan
untuk j 1 s/d n kerjakan
C[i,j] A[i,j] + B[i,j]
akhir j
akhir i
Algoritma diatas merupakan algoritma untuk :
A. melakukan penjumlahan matriks
B. melakukan perkalian matriks
C. melakukan penjumlahan
D. melakukan perkalian
34. Algoritma pada soal nomor 33 mempunyai kompleksitas waktu :
A. O(n)
B. O(n2)
C. O(log n)
D. O(n3)
35. Diberikan sebuah algoritma sebagai berikut :
Function RAT (n : integer) : integer
If n := 1 then RAT := 1
Else RAT := n * RAT(n-1)
End Function
Algoritma di atas menggunakan teknik :
A. Backtracking
B. Rekursif
C. Greedy
D. Iteratif
36. Bila Algoritma pada soal nomor 35 berinput n = 5, maka outputnya adalah :
A. 120
B. 720
C. 7
D. 5040
37. Bila Algoritma pada soal nomor 35 berinput n = 5, maka pemanggilan ulang function RAT adalah :
A. 1 kali
B. 4 kali
C. 5 kali
D. n kali
38. Algoritma pada soal nomor 35 mempunyai kompleksitas waktu :
A. O(n)
B. O(log n)
C. O(n2)
D. O(n3)
39. Diberikan sebuah algoritma sebagai berikut :
Set x, y, n, i, f : integer
x 1 ; y 1
If n 2 then
begin
for i 3 to n do
begin
F x + y
x y
y F
end
end
else
F x
Write(F)
End
Algoritma di atas menggunakan teknik :
A. Iteratif
B. DANDC
C. Greedy
D. Rekursif
40. Bila Algoritma pada soal nomor 39 berinput n = 13, maka outputnya adalah :
A. 55
B. 233
C. 89
D. 144
41. Algoritma pada soal nomor 39 mempunyai keadaan kompleksitas waktu :
A. keadaan terbaik ¹ keadaan terburuk
B. keadaan terbaik = keadaan terburuk
C. keadaan terbaik > keadaan terburuk
D. keadaan terbaik < keadaan terburuk
kak, gambar grafnya dong.. kok gk adaa sih
BalasHapus