Font size
Worksheets04 - Disjoint Sets
Total questions: 15
Worksheet time: 10mins
Disjoint Sets digunakan untuk menyimpan data dengan sifat ...
Himpunan saling lepas
Data yang memiliki keterurutan
Himpunan vertex dan himpunan edge
Data yang memiliki hubungan parent-child
Manakah yang merupakan operasi Disjoint Sets ?
Union
Add-edge
Find-Max
Successor
Delete-set
Jika Disjoint-Sets direpresentasikan dengan linked list, apa yang menjadi set's representative ?
Node dengan nilai terbesar
Head
Tail
Node yang pertama dimasukkan
Jika Disjoint-Sets direpresentasikan dengan linked list, berapakah kompleksitas orpeasi FIND-SET ?
O(1)
O(n)
O(lg n)
O(n2)
UNION pada Disjoint-Sets yang direpresentasikan dengan linked list selalu menempatkan list yang lebih panjang di depan. Cara ini dikenal dengan istilah ...
Weighted Union
Path Compression
Union By Rank
Kruskal MST
Jika Disjoint-Sets direpresentasikan dengan rooted tree, manakah element yang menjadi set's representative?
Node root
Salah satu leaf
Leaf paling dalam
Node dengan data terbesar
Yang dimaksud dengan "rank" pada node Disjoint-Sets adalah ... pada pohon yang berakar di node tersebut
Upper bound dari tinggi pohon
Tinggi pohon
Banyak node
Peringkat node
Manakah pernyataan yang benar?
Rank dapat lebih besar dari tinggi sebenarnya
Suatu set mungkin hanya terdiri dari 1 node
Mungkin ada satu node yang merupakan anggota dari dua himpunan
Mungkin ada satu node yang bukan anggota himpunan manapun
Masalah menghitung banyak komponen pada graph dapat diselesaikan dengan bantuan Disjoint-Set. Asumsikan kompleksitas operasi-operasi Disjoint-Sets adalah O(1), berapakah kompleksitas algoritma penghitung banyak komponen?
O(V+E)
O(E)
O(V²)
O(V lg V)
Perhatikan pohon Disjoint-Sets berikut ini. Jika dilakukan operasi UNION(2,3), seperti apakah pohon hasilnya? Asumsikan Disjoint-Sets tidak menggunakan heuristik Path Compression, tapi menggunakan Union By Rank
Perhatikan pohon Disjoint-Sets berikut ini. Jika heuristik path compression digunakan, dan dilakukan operasi FIND-SET(i), seperti apakah pohon hasilnya?
Kasus buruk apa yang mungkin terjadi jika Disjoint-Sets direpresentasikan dengan rooted tree tanpa menggunakan heuristik path compression maupun union by rank?
Setiap node pada tree hanya memiliki 1 anak, sehingga tree memanjang ke satu arah seperti linked-list
Ukuran tree menjadi sangat lebar
Perlu melakukan FIND-SET lebih dari 2 kali, sebelum dapat melakukan operasi UNION
Mungkin ada operasi UNION yang gagal, sehingga tree teeputus
Perhatikan graph ini. Jika algoritma Kruskal's MST dijalankan, manakah urutan UNION yang benar ?
UNION(b,d) - UNION(b,a) - UNION(d,e) - UNION(a,d)
UNION(b,d) - UNION(b,a) - UNION(d,e) - UNION(b,c)
UNION(b,d) - UNION(b,a) - UNION(d,e) - UNION(a,d) - UNION(b,c) - UNION(c,e)
UNION(a,b) - UNION(b,d) - UNION(d,e) - UNION(b,c)
Dari graph-graph berikut ini, manakah yang memiliki MST yang unik ? (hanya satu macam MST)
Disjoint-Sets disimpan dengan menggunakan 2 array, yaitu...
Array of parents
Array of children
Array of edges
Array of ranks
