Kuis M9 - Backtracking KHUSUS KELAS PAGI [PDF]

Citation preview

5/7/2021



1 pesan baru



Dashboard My courses  ATA 2020/2021 | 3-FTI | Terapan Teori Graf | TEAM TEACHING  Pertemuan M9 - Backtracking  Kuis M9 - Backtracking (KHUSUS KELAS PAGI)



Started on Friday, 7 May 2021, 1:54 PM State Finished Completed on Friday, 7 May 2021, 2:03 PM Time taken 9 mins 6 secs Grade 100.00 out of 100.00 Question 1 Correct Mark 5.00 out of 5.00



Kemungkinan penempatan 8 buah bidak Ratu (8-Queen) pada suatu papan catur 4 x 4 secara sembarang tanpa ada syarat khusus adalah (8×8)!/(8×7)!= Select one: a. 16.777.216 kemungkinan b. 40.320 kemungkinan c. 4.426.165.368 kemungkinan  d. 12 kemungkinan.



Question 2 Correct Mark 5.00 out of 5.00



Diketahui 3 Kartu yang terdiri dari 2 Kartu Merah dan 1 Kartu Kuning. Ketiga kartu akan ditempatkan pada 3 posisi yang berurutan, dengan syarat Kartu Kuning tidak diizinkan berada di posisi tengah. Banyaknya cara untuk menyusun ketiga kartu tersebut adalah: Select one: a. 5 cara solusi b. 4 cara solusi  c. 3 cara solusi d. 2 cara solusi



Question 3 Correct Mark 5.00 out of 5.00



Bounding Function (Solusi Akhir) permasalahan Colouring Graph adalah: Select one: a. Mewarnai simpul-simpul dan ruas-ruas dalam Graf sedemikian sehingga tidak ada 2 simpul bertetangga dan 2 ruas bersisian yang mempunyai warna sama. b. Mewarnai simpul-simpul dalam Graf sedemikian sehingga tidak ada 2 simpul bertetangga yang mempunyai warna sama.  c. Mewarnai simpul-simpul dalam Graf sedemikian sehingga semua simpul satu sama lain mempunyai warna berbeda d. Mewarnai ruas-ruas dalam Graf sedemikian sehingga tidak ada 2 ruas bersisian yang mempunyai warna sama.



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



1/7



5/7/2021



1 pesan baru



Question 4 Correct Mark 5.00 out of 5.00



Langkah-langkah pencarian solusi pada algoritma backtracking, jika posisi terakhir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak (sibling) yang lainnya, dan jika tidak ada simpul anak (sibling) maka dilakukan : Select one: a. Branch & Bounding ke simpul akar b. Backtracking ke simpul induk.  c. Backtracking ke simpul akar d. Branch & Bounding ke simpul induk



Question 5 Correct Mark 5.00 out of 5.00



Diketahui 3 Kartu yang terdiri dari 2 Kartu Merah dan 1 Kartu Kuning. Ketiga kartu akan ditempatkan pada 3 posisi yang berurutan, dengan syarat Kartu Kuning tidak diizinkan berada di posisi tengah. Ada berapa banyak seluruh kemungkinan solusi yang dibangun bila menggunakan algoritma Back Tracking.: Select one: a. 4 kemungkinan solusi  b. 6 kemungkinan solusi c. 5 kemumgkinan solusi d. 3 kemungkinan solusi



Question 6 Correct Mark 5.00 out of 5.00



Algoritma Backtracking dapat dikatakan lebih sebagai penyempurnaan dari : Select one: a. Algoritma Branch & Bound b. Algoritma Welch Powel c. Algoritma Brute Force  d. Algoritma Kruskal



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



2/7



5/7/2021



1 pesan baru



Question 7 Correct Mark 5.00 out of 5.00



Kompleksitas Waktu membangun Pohon pada Permasalahan Colouring Graph adalah : Select one: a. O( N X N) b. O( N!)  c. O( N) d. O(Log N)



Question 8 Correct Mark 5.00 out of 5.00



Salah satu fungsi yang dimiliki oleh algoritma backtracking dan menjadi ciri khasnya adalah fungsi pemangkasan (pruning). Andaikan tahap-tahap pencarian solusi suatu masalah direpresentasikan dalam bentuk pohon solusi, proses pemangkasan akan dilakukan terhadap simpul-simpul : Select one: a. Yang mengarah kepada solusi b. Yang tidak mengarah ke simpul induk c. Yang tidak mengarah kepada solusi.  d. Yang mengarah ke simpul induk



Question 9 Correct Mark 5.00 out of 5.00



Tahap-tahap pencarian solusi yang ditelusuri oleh algoritma Bactracking dapat dimisalkan sebagai suatu pohon solusi berbentuk: Select one: a. Pohon Berdaun b. Pohon Sintaks (Syntax Tree) c. Pohon Rentangan (Spanning Tree) d. Pohon Berakar (Rooted Tree) 



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



3/7



5/7/2021



1 pesan baru



