Lembar kerja Struktur data dengan jawaban

Apa perbedaan utama antara array statis dan dynamic array?

1. AArray statis memiliki akses indeks yang lebih lambat
2. BArray statis hanya dapat menyimpan bilangan
3. CDynamic array dapat membesar dengan pindah ke blok memori yang lebih besar
4. DDynamic array menyimpan elemennya dalam node yang saling terhubung sehingga dapat membesar satu per satu

Kedalaman (depth) suatu node dalam pohon adalah:

1. AJumlah sisi dari root ke node itu
2. BJumlah node dalam subpohonnya
3. CJumlah anak node itu
4. DJumlah sisi dari node itu ke daun terdalam

Dalam hash table, apa yang dimaksud dengan collision (tabrakan)?

1. ADua kunci berbeda dipetakan ke indeks yang sama
2. BDua kunci yang sama disimpan dua kali
3. CTabel kehabisan memori
4. DSuatu kunci sama sekali tidak dapat di-hash

Berapa lama pencarian kata dengan panjang L dalam trie dengan alfabet tetap?

1. AO(log n), dengan n jumlah kata
2. BO(L), tidak bergantung pada berapa banyak kata yang disimpan
3. CO(L × n)
4. DO(n), dengan n jumlah kata

Syarat keseimbangan apa yang dijaga AVL tree di setiap node?

1. ASemua daun berada pada kedalaman yang persis sama
2. BTinggi subpohon kiri dan kanan berbeda paling banyak 1
3. CKedua subpohon dari setiap node berisi jumlah node yang persis sama
4. DSetiap node diberi warna merah atau hitam

Sebuah binary tree memiliki root 1 dengan anak kiri 2 dan anak kanan 3; node 2 memiliki anak 4 (kiri) dan 5 (kanan). Bagaimana hasil traversal postorder-nya?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Struktur union-find (disjoint set) dengan union by rank dan path compression memiliki biaya teramortisasi per operasi sebesar:

1. AO(n)
2. BO(α(n)), fungsi invers Ackermann, yang secara praktis konstan
3. CO(n²)
4. DTepat O(log n)

Kompleksitas waktu decrease-key pada binary heap (jika posisi elemen diketahui) adalah:

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