ADA-GSL2425-FIN_EX-B

Apa tujuan utama dari penggunaan Balanced Search Trees?

• Untuk meningkatkan kecepatan pencarian
• Untuk mengurangi penggunaan ruang memori
• Untuk menambah kompleksitas dalam pencarian
• Untuk mengurangi kompleksitas dalam pencarian

Answer explanation

Penjelasan: Balanced search trees digunakan untuk memastikan bahwa pohon tetap seimbang, yang meminimalkan tinggi pohon dan, oleh karena itu, mengurangi kompleksitas operasi pencarian, penyisipan, dan penghapusan.

Apa yang dimaksud dengan heapify dalam konteks heap?

• Proses menambah elemen baru ke dalam heap
• Proses menghapus elemen dari heap
• Proses untuk mempertahankan sifat heap setelah perubahan
• Proses untuk mengurutkan elemen dalam heap

Answer explanation

Penjelasan: Heapify adalah proses untuk memastikan bahwa sebuah pohon biner memenuhi sifat heap. Misalnya, setelah menyisipkan atau menghapus elemen, kita perlu memastikan bahwa pohon masih memenuhi sifat heap dengan memodifikasi posisi elemen-elemen dalam pohon.

Apa yang dimaksud dengan max-heap?

• Heap di mana setiap simpul memiliki nilai lebih kecil dari kedua anaknya
• Heap di mana setiap simpul memiliki nilai lebih besar dari kedua anaknya
• Heap yang hanya dapat diakses melalui indeks tertentu
• Heap yang disusun dalam urutan menaik

Answer explanation

Penjelasan: Pada max-heap, nilai setiap simpul harus lebih besar dari atau sama dengan nilai anak-anaknya, sehingga elemen terbesar berada di root dan dapat diekstraksi terlebih dahulu dalam proses Heapsort.

Apa waktu kompleksitas dalam menghapus elemen root dari heap?

• O(1)
• O(log n)
• O(n)
• O(n log n)

Answer explanation

Penjelasan: Setelah elemen root dihapus, elemen terakhir dalam heap akan dipindahkan ke root, dan kemudian dilakukan heapify untuk memastikan pohon kembali memenuhi sifat heap. Proses heapify ini membutuhkan waktu O(log n), sehingga kompleksitas penghapusan adalah O(log n).

Salah satu contoh space-for-time trade-off yang umum adalah:

• Menggunakan struktur data hash untuk mengurangi waktu pencarian
• Menggunakan algoritma pengurutan untuk mempercepat pencarian
• Menggunakan algoritma rekursif untuk mengurangi ruang
• Menyimpan hasil komputasi sebelumnya dalam cache untuk menghemat ruang

Answer explanation

Penjelasan: Dengan menggunakan struktur data hash, kita dapat mengurangi waktu pencarian secara signifikan, meskipun membutuhkan lebih banyak ruang untuk menyimpan tabel hash. Ini adalah contoh space-for-time trade-off.

Apa tujuan utama dari Horspool’s Algorithm dalam pencarian string?

• Mencari kecocokan string dengan memindai seluruh teks
• Menggunakan tabel geser untuk mengurangi jumlah perbandingan karakter
• Menghitung frekuensi kemunculan substring dalam teks
• Meningkatkan efisiensi pengurutan string

Answer explanation

Penjelasan: Horspool’s Algorithm adalah algoritma pencarian string yang menggunakan strategi shift-table untuk mengurangi jumlah perbandingan karakter pada saat mencocokkan pola dengan teks, yang lebih efisien daripada pencocokan langsung.

Apa yang dimaksud dengan collision dalam konteks hashing?

• Dua elemen yang memiliki nilai hash yang berbeda
• Dua elemen yang memiliki nilai hash yang sama
• Ketika hash table kehabisan ruang
• Proses pencarian nilai hash yang tidak ditemukan

Answer explanation

Penjelasan: Collision terjadi ketika dua elemen yang berbeda menghasilkan nilai hash yang sama, yang kemudian memerlukan teknik seperti separate chaining atau open addressing untuk menyelesaikannya.

Bagaimana Horspool’s Algorithm menangani perbandingan karakter yang tidak cocok?

• Meningkatkan posisi penggeseran pola berdasarkan perbandingan terakhir
• Mengurangi panjang pola dengan mengabaikan karakter yang sudah dicocokkan
• Melanjutkan pencocokan dari karakter pertama
• Menggeser pola ke posisi berikutnya dengan lebih sedikit perbandingan

Answer explanation

Penjelasan: Horspool’s Algorithm menggunakan tabel geser untuk mengurangi perbandingan dengan memindahkan pola lebih jauh ketika terjadi ketidaksesuaian karakter, sehingga pencocokan lebih efisien.

Apa yang dimaksud dengan memoization dalam konteks Dynamic Programming?

• Teknik untuk menyelesaikan masalah dengan membagi sub-masalah secara seimbang
• Teknik untuk menyimpan hasil perhitungan sub-masalah agar tidak dihitung ulang
• Teknik untuk mencari solusi global yang optimal
• Teknik untuk menyelesaikan masalah secara iteratif

Answer explanation

Penjelasan: Memoization adalah teknik dalam Dynamic Programming yang melibatkan penyimpanan hasil perhitungan sub-masalah dalam suatu struktur data (seperti array atau tabel), sehingga jika sub-masalah tersebut diperlukan lagi, hasilnya dapat langsung digunakan tanpa dihitung ulang.

Manakah dari berikut ini yang merupakan contoh masalah yang dapat diselesaikan dengan Dynamic Programming?

• Masalah sorting
• Masalah pencarian jalur terpendek dalam graf berbobot
• Masalah Fibonacci
• Masalah pencarian elemen terbesar dalam array

Answer explanation

Penjelasan: Masalah Fibonacci adalah contoh klasik dari Dynamic Programming, di mana nilai Fibonacci dihitung dengan cara menyimpan hasil perhitungan sebelumnya untuk menghindari perhitungan ulang yang tidak perlu.