Untuk pengajar: gratis untuk dicetak, disalin, dan dipakai di kelas. Setiap lembar kerja baru punya nilai baru dan kunci jawabannya sendiri. Tautan ke ExamProblems di halaman mata kuliah Anda sangat kami hargai.
Nama: ____________________ Tanggal: ____________
1.Mudah
Apa yang dimaksud dengan graf berarah (directed graph)?
AGraf yang tidak memiliki siklus
BGraf yang semua sisinya berbobot
CGraf yang setiap pasangan simpul berbedanya dihubungkan oleh sebuah sisi
DGraf yang sisinya memiliki arah dari satu simpul ke simpul lain
2.Mudah
Apa yang dimaksud dengan deque (double-ended queue)?
ADua queue terpisah yang berbagi satu array
BQueue yang diurutkan berdasarkan prioritas
CStruktur yang memungkinkan penyisipan dan penghapusan di kedua ujung
DQueue yang hanya mengizinkan penghapusan di belakang
3.Mudah
Dalam graf tak berarah, apa yang dimaksud dengan derajat (degree) simpul?
APosisinya dalam adjacency list
BJumlah simpul dalam graf
CJumlah sisi yang terhubung dengannya
DPanjang lintasan terpanjang darinya
4.Sedang
Syarat keseimbangan apa yang dijaga AVL tree di setiap node?
ASemua daun berada pada kedalaman yang persis sama
BSetiap node diberi warna merah atau hitam
CTinggi subpohon kiri dan kanan berbeda paling banyak 1
DKedua subpohon dari setiap node berisi jumlah node yang persis sama
5.Sedang
Berapa banyak memori yang dipakai adjacency list untuk graf dengan V simpul dan E sisi?
AO(V²)
BO(E²)
CO(V × E)
DO(V + E)
6.Sedang
Berapa biaya menyisipkan elemen di tengah array berisi n elemen?
AO(n), karena elemen-elemen sesudahnya harus digeser
BO(1), karena indeksnya diketahui
CO(log n), karena binary search
DO(n²), karena setiap elemen bergeser n kali
7.Sulit
Bagaimana radix tree (compressed trie) memperbaiki trie biasa?
AMenyimpan setiap kata dalam hash table di root alih-alih dalam node-node terpisah
BHanya menyimpan huruf pertama setiap kata
CMengurutkan anak-anak setiap node berdasarkan frekuensi
DMenggabungkan rantai node beranak tunggal menjadi satu sisi yang diberi label string
8.Sulit
Sifat mana yang menjaga setiap B-tree tetap seimbang sempurna?
ASetiap node menyimpan satu kunci
BSetiap node memiliki tepat dua anak
CKunci hanya disimpan di root
DSemua daun berada pada kedalaman yang sama
Kunci jawaban
1. D · Graf yang sisinya memiliki arah dari satu simpul ke simpul lain
2. C · Struktur yang memungkinkan penyisipan dan penghapusan di kedua ujung
3. C · Jumlah sisi yang terhubung dengannya
4. C · Tinggi subpohon kiri dan kanan berbeda paling banyak 1
5. D · O(V + E)
6. A · O(n), karena elemen-elemen sesudahnya harus digeser
7. D · Menggabungkan rantai node beranak tunggal menjadi satu sisi yang diberi label string
8. D · Semua daun berada pada kedalaman yang sama
Penyelesaian lengkap langkah demi langkah: latih topik ini di examproblems.com.