Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

1. AHanya dapat diselesaikan dengan mencoba setiap kemungkinan
2. BTidak memiliki solusi
3. CDapat diselesaikan dalam waktu konstan
4. DDapat diselesaikan dalam waktu polinomial

Bagaimana cara kerja selection sort?

1. AMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
2. BBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
3. CBerulang kali menukar elemen bersebelahan yang urutannya salah
4. DMembagi array menjadi dua bagian lalu menggabungkannya

Apa syarat binary search terhadap inputnya?

1. AArray hanya boleh berisi bilangan positif
2. BArray harus terurut
3. CArray tidak boleh berisi lebih dari 1000 elemen
4. DPanjang array harus pangkat dua

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(V × E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V + E)

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 100
2. BSekitar 20
3. CSekitar 500,000
4. DSekitar 1,000

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 2
2. BGreedy memakai 3 koin; optimalnya 3
3. CGreedy memakai 2 koin; optimalnya 2
4. DGreedy memakai 4 koin; optimalnya 3

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, sehingga batas bawah itu salah
3. CYa, tetapi hanya untuk array yang lebih pendek dari 100
4. DTidak, karena insertion sort bukan pengurutan berbasis perbandingan

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AAlgoritma Prim yang dimulai dari satu simpul
2. BAlgoritma Kruskal
3. CAlgoritma Dijkstra
4. DFloyd–Warshall