UNIVERSITAS GUNADARMA SK No. 92 lDikti lKep | 96 Falrultusllmu Komputer,TeknolagiIndustri, Ekonomi, Tehik Sipil dsn Perencarwan,Psikologi, Sastra Soal Ujian Akhir Semester Mata Kuliah Fakultas Jenjang Tingkat/Kelas Semester/Tahun
Perancangan & Analisis Algoritma Teknologi Industi Sl Teknik Informatika III/3IAOI- 16 PTA/2009-2010
Tanggal n lataoro Waktu 90 menit Dosen Jum.Soal 60 PG Sifat Tutup Buku
DILARANG MENCONTEK DALAM BENTT]K APAPT]N !! PILIHAN GAI\IDA 1. Algoritma adalahurutanlangkah-langlratr penyelesaianmasalahsecarasisternatis. Sebuahalgoritna tidak sajaharusbenar,tetapijuga hanrs... a. efisien c. murah b. sederhana d. banyak 2. Keistimewaandari teknik rekursif adalah a. cepat c.. memilikibanyakperulangan b. dapatmemanggildirinya sendiri d. ringkas 3. Berikut merupakankeadaandari kompleksitaswaktu, kecuali a. Best case c. Worst case b. Lower case d. Averagecase 4. Terdapattiga algoritna yaitu A, B, C dan D. Kompleksitaswaktu algoritnaa A : O(n!), Kompleksitas waktu algoritna B : O(n), kompleksitas waktu algoriha C : O(2n), kompleksitaswaktu algoritna D : O(log n). Dari keempat algoritna tersebut manakah algoritna yangmemiliki kompleksitaswaktu paling baik ? a. Algortima A c. Algoritna C b. AlgoritmaB d. AlgorifinaD 5. DiketahuiTr(n) : O(n) danTz(n): O(n),makanilai dari T1(n)+ T2(n)adalah a. o(l) b. O(logn)
UAS_PTA_09l0_Perancangan&AnalisisAlg.
c. o(n) d. O(n:)
6. Terdapatkumpulankoin sebesar9, 8, 7, 5,2, I akanditukardenganuangyangjumlahnya20. Jika menggunakanalgoritnnaGreedymaka banyaknyakoin yang harus ditukar dengan jumlatr uangtersebutadalatr a. 2 koin c. 4 koin b. 3 koin d. 5 koin 7. Untuk menjawabsoalno. 7-8 perhatikanalgoritna berikut : f o r i : I t on -.1 min: AI iJ do f o r j:i +Ito n tfAtil < A[minJthen min: A[iJ endif endfor swap (A[iJ, A[mtn]) endfor Kompleksitaswaktu algoritmatersebutjika dinyatakandalambig OH adalah a. o(l) c. O(2n)
b. o(n)
d. o(n1
8. Operasidasardari algoritmatersebutadatah a. if A[i]
UAS_PTA_0910_Perancangan&Analisis AIg.
2
13.Diketahui suatugraf sebagaiberikut A
+=
3 -B 2
Dengan menggunakan algoritma Bnrte force jika perjalanan dimulai dari simpul A dan kembali lagi ke simpul tersebutdengan melewati setiap simpul tepat satu kali, maka banyaknyalangkah yang dapatditempuhsampaiditemukanrute terpendekadalah c. 4 kali a. 6 kali d. 3 kali b. 5 kali
14.Diketahui sebuahalgoritmasebagaiberikut : functionfak(n: integer): integer tf n :: 0 thenfak:: I elsefak:: n*fak(n-I) endfunction Jika algoritna diatasberinputtr: 5, makapemanggilanulang function fak adalah a. 5 kali c. 4 kali d. 16kali b. 25 kali sebesar... 15.Algoritmapadano. 14mempunyaikompleksitas^waktu c. O(n') a. O(n)
b. o(n-l)
d. o(2n)
16.Terdapat3 tahapandalarnmeftncang algoritnaadenganmetodeDivide and Conquer..Tahap yang menggabrtngkansolusi masing-masihg sub masalah sehingga membentuk solusi masdlahsernulaadalatr a. Divide c. Conquer b. Merge d. Combine 17.Tattapan dalam algoritrna Divide and Conquer yang memecahkanmasing-masingsub masal*r secararekursifadalatrtatrap....... a. bivide c. Conquer b. Merge d. Combine 18. Sdtahsatu masalatryang dapat diselesaikandenganmenggunakanalgoritna Backtracking adalahkasusN-QueenProblem. Jika N : 4 dan posisi Ql diletakkanpadakotak baris ke-l kolom ke-I, makaposisiyangmungkindibentukuntuk Q2 adalahpadakotak.... a. Bariske-l kolom ke-2 c. Bariske-2 kolom ke-3 b. Baris ke-2 kolom ke-l d. Baris ke-2 kolom ke-2 19. Strategialgoritmayangdidasarkanpadapencarianruangsolusiadalah a. Algortima Brute force c. Algorifrna Divide and Conquer b. Algoritma Greedy d. Algortima Branchand Bound
UAS-Ff{0910-Perancangan&Analisis Alg.
3
20. Banyaknya operasi perbandinganyang dilahrkan dalarn algoritna dibawah ini adalah sebesar.. . .....
a. (n-1)kali b. n kali
maks ( at fo rk(2 to n d o If a*> maks then maks ( a1 endif endfor c. (n+1)kali d. I kali
21. Berikut merupakanelemen-elemendalarnalgoritna Greedy,kecuali a. Fungsipencarian(searching) c. Fungsiseleksi b. Fungsifeasible d. Fungsiobjektif 22. Algoritna adalahurutanlangkatr-langkahpenyelesaianmasalahsecarasistematis. SebuahalgoriUnatidak sajaharusbenar,tetapijuga harus... a. sederhana c. murah b. panjang d. efisien 23. Efisiensi algorimradinyatakandenganmeminimumkankebutuhan... a. uangdanwaktu c. numg danwaktu b. software d. hardware 24. Kebutuhanwaktu dan ruangsuatualgoritroabergantungpadaukuran... a. harddisk c. output b. input d. processor 25. Sebuahmasalahdapatmempunyailebih dari satualgoritmapenyelesaian. Efisiensialgoriha juga bergunadalam... a. penentuanbiaya c. penentuanoutput b. pemilihanalgqritma d, pemilihan PC 26. Besaranyang dipakaiuntuk menerangkanmodel abstak pengukuranwaktu dan ruang disebut... a. kompleksitasalgoritna c. kompleksitasproses b. kompleksitasmesin d. kompleksitasinput 27. Kompleksitasyang diukur dari jumlah tahapankomputasiyang dibutuhkanuntuk mer{alankanalgoritna sebagaifungsi dari ukuranrnasukann, disebut... a. kompleksitaswaktu c. kompleksitasruang b. a danc benar d. a dan c salatr
UAS-FfA_09 l0_Perancangan&AnalisisAlg.
4
28. Berikut merupakanwaktu eksekusidari beberapaalgorifina. Manakahwaktu eksekusiyangpaling cepat? a. n2o c. 2n b. n2ooo d. n2oo 29. Berikut adalahwaktu eksekusidari beberapaalgoritnaa. Manakahwaktu eksekusiyang paling lambat? a . n 2o c.2n b. n2ooo d. n'* 30. Kompleksitasalgorituaterdiri dari ... a. kompleksitaswaktu b. kompleksitasruang
c. a danb benar d. a danb salah
3l.Kompleksitas yang diukur dari memori yang digunakanoleh struktur data ymg terdapat didalamalgoritmasebagaifungsi dari ukuranmasukann, disebut... a. kompleksitaswaktu c. kompleksitasruang b. adancbenar d. adancsalah 32.AlgoritmaDivide andConquerbiasanyaditerapkanpadamasalah-masalah... a. pencarianruangsolusi c. rekursif b. iteratif d. sortingdan searching 33. MenaraHanoiadalahcontohklasik dari kasusyangdiselesaikan denganteknik.... a. sortingdan searching c. multiplicatif b. itetatif d. rekursif 34. PencdriannumgsolusipadaalgoritmaBacktrackingmenggunakan metode.... a. Divide and Conquer c. Greedy b BreadthFirst Search(BFS) d. DepthFirst Search(DFS) 35. Dalam algoritna Backhackingsemrnkemungkinansolusi dari persoalandisebut d. queue c. ruangsolusi b. stack d. fungsi pembatas 36. PadapersoalanSum of Subsetjika diketahuisuatuhimpunanyaitu {7, 8, 9, 13, l1}, maka dengan menggunakanmetode DFS untuk jumlatr seluruh elemennya29 a}orndiperoleh tupel.... a . { 1 ,0 , 1 ,0 , l } c. { 0,0, 1, 1,0} b . { 1 ,0 , 1 , 1 ,0 } d. { 1,0, 1,0,0} 37. Solusiyangdiperolehdenganmenggunakan DFS Edalahberupatupel yang........ a. sembarang c. tidak teratur b. sama d. berbeda
UAS_PfA_09l0_Perancangan&AnalisisAlg.
38.Dalam suatu graf, kunjunganke setiap simpul dengan menggunakanpencmian melebar disebut a. Depth First Search(DFS) c. Mergesort b. Breadthfirst Search(BFS) d. Binary Search 39. Diketahui suatupohon
Denganmenggunakanpencarianse&ra BreadthFirst Semch(BFS), urutanpenyelesaiannya adalah a. R r 4b,c,d,e,f,g,h a. &a,d,or B,h,b,f,c b. R,4 d, e, b, f, c, g, h d. &a"d,g,h€,b,f,c 40. Dari soal no. 39, denganmenggunakanpencariansecaraDepth First Search(DFS), urutan penyelesaiannya adalah a . & 4 b,c,d ,e ,f,g ,h c. R,4d,e,g,h,b,f,c b . F L 4d ,€ ,b ,f,c,g ,h d. &a,d,g,h,e,b,flc 41. Pencarianruangsolusi denganmenggunakanstackdisebutjuga dengan a. Binary Search c. Depth First Search(DFS) b. Mergesort d. BreadthFirst Search(BFS) 42. Algoritma GREEDY-KNAPSACK secaralangsungakanmenghasilkansolusi yang optimal, karenamenggunakansatudiantaratiga kriteria Greedy.Kriteria yang dimaksudadalah a, Memilih barangdenganberatterbesar b. Memilih barangdenganprofit terbesar c. Memilih barangdenganprofit terkecil d. Memilih barangdenganperbandinganprofit danberafiryayangterbesar 43. Algoritna SequentialSearchmemiliki kompleksitaswaktu terbaik sebesar... a. T(n): I c. T(n): nz b. T(n) : n d. T(n): Qt+ lyz
UAS_PTA-09l0_PerancanganMnalisis Alg.
6
44.Iil
d. o(2n)
b. o(n)
45. Diketatruisebuqhalgoritrra sebagaiberikut read(x); x : :x+a [k]; writeln(x); Big Oh dari algorifinadiatasadalah... c. O@2) a. O(1)
d. o(2n)
b. o(n)
46. Untuk menfawabsoalno. 4G48 perhatikanalgorifina berikut read(x); i f xmo d 2 :=0 th e n begrn x::x*l ; wnt-ln(x); end else writeln(x); perintahread(x)adalahsebanyak.... Waktu eksekusiuntuk melaksanakan a. x kali c. (x mod 2) ltali b. (x + 1) kati d. I kali 47. OperasiyangmeNrdasari algoriha diatasadalah a. x::x*l c. writeln(x) b. if x mod2:0 d. readln(x) 48. Big OH dari algoriunadiatasadatah... a. O(n) c. O(n)
b. o(2n)
d. o(l)
49. Untuk soalno. 49 - 50, perhatikanalgoritmaberikut i : : 2; w h i l e i <:n d o begin jumlah ::jumlah + a[i]; i ::i +1 : end;
UAS-FIA-09 l0-Perancangan&AnalisisA16
7
Operasiyang mendasarialgoritna tersebutadalah c. jumlatl :: jumlatr+ a[i] a. i:2 d. i::i+ l b . w h il e i <=n 50.Big OH dari algoritna diatasadalah...
a. o(n)
c. o("1
b. O(n')
d. O(n log n)
51. Padaalgoritna Cireedy,salahsatufungsi yang akanmemaksimalkanataumeminimalkan nilai solusi,danberhrjuanuntuk memilih satusajasolusiterbaik dari masing-masinganggota himpunansolusiadalah.. a. Fungsiobjektif c. Fungsiseleksi d. Fungsisubyektif b. Fungsikelayakan yangmemiliki peluanguntuk membentuksolusi 52. Himpunanyang berisi elemen-elemen disebut.. a. Himpunansimpul c. Himpunansolusi b. Himpunanbasis d. Himpunankandidat 53. DalamAlgoritrr -.Greedysecaraumum,variabelFEASIBLE merupakanvariabelbernilai .,. a. String c. Boolean b. Integer d. Char 54.DalammetodeGreedy,solusioptimaldiperolehdari... a. Secaralangsung b. Secaratidak langsung c. Secararandom d. Melalui himpunansolusiyangmungkin jenis dari SortingAlgorithm adalah 55. Yang termasukmacirm-macam a. bublesort,bruteforce,geedy b. insertionsort, quick sort,notasibig-O c. buble sort, insertionsort, selectionsort d. gtreedy,backhacking,bubblesort 56. Kompleksitaswaktu untuk kasusrata-rata(averagecase),yaitu waktu ruta-ratayang dibutuhkanuntuk mengeksekusialgoritna sebagaifungsi dari n merupakanpengertian dari... a. T*"*(n) c. T.i,,(n) b. T**(n) d. satahsemua
UAS-FTA-09l0-Perancangan&AnalisisAlg.
I
57. Pencarianstringdi dalamteksdalqmAlgoritmaBruteForcedisebutjuga dengan".. a* Patchmatching b. Text (teks) c. Shing matchingataupatternmatching d. Long sfiing 58. Algoritma Traversaluntuk graf dibagi 2 macamyaitu ... a. Pencarianmenyampingdanpencarianmeluas b. Pencarianmeluasdanpencarianmelebar c. Pencarianmelebardan pencarianmendalam d. Pencarianmeluasdanpencarianmenyamping 59. Berikut ini. adalah masalah-masalah yang dapat diselesaikanoleh algoritma backhacking, kecuali... u The-8-QueenProblem c. Hamilton cycles b. GraphColoring d. BackdoorSolve 60. Algoritna yangbiasadipakai sebagaiAnificial Intelegencepadagamesadalah... a. Bactracking c. Greedy b. Divide&Conquer d. Brute Force
UAS_PTA09 l0_Perancangan&AnalisisAlgl
9
