Lembar kerja Algoritma & kompleksitas dengan jawaban

Bagaimana cara kerja selection sort?

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Apa yang dimaksud base case pada fungsi rekursif?

1. ABaris pertama fungsi
2. BKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
3. CKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
4. DPemanggilan yang memakai memori paling banyak

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BSatu loop saja
3. CSubmasalah yang tumpang tindih dan substruktur optimal
4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah

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

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

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

1. AAkses array memerlukan O(n)
2. BKunci harus diurutkan terlebih dahulu
3. CBanyak kunci dapat bertabrakan (collision) di bucket yang sama
4. DFungsi hash lambat

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

1. An! tumbuh lebih cepat daripada 2ⁿ
2. Bn! adalah O(n²)
3. CKeduanya tumbuh dengan laju yang sama
4. D2ⁿ tumbuh lebih cepat daripada n!