NASKAH UJIAN UTAMA MATA UJIAN JENJANG/PROG. STUDI HARI / TANGGAL
: LOGIKA DAN ALGORITMA : DIPLOMA TIGA / MANAJEMEN INFORMATIKA : Kamis / 18 FEBRUARI 2016
NASKAH UJIAN INI TERDIRI DARI 80 SOAL PILIHAN GANDA SETIAP SOAL PILIHAN GANDA HANYA ADA SATU JAWABAN YANG BENAR. PILIHLAH SATU DARI EMPAT JAWABAN YANG ADA. HITAMKAN LINGKARAN PADA LEMBAR JAWABAN SESUAI PILIHAN SAUDARA.
Untuk soal no. 1 s/d 12, gunakan graf G di bawah ini :
Graf G
1. Order dari graf G adalah … A. 5 B. 8
C. 10 D. 12
2. Size dari graf G adalah … A. 8 B. 10
C. 11 D. 12
3. Derajat graf G adalah … A. 1800 B. 90 0
C. 30 D. 24
4. Jarak antara simpul A dan simpul F pada graf G adalah … A. 2 C. 4 B. 3 D. 6 5. Diameter graf G adalah … A. 2 B. 3
C. 4 D. 6
6. Bilangan Kromatik dari graf G adalah … A. 2 B. 3
C. 4 D. 6
7. Jumlah Sirkuit pada graf G adalah … A. 6 B. 10
C. 18 D. 20
8. Simpul pada graf G yang ber-adjacent dengan simpul G adalah simpul A. A C. C B. B D. D 9. Edge dari graf G yang ber-incident dengan simpul E adalah A. AB C. CE B. FG D. CD 10. Graf G merupakan … A. Graf tidak sederhana B. Graf berarah
C. Graf sederhana D. Graf regular
11. Simpul pada graf G yang tidak adjacent dengan simpul A adalah simpul A. B C. F B. C D. G 12. Derajat simpul C dari graf G adalah A. 2 B. 3
C. 4 D. 5
Untuk soal no. 13 s/d 14, gunakan graf G1 di bawah ini :
Graf G1
13. Untuk menentukan Pohon Rentangan Minimum, dapat dilakukan dengan menggunakan Metode Prims. Dengan metode tersebut, jika diterapkan pada graf G1, maka ruas yang terpilih pada langkah kelima adalah ruas: A. GH C. AD B. HI D. BC 14. Pohon Rentangan Minimum dari graf G1 mempunyai total bobot ... A. 36 C. 44 B. 37 D. 78 15. Matriks adjacency suatu graf bersifat : A. Simetris B. Asimetris
C. Tertutup D. Terbuka
16. Perjalanan Euler adalah perjalanan yang melalui semua . . . . tepat satu kali, berawal dan berakhir pada simpul yang sama A. Ruas C. Ruas dan Simpul B. Simpul D. Graf 17. Graf Lengkap dengan 5 simpul memiliki bilangan kromatis . . . . A. 2 C. 4 B. 3 D. 5 18. Sebuah graf lengkap juga merupakan . . . . A. Graf Regular B. Tree
C. Graf Planar D. Spanning Tree
19. Graph yang tidak mengandung sirkuit disebut . . . . A. Pohon B. Loop
C. Cycle
D. Forest
20. Algoritma yang dapat digunakan untuk mencari pohon rentangan minimal adalah . . . . A. Solin, Kruskal, dan Prims C. Solin B. Solin, dan Kruskal D. Solin, Kruskal, Prims, dan Dijkstra 21. Jika diketahui graf G1 dan G2, maka operasi penjumlahan ring dari kedua graf tersebut adalah: A. (G1 - G2) U (G2 - G1) C. (G1 ∩ G2) U (G2 - G1) B. (G1 - G2) U (G2 ∩ G1) D. (G1 ∩ G2) - (G1 U G2) 22. Graf Regular adalah …. A. Graf yang setiap derajatnya sama B. Graf yang setiap sizenya berderajat sama C. Graf yang setiap ruasnya berderajat sama D. Graf yang setiap simpulnya berderajat sama 23. Maksimum jarak antara simpul pada sebuah graf terhubung G disebut : A. Jarak C. Cabang B. Diameter D. Daun 24. Matriks Ajasensi adalah . . . . A. Matriks yang baris dan kolom menghubungkan simpul dan simpul B. Matriks yang baris dan kolom menghubungkan simpul dan ruas C. Matriks yang baris dan kolom menghubungkan ruas dan ruas D. Matriks yang baris dan kolom menghubungkan simpul dan derajatnya 25. Pada sebuah graph akan ditemui bahwa: A. Banyaknya simpul yang berderajat genap adalah ganjil B. Banyaknya simpul yang berderajat ganjil adalah genap
C. Banyaknya simpul yang berderajat ganjil adalah ganjil D. Banyaknya simpul yang berderajat genap adalah genap
26. Banyaknya anggota himpunan ruas pada sebuah graph merupakan : A. Verteks Graph G C. Size Graph G B. Order Graph G D. Ruas Graph G 27. Pernyataan yang benar adalah : A. Jumlah derajat simpul-simpul sebuah graph sederhana sama dengan jumlah ruasnya. B. Jumlah ruas sebuah graph sederhana sama dengan setengah kali jumlah derajat simpulsimpulnya. C. Jumlah ruas sebuah graph sederhana sama dengan satu setengah kali jumlah derajat simpulsimpulnya. D. Jumlah derajat simpul-simpul sebuah graph sederhana sama dengan setengah kali jumlah ruasnya. 28. Suatu matriks M berordo n x n, dimana aij, bernilai p, jika ada p ruas yang menghubungkan simpul vi dengan simpul vj, disebut : A. Matrik Connection B. Matrik Ruas
C. Matrik Ajasensi
D. Matrik Incidence
29. Pernyataan yang benar adalah : A. Sebuah graph dengan n simpul, dimana n berupa bilangan ganjil dan semua simpulnya berderajat dua, akan mempunyai bilangan kromatik 2 B. Bilangan kromatik dari sebuah graph lengkap dengan n simpul adalah n-1 C. Bilangan kromatik dari sebuah graph terhubung sederhana selalu lebih dari atau sama dengan 2 D. Sebuah graph dengan n simpul, dimana n berupa bilangan genap dan semua simpulnya berderajat dua, akan mempunyai bilangan kromatik 3 30. Pernyataan yang salah tentang sebuah pohon adalah : A. Tidak mengandung sirkuit C. Memiliki bilangan kromatik 2 B. Jumlah simpul - jumlah ruas = 1 D. Semua simpulnya berderajat 2 31. Algoritma Welch – Powell dapat digunakan untuk menyelesaikan masalah: A. Graf Planar C. Minimal Spanning Tree B. Pembobotan Graf D. Pewarnaan Graf 32. Algoritma pembentukan Pohon Rentangan Minimal dengan cara penghapusan ruas dimulai dari ruas-ruas berbobot terbesar adalah : A. Algoritma Kruskal C. Algoritma Welch – Powell B. Algoritma Solin D. Algoritma Euler 33. Pada graph berarah, banyaknya arkus yang keluar ke sebuah simpul dinamakan: A. Jalur C. Sirkuit B. Derajat ke dalam D. Derajat keluar 34. Pada graph berarah, simpul yang memiliki derajat kedalam sama dengan nol disebut : A. Muara C. Sirkuit B. Sumber (Source) D. Terminal 35. Perhatikan graph G=(V,E) dibawah ini. Banyaknya simpul yang berderajat genap pada graph tersebut adalah :
A. 1 B. 2
C. 3 D. 5
Perhatikan graph berikut untuk menjawab soal nomor 36 s/d 37
36. Pernyataan yang benar untuk graph di atas, yaitu: A. Simpul H merupakan simpul muara dan Simpul A merupakan simpul sumber B. Graph tersebut memiliki satu simpul sumber dan dua simpul muara C. Derajat ke dalam simpul H tidak sama dengan derajat keluar simpul A D. Simpul A merupakan simpul muara dan Simpul H merupakan simpul sumber 37. Pernyataan yang salah tentang graph tersebut adalah A. Terdapat semi path yang menghubungkan setiap pasangan simpul B. Graph terhubung unilateral C. Graph berarah sederhana D. Graph terhubung lemah 38. Suatu urutan dari barisan langkah-langkah guna menyelesaikan masalah disebut: A. Algoritma C. Instruksi B. Semi Algoritma D. Semi Instruksi 39. Berikut ini adalah alur dari proses penyelesaian masalah: A. Masalah algoritma program model eksekusi hasil B. Masalah program model algoritma hasil C. Masalah semi algoritma model program eksekusi D. Masalah model algoritma program eksekusi hasil 40. Suatu prosedur yang hanya akan berhenti jika menghasilkan penyelesaian yang diharapkan adalah: A. Instruksi C. Semi Algoritma B. Algoritma D. Semi Instruksi Untuk soal nomor 41 sampai dengan 43 perhatikan penggalan program berikut: (1) (2) (3) (4) (5) (6)
baca bilangan bulat positif A nyatakan nilai B=0 hitung C = B x B jika C=A, maka B adalah akarnya, lalu berhenti nilai B ditambah 1 kembali ke langkah 3
41. Jika A diberi nilai 81, maka outputnya: A. 6 B. 7
C. 18 D. 9
42. Langkah-langkah tersebut “akan berhenti” bila input yang diberikan: A. 619 C. 226 B. 196 D. 254 43. Berapa kali langkah ke-3 sampai ke-4 dikerjakan bila inputnya 121 ? A. 11 kali C. 13 kali B. 12 kali D. 14 kali 44. Jika F(x) = 7 x5 + 2 x3 + 4 merupakan fungsi waktu tempuh dengan x input data, maka : A. F(x) = O (X3) C. F (x) = O (X 5) 2 B. F (x) = 2 O (X ) D. F (x) = O (X 7) 45. Berikut ini adalah yang termasuk keadaan dari kompleksitas waktu suatu algoritma : A. Average case C. Weight case B. Base case D. Random case 46. Suatu keadaan yang merupakan nilai minimum dari kompleksitas waktu suatu algoritma, disebut : A. Best case C. Worst case B. Average case D. Random case 47. Best case pada kompleksitas waktu suatu algoritma “perkalian” matriks bujur sangkar adalah: A. O (n2) C. O (3n) B. O (2 n) D. O (n3) 48. Worst case pada kompleksitas waktu suatu algoritma “penjumlahan” matriks bujur sangkar adalah: A. O (n3) C. O (3n) B. O (n2) D. O (2n) 49. Output dari algoritma (Program bahasa Basic) berikut adalah : 10 for i = 1 to 20 20 next i 30 print i A. 1 B. 20
C. 21 D. 1,2,3, … , 20
Untuk menjawab soal nomor 50 sampai 53, perhatikan algoritma berikut (1) Set k 1, loc 0 (2) REPEAT langkah (3) dan (4) WHILE loc = 0 dan k n
(3) (4) (5) (6)
A IF item = data (k) THEN loc k A k k+1 IF loc = 0 THEN WRITE ‘item tidak ada pada array data’ ELSE WRITE loc ‘adalah lokasi item’ EXIT
Array data :
19
8
67
7
10
50. Bila item = 19, maka operasi perbandingan (IF item = data (k)) akan dikerjakan sebanyak : A. 1 kali C. 3 kali B. 5 kali D. Jawaban A, B dan C salah 51. Bila item = 10, maka operasi perbandingan (IF item = data (k)) akan dikerjakan sebanyak : A. 1 kali C. 3 kali B. 5 kali D. Jawaban A, B dan C salah 52. Bila item = 69, maka operasi perbandingan akan dikerjakan sebanyak : A. 1 kali C. 17 kali B. 5 kali D. Jawaban A, B dan C salah 53. Bila jumlah data dalam array adalah n, maka keadaan rata-rata kompleksitas waktu dari algoritma tersebut adalah : A. n C. ½ (n - 1) B. ¼ (n + 1) D. ½ (n + 1) Untuk menjawab soal nomor 54 sampai 56, perhatikan algoritma berikut PROCEDURE Fibonaci (n : integer) : integer IF n 1 THEN Fibonaci = 1 ELSE F = n Fibonaci (n-1) ENDIF END_P 54. Bila input n = 6, maka outputnya adalah : A. 70 B. 120
C. 720 D. 5040
55. Untuk n = 9 terjadi pemanggilan ulang prosedur F sebanyak : A. 7 kali C. 10 kali B. 8 kali D. 9 kali 56. Bila dengan n input data, maka pemanggilan prosedur F terjadi sebanyak : A. n kali C. n! kali B. (n – 1) kali D. (n – 10) kali 57. Untuk menyelesaikan masalah menara hanoi dengan n buah piringan dibutuhkan pemindahan sebanyak : A. n2 + 1 kali C. n 2 – 1 kali B. 2n – 1 kali D. 2 n – 1 kali
58. Pada masalah menara Hanoi, bila banyaknya piringan = 6, maka dibutuhkan pemindahan sebanyak : A. 11 kali C. 35 kali B. 127 kali D. 63 kali Perhatikan algoritma berikut untuk menjawab soal nomor 59 sampai dengan 61 PROCEDURE A (n : integer) : integer IF n 2 THEN A = 1 ELSE A(n) = A (n-1) + A (n - 2) ENDIF END_A 59. Bila input data sebesar 9, maka outputnya adalah : A. 21 C. 34 B. 55 D. 89 60. Bila input data sebesar 5, maka banyaknya pemanggilan ulang prosedur A adalah : A. 6 kali C. 12 kali B. 8 kali D. 14 kali 61. Bila input data sebesar 9, maka sebanyaknya pemanggilan ulang prosedur A adalah : A. 66 kali C. 24 kali B. 40 kali D. 8 kali 62. Suatu himpunan dengan 5 elemen mempunyai himpunan bagian sebanyak : A. 5 C. 16 B. 32 D. 25 63. Pemakaian ulang metode divide and conquer dinyatakan dengan menggunakan : A. Teknik iteratif C. Teknik direktif B. Teknik rekursif D. Jawaban A, B dan C benar Untuk menjawab soal nomor 64 sampai dengan 68, perhatikan algoritma berikut. PROCEDURE STRAITMAXMIN (A, n, max, min) INTEGER i, n max min A (1) FOR i 2 to n DO IF A (i) > max THEN max A (i) ELSE IF A (i) < min THEN min A (i) ENDIF ENDIF REPEAT END STRAITMAXMIN 9 8 7 5, 64. Jika suatu array terdiri dari perbandingan-perbandingan elemen) adalah : A. 3 satuan operasi B. 4 satuan operasi
maka
waktu
tempuh
C. 6 satuan operasi D. 8 satuan operasi
(banyaknya
65. Jika suatu array terdiri dari adalah : A. 5 satuan operasi B. 10 satuan operasi
1
66. Jika suatu array terdiri dari adalah: A. 5 satuan operasi B. 10 satuan operasi
10
7
15
24
32
41
, maka waktu tempuhnya
C. 6 satuan operasi D. 12 satuan operasi 8
6
14
16
17
, maka waktu tempuhnya
C. 6 satuan operasi D. 7 satuan operasi
67. Jika suatu array terdiri dari n elemen yang disusun menaik, maka akan diperoleh waktu tempuh dengan keadaan : A. Terbaik (best case) C. Terburuk (wost case) B. Rata-rata (average case) D. Acak (random case) 68. Time complexity dari prosedur STRAITMAXMIN adalah : A. O (n 3) C. O (n) 2 B. O (n ) D. O (3n)
Untuk menjawab soal nomor 69 sampai dengan 73, perhatikan algoritma berikut. PROCEDURE MERGESORT(low,high) INTEGER low,high IF low < high THEN mid (low + high) / 2 CALL MERGESORT(low,mid) CALL MERGESORT(mid+1,high) CALL MERGE(low,mid,high) ENDIF END MERGESORT PROCEDURE MERGE(low,mid,high) INTEGER h,I,j,k,low,mid,high GLOBAL A(low:high); LOCAL B(low:high) h low; j mid + 1; i low WHILE h mid AND j high DO IF A(h) A(j) THEN B(i) A(h); h h+1 ELSE B(i) A(j); j j+1
ENDIF i i+1 REPEAT IF h > mid THEN FOR k j TO high DO B(i) A(k); i i+1 REPEAT ELSE FOR k h TO mid DO B(i) A(k); i i+1 REPEAT ENDIF FOR k low TO high DO B(k) A(k) REPEAT END MERGE 69. Pemakaian teknik DANDC banyak digunakan dalam menyelesaikan masalah, antara lain A. Searching dan Sorting C. Pencarian dan Shorting B. Sorting dan Pengurutan D. Searching dan Pencarian 70. Pada algoritma MERGESORT akan terjadi proses pemecahan masalah jika elemen-elemen tersusun secara : A. Decreasing C. Increasing B. Non decreasing D. Apapun susunannya 71. Pada masalah MERGESORT dengan 8 elemen input, akan terjadi pemanggilan ulang prosedur mergesort sebanyak A. 14 kali C. 34 kali B. 30 kali D. 36 kali 72. Pemanggilan prosedur merge dalam algoritma mergesort dengan 8 elemen input adalah A. 18 kali C. 16 kali B. 7 kali D. 15 kali 73. Time complexity masalah mergesort adalah : A. O (n2 log n) B. O (n2)
C. O(n) D. O (n 2log n)
74. Tahapan dalam teknik Divide and Conquer yang membagi masalah menjadi beberapa sub masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil adalah tahap : A. ldentifikasi B. Conquer
C. Divide
D. Combine
75. Jika diketahui suatu himpunan A = {15, 17, 19, 20, 23, 25}, rnaka dengan menggunakan algoritma sum of subsets untuk jumlah seluruh elemennya = 55 akan diperoleh tupel : A. (1, 0, 0, 1, 1, 0) C. (1, 0, 0, 1, 0, 0) B. (1, 1, 0, 0, 1, 0) D. (0, 0, 0, 1, 1, 0) 76. Solusi yang diperoleh dengan cara Depth First Search berupa tupel yang : A. Sembarang C. Sama B. Tidak Seragam D. Berbeda 77. Pada kasus Menara Hanoi, jika terdapat 5 piringan maka pemindahan piringan yang dibutuhkan adalah sebanyak: A. 15 C. 31 B. 16 D. 63 78. Suatu proses yang dapat memanggil dirinya sendiri disebut : A. Teknik Kompilasi C. Teknik Iteratif B. Teknik terstruktur D. Teknik Rekursif Untuk soal no. 79 s/d 80, gunakan graf X dan Graf Y di bawah ini : Jika Graf X merupakan penyajian pohon dari ruang penyelesaian dalam BFS, sedangkan Graf Y merupakan penyajian pohon dari ruang penyelesaian dalam DFS, untuk 3 tuple dapat digambarkan seperti di bawah ini.
Graf X
79. simpul 7 pada graf X adalah sama dengan … A. Simpul I pada graf Y B. Simpul J pada graf Y
Graf Y
C. Simpul K pada graf Y D. Simpul L pada graf Y
80. simpul 6 pada graf X adalah sama dengan … A. Simpul I pada graf Y B. Simpul J pada graf Y
C. Simpul K pada graf Y D. Simpul L pada graf Y
