Lembar kerja Struktur data dengan jawaban

Dalam graf tak berarah, apa yang dimaksud dengan derajat (degree) simpul?

1. APosisinya dalam adjacency list
2. BJumlah sisi yang terhubung dengannya
3. CPanjang lintasan terpanjang darinya
4. DJumlah simpul dalam graf

Tinggi (height) pohon umumnya didefinisikan sebagai:

1. AJumlah daun dalam pohon
2. BJumlah anak root
3. CJumlah total node dalam pohon, dengan menghitung root dan setiap daun
4. DJumlah sisi pada lintasan terpanjang dari root ke daun

Struktur manakah yang biasanya digunakan untuk mengimplementasikan priority queue?

1. AString
2. BHeap
3. CSingly linked list tanpa urutan
4. DStack

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

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

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

1. ALinked list selalu menyimpan elemen di disk
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. DArray memakai lebih sedikit instruksi untuk membandingkan nilai

Apa yang benar tentang adjacency matrix graf tak berarah?

1. ASetiap baris memiliki tepat satu angka 1
2. BDiagonal utamanya selalu berisi angka satu
3. CMatriksnya selalu segitiga atas
4. DMatriksnya simetris terhadap diagonal utama

Fenwick tree (binary indexed tree) atas array berisi n bilangan mendukung operasi apa dalam O(log n)?

1. AMencari median dalam O(1)
2. BKueri prefix sum dan pembaruan satu elemen
3. CMengurutkan array dan binary search
4. DMenyisipkan elemen di posisi mana pun

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

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