Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

1. ABahasa pemrograman yang dirancang untuk menulis rumus matematika
2. BStruktur data yang menyimpan bilangan
3. CSetiap program komputer yang memiliki antarmuka grafis
4. DUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah

Bagaimana cara kerja selection sort?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

1. AO(n log n)
2. BO(1)
3. CO(n²)
4. DO(n)

Rekurens T(n) = T(n − 1) + O(1) menghasilkan apa?

1. AO(2ⁿ)
2. BO(log n)
3. CO(n)
4. DO(n²)

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray dengan panjang 2
2. BArray yang sudah terurut
3. CArray yang semua elemennya berbeda
4. DArray dalam urutan acak

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas terpendek terlebih dahulu
2. BPilih aktivitas yang dimulai paling awal
3. CPilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ATermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
2. BDapat diselesaikan dalam waktu polinomial
3. CBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
4. DTidak mungkin diselesaikan

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

1. AKunci harus diurutkan terlebih dahulu
2. BBanyak kunci dapat bertabrakan (collision) di bucket yang sama
3. CFungsi hash lambat
4. DAkses array memerlukan O(n)