PROGRAM DIPLOMA TIGATEKNOLOGI & INFORMASI UNIVERSITAS GUNADARMA PANITIAUJIANUTAMAPERIODE ITAHUN2012 PROGRAM STUDIMANAJEMEN INFORMATIKA REF.SK. REKTORUNIVERSITAS GUNADARMA NOMOR: oos/SKlREKtVclzO12 NASKAHUJIANUTAMA MATAUJIAN JENJANGIPROG. sruDl HARI/TANGGAL WAKTU
: LOGIKADANALGORITMA : DIPLOMA TtcA / MANAJEMEN tNFORMATIKA : SENIN/6PEBRUAR| 2012 : P K .0 9.00- 11"00( 120M ENTT)
NASKAHUJIANINITERDIRIDARI80 SOALPILIHANGANDA SETIAP SOALPILIHANGANDAHANYAADA SATUJAWABANI YANGBENAR. PILIHLAHSATU DARI EMPATJAWABANYANGADA. HITAMI{A.T{ LINGKARAN PADALEMBARJAWABANSESUAIPILIHANSAUDARA. 1.
Padagrafberarah(directed graph),ruas-ruasnya disebut: A. Source C. Sink B. Region D. Arkus
2.
Lintasantertutupdengansemuasimpulberderajat duadisebut: A. Walk C. Sirkuit B. Path D. Trail
3.
Banyaknya simpulatautitikpadasuatugrafdisebut: A. Size C. Order B. Diameter D. Edge
4.
Barisan simpuldanruasdi manaruashanyabolehdilewati satukalidisebut. A. Walk C, Sirkuit B. Path D. Trail
5.
Barisan simpuldanruasdi manasimpulhanyabolehdilewati satulri:iidisebut: A. Walk C. Sirkuit B. Path D. Trail
6.
Perjalanan Euleradalahperjalanan yangmelewati setiap A. Simpul C. Vertex B. Edge D. Node
7.
Masalahseorangpedagangkelilingyang mengunjungi tiap rumahsatukalidari suatutempatdan kembalike tempatsemuladalamilmu teorigraf merupakan contohklasikyangdapatdiselesaikan dengan: A. Perjalanan Hamilton C. Max-FlowProblem B. Perjalanan Euler D. Pewarnaan Graf
tepatsatukali.
UNIVERSITAS {; (INADARMA I
8.
graf G(VE) sebagaiberikuty={vl, v2, v3, v4, v5, v6} dan E=i(vl,v2), Diketahui (vl,v5),(v1,vO), (v2,v3),(v2,v4),(v3,v4),(v4,v5),(v5,v6)).Orderdarigraftersebut a d a l a h: A. 4 C.6 8.8 D. 10
9.
Lihatgrafpadasoalno.8. Sizedarigraftersebutadalah: 4.6 C.8 8,7 D.9
10. Lihatgrafpadasoalno.8. Derajatdarisimpulv5 adalah: 4.3 C.5 8.4 D.6 11. Lihatgrafpadasoalno.8. Diameter graftersebutadalah: A. 3 C.5 8,4 D.6 12. Lihatgraf padasoal no. 8. Di dalamgraftersebuttidakterdapatperjalanan Euler karena: A. Jumlahsimpulnya genap genap C. Jumlahruasnya B, Ada simpulderajatgenap D.Adasimpulderajatganjil 13. Subgrafterhubungdarisuatugrafyangtidakterkandung dalamsubgrafterhubung lainyanglebihbesardisebut: A. Komponen C. CutSet B. Trail D. Sirkuit graf G1 dan G2, makaoperasipenjumlahan 14. Jika diketahui ringdari keduagraf tersebutadalah: A. ( G1- G2 )u (c2 - c1 ) c. ( c1 - c2) n ( G2- c1) B. ( Gl n G2 )u (c2 - cl ) D. ( c1 - c2) u ( G2n Gl) 15. Grafyangsetiapsimpulnya berderajat samadisebut: A. GrafBipartisi C. GrafPlanar B. GrafSederhana D. GrafReguler 16. Grafyangdigambarkan tanpaadanyaruasyangberpotongan disebut: A. GrafBipartisi C. GrafPlanar B. GrafSederhana D. GrafReguler 17. Sebuahruasyangkeduasimpulujungnya sama,yaituel = (v,v) disebut: A. RuasTerisolasi C. RuasSejajar B. RuasBerganda D. Selfloop 18. Matriksadjacency suatugrafbersifat: A. Simetris C. T erbuka B. Tertutup D. Asimetris jikadiagonal 19, PadamatriksAdjacency utamamemiliki nilaiselain0 (not),makagraf tersebutmemiliki: A. RuasTerisolasi C. RuasSejajar B. RuasBerganda D. Setfloop UNIVERSITAS GUNADARMA 2
darisuatusimpulke simpullainnyadisebut: 20. Fanjangjalurrterpendek C. Diameter i{. Jarak D. Daun E;. Cabang ruasnyaa,Calah : graflengkap4 sinrpul,makajunnlah 21. Diketahui C.6 r A, .4 n.7 8.5 itu olelrlebihdari satu rua$,makaruas-ruas 22. Dua buahsimpulyangdilrub,ungkan disebut" C. RuasSejajar A. RuasTerisolasi looP D. S;elf B. RuasBerganda siualtu simpuldisebut: 23. Banyal
ut\tIVERitITAS GaNAD.ARMA3
32. Jika diketahuigraf G denganv = 4, e = 4, makajumlah regionnyaadalah:
4 .1 8 .2
c.3 D. 4
33. Di bawahini yangmerupakan mencariminimumspanningtreeadalah: algoritma A. Solin C. Welch-Powell B. Shamir D. Euclides jikaterdapatelemennolmakagraftersebut: 34. Padamatrikskoneksi, A. Grafreguler C. Graftidakterhubung B. Grafplanar D. 'Grafterhubung 35. Pengaturanfrekuensiradio siaran dapat diselesaikandengan menggunakan algoritma: A. Solin C. Welch-Powell B. Shannir D. Euclides 36. Daerahyangdibatasiolehsuatusirkuitdisebut; A. Arkus C. Sirkuit B. Trail D. Region 37. Kelemahan darimatriksruasadalah: A. Tidakdapatmenunjukkan adanyaruasberganda B. Tidakdapatmenunjukkan adanyaruassejajar C. Tidakdapatmenunjukkan adanyaselFloop D. Tidakdapatmenunjukkan adanyasimpulterisolir 38. Suatugraf yang diperolehdengancara membagibeberaparLia$Carisuatugraf lainolehpenambahan beberapa simpulpadaruasdisebut: A. Homomorfisrna C. lsomorfisma B. Metamorfosis D. Dualmorfisma 39. Jika diketahuisebuahgraf denganorder= v dan ruas = e, makaukuranmatriks adjacency darigraftersebutadalah: A. e xv C, exe B. vxv D. vxe 44. Daunmemilikiderajat simpulsebanyak : A. 1 C.3 B. 2 D.4 41. Suatugrafdenganv simpul,e ruasdanr regiondikatakan planarbiiamemenuhi : A. V -r+e =2 C. v*e+r =Z B. r -V +2 =e D. v- r *e=Z 42. Padadigraf,banyaknya arkusyangmasukke suatusimpuldiseliut: A. Source C. In degree B Sink D, Outdegree 43. Bilangan pewarnaan kromatis simpuldarigraflengkap 3 simpuladalah: 4.4 C.2 B. 3 D.1 ANIVE RSTTAS GUNADARMA 4
Suatugrafdengann simpuladalahtreejika : A. Terhubung dantidakmengandung sirkuit B. mempunyai (n - 1) ruas C. Bennrarna 2 D. Semuabenar 45. Berikutadalahpernyataan yangbenar,kecuali: A. Sumberadalahsimpulyangmempunyai in degree= 0 B. In degreesuatusimpuladalahbanyaknya ruas yang berakhirpada simpul tersebut C' Out degreesuatusimpuladalahbanyaknya ruas yang dimulaidari simpul tersebut. D. Sourceadalahsimpulyangmempunyai outdegree= 0 46. Diameter suatugrafterhubung adalah:
A. B. C D.
jarakantarasirnpuldarisuatugraf Maksimum jarakantarasimpuldarisuatugraf minimum jarakantarasimpul-simpul rata-rata darisuatugraf Kedalaman antarasimpul-simpul suatugraf
47 . Padadigraf,simpulyangmemiliki = 0 disebut: derajatkedalam
A. Source B. Sink
C. Muara D. Arkus
48. Kedalaman pohonbinerlengkap dengan32 simpuladalah:
A. 5 8.6
c.z
D.B
49. SebuahgrafT dikatakan Spanning TreedarigrafG jika :
A. T adalahTree B. Semuabenar
C. T adalahsubgrafdariG D.T mengandung semuasi,.npul G
50. TeknikBacktracking pertamakalidiperkenalkan oleh: A. DH lehmer C. Golomb B. RJ Walker D. Baumert 51. Dasardariteknikbacktracking adalah: A. Sorting C. Mergesort B. Bubblesort D. Searching 52. Suatufungsi yang diberikanuntukwaktutempuhdan atau kebutuhanmemori dengann inputdatadisebut: A. Running time C. Kompleksitas wakiu B. Compiler D. Waktutunda 53. Urutanpenyelesaian masalahyangbenar: A. Masalah - algoritma - model- program - eksekusi-hasil B, Masalah. - model- semialgoritma - program- eksekusi- hasil C. Masalah - model- algoritma - program:eksekusi-hasil D. Masalah* model- program- algoritma - eksekusi- hasil 54. Suatuproseduryang hanya akan berhentijika menghasilkanpenyelesaianyang diharapkan disebut: A. Instruksi C. Algoritma B. Semialgoritma D. Pseudo- code UNIVERSITAS GUNADARMA 5
hingga membentuk 55. Penghapusanruas yang berbobotterbesarberturut-turut spanning tree: algoritma Kruskal A. Spanning treeminimal, Kruskal B. Spanning algoritma treemaksimal, Solin C. Spanning algoritma treeminimal, Kruskal D. Spanning algoritma treemaksimal, derajat= 0 disebut: 56. Simpulyangmemiliki C. Simpulcabang A. Simpulbergantung D. Sim Pulter isolir B . S i mp udl a u n yangbenarmengenai TreepadagrafG denganv simpuldane 57. Berikutpernyataan ruas,kecuali: (v - 1) ruas A. G tidakmengandung sirkuitdanmempunyai sirkuit B. G terhubung dantidadkmengandung (e - 1) ruas sirkuitdanmempunyai C. G tidakmengandung (vruas D. G terhubung danmempunyai 1) adalah: 58. Yangbukandimilikiolehdua buahgrafyangisomorfis A. Jumlahsimpulnya sama B. Jumlahruasnyasama ganjilataugenapadalahsama C. Jumlahsimpulyangberderajat = j u ml a h ruas D . Ju ml a hsi mp u l 59. Pernyataan berikutbenar,kecuali: semijalur setiapduasimpulterdapat diantara A. Terhubung unilateral terjadijika semijalur setiapduasimpulterdapat diantara B. Terhubung lemahterjadijika C. Terhubung kuat terjadijika diantaradua simpulsembarangLl dan V terdapat jalurdariU ke V dandariV ke U U dan V D, Terhubungunilateralterjadijika diantaradua simpul senr'narang terdapatjalurdariU ke V ataudariV ke U masing-masing 60. TahapandalamteknikDivideand Conqueryang menyelesaikan : tahap adalah semula masalah solusi membentuk submasalah sehingga ldentifikasi C. A. Conquer D. Divide B. Combine 61. Tahapandalam teknik Divideand Conqueryang membagimnsalahmenjadi denganmasalahsemulanamun kemiripan beberapa sub masalahyangmemiliki berukuran lebihkeciladalahtahap: A, Conquer C. ldentifikasi D. Divide B . C o mb i n e 62. Jika cliketahuisuatu himpunanff = {5, 7, 9, 10, 13, 1Si, rnaka dengan = 25 menggunakan algoritmasum of subsetsuntukjumtahseluruhelemennya akandiperoleh tupel: c. ( 1,1, 0, 0, 1, 0) A. (1 ,0 , o , 1 , 1 , 0 ) D. ( 0,0, 0, 1, 1, 0) B. (1 ,0 , 0 , 1 , 0 , 0 ) dengancara DepthFirsf Searchberupatupelyang: 63. Solusiyangdiperoleh C. Terurut A. Sembarang D. Sama B. Berbeda UNIVER.STT,S GUNADARMA6
6 4 . Pada kasus MenaraHanoi,jika terdapat4 piringanmaka pemindahan piringan
yangdibutuhkan adalahsebanyak: A . 15 c. 16 8.31 D.8
65. Suatuprosesyangdapatmemanggil dirinyasendiridisebut :
A. TeknikKompitasi B. Tekniklteratif
C. TeknikRekursif D. Teknikterstruktur
66. pallm algoritma backtracking semuakemungkinan solusidaripersoalan disebut:
A. Queue B. Stack
C. Ruangsolusi D.. Fungsipembatas
6 7 . Berikutmerupakan kriteriaalgoritma yangbaik,kecuali: A. Ada output C. Jumlahlangkahnyatak hingga
B, Efisien
D. Terstruktur
68. Efisiensi suatualgoritma dilihatdari:
A B. C. D.
Running timedankebutuhan memory adaoutput Validitasnya Banyaklangkahnya terhingga
69. Berikutmerupakan keadaandarikompleksitas algoritma,kecuali.
A. Bestcase B. Averagecase
C. Worstcase D. Specialcase
7 0 . Jikadiketahuikompleksitas algoritma A adalahO(n)dan kompleksitas algoritma B adalahO(nlogn), maka: A. Algoritma A lebihlambatdaripada algoritma B B. Algoritma A lebihburukdaripada algoritma B C. Algoritma A lebihcepatdaripada algoritma B D. Algoritma A samadenganalgoritma B 7 1 . Suatukeadaanyang merupakan nilaimaksimaldari kompleksitas waktusuatu algoritma disebut: A. Bestcase C. Worstcase B. Averagecase D. Specialcase 72. Jika diketahuiT(n) = 200n2 + 456n + 29876merupakanfung,siwaktutempuh dengann inputdata,maka : A. T(n)= 911; B. T(n) = 91n;
C' T(n)= O(n') D' T(n)= O(n2)
73. Diketahui suatualgoritma sebagaiberikut: SetA[i,j],Bli,jl,Cli,jl f o r i =1 to n d o f o rj * 1 to n d o C = A+B endfor endfor UNIVERSITAS GUNADARMA 7
Algoritma di atasmerupakan algoritma untuk: penjumlahan A. Melakukan matriks B. Mencarielementerbesardarisuatuarray perkalian C. Melakukan matriks D. Mengurutkan elemendalamsuatuarray 74, Algoritmapadasoalno.73 mempunyai waktusebesar: kompleksitas = A. T(n)= 611; T(n) O(nj) C. B. T(n)= O(n) D. T(n)= O(n') 75. Diketahui suatualgoritma sebagaiberikut: functionfak(n: integer): integer ifn:=0 thenfak := 1 elsefak:= n"fak(n- 1) end function Jikaalgoritma functianfak adalah'. diatasdiberiinputn = 6, makapemanggilan A. 54 kali C. 6 kali B. 87 kali D. 7 kali 76. ..!ikadiketahuiT(n) = 100 merupakan fungsiwaktutempuhdengann inputdata, maka: A. T(n)= 911; c' T(n)= o(nl) = B. T(n) O(n) D. T(n)= O(n') = 100n+ 75634562merupakan 77. JikadiketahuiT(n) fungsiwaktutempuhdengann inputdata,maka: A. T(n)= 911; C. T(n)= O(n') = B. T(n) O(n) D. T(n)= O(n2) 78. Kelebihan teknikGreedyadalah: A. Solusilebihcepatditemukan B. Murah
C. Solusipastiditemukar, D. Semuabenar
79. Kelebihan teknikBrute Forceadalah: A. Solusilebihcepatditemukan C, Solusipastiditemukan B. Murah O. Semuabenar 80" TeknikBrute Forcekadangdisebut: A. Naivemethod C. Backtracking B. Blundermethod D. Semuasalah
ANIVERSITAS GUNADARMA 8