Question 10 Correct Mark 5.00 out of 5.00



Langkah-langkah pencarian solusi pada algoritma backtracking, jika lintasan yang diperoleh dari perluasan simpul-E (Expand Node) tidak mengarah ke solusi, maka simpul itu akan menjadi : Select one: a. Simpul mati yang tidak dapat diperluas lagi.  b. Simpul Daun yang berguguran c. Simpul hidup yang terus di-expand d. Simpul Akar yang ditanam



Question 11 Correct Mark 5.00 out of 5.00



Jumlah solusi untuk menempatkan 5 ratu pada 5 × 5 papan catur, baik solusi Dasar maupun solusi Semua masing-masing adalah: Select one: a. 92 dan 724 b. 1 dan 2 c. 12 dan 92 d. 2 dan 10 



Question 12 Correct Mark 5.00 out of 5.00



Backtracking (Runut-balik) adalah algoritma yang berbasis pada …. untuk mencari solusi persoalan secara lebih mangkus. Select one: a. DFS (Depth-First Search)  b. BFS (Breadth-First Search) c. Post Order Traversal d. In Order Traversal



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



4/7



5/7/2021



1 pesan baru



Question 13 Correct Mark 5.00 out of 5.00



Diketahui 3 Kartu yang terdiri dari 2 Kartu Merah dan 1 Kartu Kuning. Ketiga kartu akan ditempatkan pada 3 posisi yang berurutan, dengan syarat Kartu Kuning tidak diizinkan berada di posisi tengah. Ada berapa banyak seluruh kemungkinan solusi yang dibangun bila menggunakan algoritma Brute Force: Select one: a. 4 kemungkinan solusi b. 5 kemumgkinan solusi c. 3 kemungkinan solusi d. 6 kemungkinan solusi 



Question 14 Correct Mark 5.00 out of 5.00



Algotitma Brute force dan Backtracking, keduanya adalah algoritma yang mencari solusi dari suatu masalah dengan cara membuat kandidat-kandidat solusi secara bertahap. Pada pencarian solusi dengan brute force, Select one: a. Program akan berhenti memproses suatu kandidat solusi segera setelah sampai pada suatu tahap dimana kandidat solusi tersebut terbukti tidak mengarah pada solusi akhir (bounding function). b. Program akan melakukan penelusuran secara Depth First Searh (DFS) c. Program akan melakukan penelusuran secara Pre Order Traversal d. Program akan membuat seluruh kemungkinan solusi, baru kemudian menguji satu persatu apakah solusi yang telah dibuat dapat memenuhi spesifikasi solusi akhir (bounding function) yang dicari. 



Question 15 Correct Mark 5.00 out of 5.00



Bounding Function (Solusi Akhir) pada permasalahan Sum Of Subset adalah: Select one: a. Mencari subset-subset yang memiliki jumlah sama dengan M  b. Mencari subset-subset yang memiliki jumlah lebih kecil sama dengan M c. Mencari subset-subset yang memiliki jumlah lebih kecil dari M d. Mencari subset-subset yang memiliki jumlah lebih besar dari M



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



5/7



5/7/2021



1 pesan baru



Question 16 Correct Mark 5.00 out of 5.00



Pencarian solusi pada algoritma backtracking dihentikan jika: Select one: a. Telah ditemukan simpul daun (leaf) b. Telah ditemukan solusi atau tidak ada simpul hidup yang dapat ditemukan.  c. Telah ditemukan simpul induk (parent) d. Telah ditemukan simpul anak (sibling)



Question 17 Correct Mark 5.00 out of 5.00



Solusi pada algoritma backtracking dicari dengan membentuk lintasan dari akar ke daun. Simpul yang telah dilahirkan dinamakan simpul hidup dan simpul hidup yang diperluas dinamakan : Select one: a. Simpul-E (Expand node)  b. Simpul Akar c. Simpul Daun d. Simpul Mati



Question 18 Correct Mark 5.00 out of 5.00



Algoritma backtracking adalah sebuah algoritma yang berbasis depth-first search (DFS) yang dibangun secara dinamis dalam pencarian solusi pada : Select one: a. Pohon Ruang Status (State Space Tree)  b. Pohon Sintaks (Syntax Tree) c. Pohon Biner ( Binary Tree) d. Pohon Rentangan (Spanning Tree)



Question 19 Correct Mark 5.00 out of 5.00



Mekanisme penyelesaian dengan menggunakan backtracking berprinsip pada metode: Select one: a. Iteratif b. Interaktif c. Rekursif  d. Kondusif



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



6/7



5/7/2021



1 pesan baru



Question 20 Correct Mark 5.00 out of 5.00



Algoritma backtracking pada tahun 1950 pertama kali diperkenalkan oleh: Select one: a. Baumert b. Rwalker c. Golomb d. D.H. Lehmer 



◄ Materi M9 - Backtracking Jump to...



https://v-class.gunadarma.ac.id/mod/quiz/review.php?attempt=3410069&cmid=584998



7/7