Data Structure Quiz

Apa perbedaan utama antara Insertion Sort dan Selection Sort?

• Insertion Sort memilih elemen terkecil

• Selection Sort menyisipkan elemen ke posisi yang benar

• Insertion Sort bekerja dengan menyisipkan, sementara Selection Sort memilih elemen minimum

• Selection Sort memiliki kompleksitas yang lebih rendah

Answer explanation

Insertion Sort menyisipkan elemen ke posisi yang benar dalam urutan yang sudah terurut, sedangkan Selection Sort memilih elemen terkecil dari yang belum terurut dan menempatkannya di posisi yang benar. Ini adalah perbedaan utama antara keduanya.

Manakah dari pernyataan berikut yang benar mengenai Binary Search Tree (BST)?

• Semua anak kiri lebih besar dari node induk

• Semua anak kanan lebih kecil dari node induk

• Semua anak kiri lebih kecil dan anak kanan lebih besar dari node induk

• Semua node memiliki dua anak

Answer explanation

Pernyataan yang benar mengenai Binary Search Tree (BST) adalah bahwa semua anak kiri lebih kecil dan anak kanan lebih besar dari node induk. Ini adalah sifat dasar BST yang memastikan struktur pohon tetap teratur.

Divide and Conquer digunakan dalam algoritma berikut, kecuali:

• Merge Sort

• Quicksort

• Insertion Sort

• Binary Search

Answer explanation

Insertion Sort tidak menggunakan metode Divide and Conquer, melainkan mengurutkan elemen satu per satu dengan membandingkan dan menyisipkan. Sementara Merge Sort, Quicksort, dan Binary Search menggunakan pendekatan ini.

Fungsi FindMin dalam BST bekerja dengan:

• Mencari node paling kanan

• Mencari node tengah

• Menelusuri sub-pohon kiri hingga mencapai node paling kiri

• Menelusuri sub-pohon kanan hingga mencapai node paling kanan

Answer explanation

Fungsi FindMin dalam BST mencari nilai terkecil dengan menelusuri sub-pohon kiri hingga mencapai node paling kiri, karena dalam BST, node terkecil selalu berada di sisi kiri.

Representasi grafik dengan matriks ketetanggaan cocok untuk grafik:

• Terarah

• Tidak Terarah

• Sparse

• Padat

Answer explanation

Matriks ketetanggaan paling cocok untuk grafik padat karena dapat merepresentasikan semua kemungkinan hubungan antar simpul dengan efisien, terutama ketika jumlah sisi mendekati jumlah maksimum yang mungkin.

Dalam algoritma DFS, sebuah node akan diwarnai hitam ketika:

• Pertama kali ditemukan

• Semua tetangganya telah ditemukan

• Node tersebut tidak memiliki penerus

• Node tersebut menjadi akar

Answer explanation

Dalam algoritma DFS, sebuah node diwarnai hitam setelah semua tetangganya telah ditemukan, menandakan bahwa semua jalur dari node tersebut telah dieksplorasi sepenuhnya.

Apa tujuan dari strategi partisi dalam Quicksort?

• Untuk mengurutkan semua elemen sekaligus

• Untuk memindahkan semua elemen ke kiri

• Untuk mengatur elemen yang lebih kecil dari pivot ke kiri, dan yang lebih besar ke kanan

• Untuk menemukan elemen terbesar

Answer explanation

Tujuan dari strategi partisi dalam Quicksort adalah untuk mengatur elemen-elemen sehingga elemen yang lebih kecil dari pivot berada di kiri dan yang lebih besar berada di kanan, memudahkan proses pengurutan.

Heap yang diatur sedemikian rupa sehingga elemen terkecil selalu berada di akar disebut:

• Max Heap

• Min Heap

• Pohon AVL

• Pohon Biner

Answer explanation

Heap yang diatur sehingga elemen terkecil berada di akar disebut Min Heap. Dalam struktur ini, setiap node memiliki nilai yang lebih besar atau sama dengan nilai anak-anaknya, menjadikannya mudah untuk mengakses elemen terkecil.

Salah satu keuntungan menggunakan daftar ketetanggaan dibandingkan dengan matriks ketetanggaan adalah:

• Lebih cepat untuk menemukan node tetangga

• Lebih efisien dalam penggunaan memori untuk grafik jarang

• Lebih cocok untuk grafik padat

• Tidak memerlukan pointer

Answer explanation

Daftar ketetanggaan lebih efisien dalam penggunaan memori untuk grafik jarang karena hanya menyimpan informasi tentang node yang terhubung, sedangkan matriks ketetanggaan menyimpan data untuk semua kemungkinan hubungan, yang boros memori.

Traversal BFS cocok digunakan ketika kita ingin menemukan:

• Jalur terdalam

• Jalur terpanjang

• Jalur terpendek dalam hal node

• Siklus dalam graf

Answer explanation

Traversal BFS (Breadth-First Search) digunakan untuk menemukan jalur terpendek dalam hal node karena ia mengeksplorasi semua node pada level yang sama sebelum melanjutkan ke level berikutnya, sehingga memastikan jalur terpendek ditemukan.