Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. AInsertion sort
2. BBubble sort
3. CMerge sort
4. DQuicksort

Apa tiga langkah algoritma divide and conquer?

1. AUrutkan, cari, kembalikan
2. BDivide, conquer, combine (bagi, taklukkan, gabungkan)
3. CTebak, periksa, ulangi
4. DBaca, hitung, tulis

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang selalu memakai rekursi
2. BAlgoritma yang mencoba semua kandidat solusi yang mungkin
3. CAlgoritma yang menebak jawaban secara acak
4. DAlgoritma yang berjalan di banyak prosesor

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar √n
2. BSekitar n
3. CSekitar n / 2
4. DSekitar log₂ n

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. AAlgoritma Kruskal
2. BDepth-first search (DFS)
3. CAlgoritma Dijkstra
4. DBellman–Ford diperlukan dalam semua kasus

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. ALintasan terpendek antara semua pasangan simpul dalam O(V³)
2. BMinimum spanning tree dalam O(E log V)
3. CUrutan topologis dalam O(V²)
4. DLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)

Pernyataan mana tentang notasi little-o yang benar?

1. An² = o(n)
2. Bn = o(n²), tetapi n bukan o(n)
3. Cn = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri
4. D2n = o(n), karena 2n tumbuh lambat

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

1. AKualitasnya tidak diketahui dibandingkan optimum
2. BPaling banyak dua kali ukuran minimum vertex cover
3. CPaling banyak log n kali minimum
4. DSelalu merupakan minimum vertex cover