Lembar kerja Struktur data dengan jawaban

Struktur manakah yang biasanya digunakan untuk mengimplementasikan priority queue?

1. AHeap
2. BStack
3. CSingly linked list tanpa urutan
4. DString

Operasi manakah yang lambat pada array tetapi cepat di bagian head linked list?

1. AMengakses elemen ke-5
2. BMencari panjang array berukuran tetap
3. CMembaca elemen terakhir berdasarkan indeks
4. DMenyisipkan di awal

Hash table menyimpan data dalam bentuk:

1. APohon dengan kunci terurut
2. BPasangan kunci–nilai yang dilokasikan dengan fungsi hash
3. CString dengan panjang tetap
4. DHanya daftar terurut

Dalam binary heap yang disimpan dalam array mulai dari indeks 0, di mana induk dari node pada indeks i?

1. APada indeks 2i + 1
2. BPada indeks i − 1
3. CPada indeks ⌊i / 2⌋ + 1
4. DPada indeks ⌊(i − 1) / 2⌋

Berapa biaya menyisipkan elemen di tengah array berisi n elemen?

1. AO(1), karena indeksnya diketahui
2. BO(n), karena elemen-elemen sesudahnya harus digeser
3. CO(log n), karena binary search
4. DO(n²), karena setiap elemen bergeser n kali

Mengapa menelusuri array dalam praktik sering jauh lebih cepat daripada menelusuri linked list dengan panjang sama?

1. AArray memakai lebih sedikit instruksi untuk membandingkan nilai
2. BPenelusuran array berjalan dalam O(1) secara total, sedangkan penelusuran linked list O(n)
3. CElemen array berurutan di memori, sehingga memanfaatkan cache CPU dengan baik
4. DLinked list selalu menyimpan elemen di disk

Bagaimana mendeteksi apakah singly linked list mengandung siklus dengan memori tambahan O(1)?

1. ASimpan setiap node yang dikunjungi dalam hash set
2. BUrutkan list dan cari duplikat
3. CHitung node sampai hitungannya melebihi field panjang list
4. DGerakkan satu pointer satu langkah dan pointer lain dua langkah, lalu periksa apakah keduanya bertemu

Anda harus menyimpan k nilai terkecil dari aliran n bilangan dengan memori O(k). Pendekatan mana yang bekerja dalam waktu O(n log k)?

1. AArray terurut berisi semua n nilai
2. BQueue FIFO berisi k nilai terakhir
3. CMax-heap berukuran k, mengganti root-nya ketika datang nilai yang lebih kecil
4. DMin-heap yang menampung semua n nilai, lalu k nilai terkecil dikeluarkan di akhir