Lembar kerja Struktur data dengan jawaban

Apa yang dilakukan fungsi hash dalam hash table?

1. AMengurutkan kunci dalam tabel
2. BMemetakan kunci ke indeks dalam tabel
3. CMengenkripsi nilai dalam tabel
4. DMenghitung berapa banyak kunci yang disimpan

Apa yang dimaksud dengan deque (double-ended queue)?

1. AQueue yang diurutkan berdasarkan prioritas
2. BQueue yang hanya mengizinkan penghapusan di belakang
3. CDua queue terpisah yang berbagi satu array
4. DStruktur yang memungkinkan penyisipan dan penghapusan di kedua ujung

Sebuah graf terdiri atas:

1. AHanya kunci dan hash
2. BHanya akar dan daun
3. CSimpul (vertex/node) yang dihubungkan oleh sisi (edge)
4. DBaris dan kolom

Berapa banyak memori yang dipakai adjacency list untuk graf dengan V simpul dan E sisi?

1. AO(V × E)
2. BO(V²)
3. CO(E²)
4. DO(V + E)

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. BElemen array berurutan di memori, sehingga memanfaatkan cache CPU dengan baik
3. CLinked list selalu menyimpan elemen di disk
4. DPenelusuran array berjalan dalam O(1) secara total, sedangkan penelusuran linked list O(n)

Sebuah queue diimplementasikan dengan dua stack: push ke stack "in", dan pop dari stack "out", yang diisi ulang dari "in" saat kosong. Berapa biaya amortisasi per operasi?

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

Dalam algoritma minimum spanning tree Kruskal, untuk apa struktur union-find dipakai?

1. AMenyimpan jarak terkini setiap simpul dari sumber selama pencarian
2. BMemeriksa apakah kedua ujung suatu sisi sudah terhubung
3. CMemilih simpul awal
4. DMengurutkan sisi berdasarkan bobot

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

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