Lembar kerja Algoritma & kompleksitas dengan jawaban

Bagaimana cara kerja selection sort?

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

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu polinomial
2. BDapat diselesaikan dalam waktu konstan
3. CTidak memiliki solusi
4. DHanya dapat diselesaikan dengan mencoba setiap kemungkinan

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. AMerge sort sudah O(n)
2. BDynamic programming hanya bekerja pada masalah graf, bukan pada array
3. CMerge sort tidak memiliki struktur rekursif
4. DSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang

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

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

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

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

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

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

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

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