Quiz 2 - ASD - B

Dalam konteks pengelolaan struktur data pohon biner, manakah dari pernyataan berikut yang paling tepat membedakan antara operasi dasar dan operasi bantu (auxiliary)?

• Operasi dasar selalu melibatkan manipulasi langsung terhadap node, sedangkan operasi bantu hanya mencakup traversal sederhana tanpa analisis struktur

• Operasi dasar berfokus pada pengubahan struktur pohon, sedangkan operasi bantu menganalisis properti pohon tanpa mengubah strukturnya

• Operasi dasar hanya melibatkan pencarian, sedangkan operasi bantu bertanggung jawab atas penyisipan dan penghapusan.

• Tidak ada perbedaan yang signifikan antara operasi dasar dan bantu karena keduanya memerlukan traversal.

Diberikan pohon biner seperti pada gambar, dan kita ingin menyisipkan elemen 12 menggunakan metode level-order traversal. Di manakah node 12 akan disisipkan?

• Sebagai anak kiri dari node 1

• Sebagai anak kanan dari node 1

• Sebagai anak kiri dari node 34

• Sebagai anak kanan dari node 10

Jika node 12 dihapus dari binary search tree (BST) pada gambar, node manakah yang paling tepat menggantikan posisinya agar struktur tetap memenuhi aturan BST?

• Node 15

• Node 19

• Node 7

• Node 30

Dalam konteks struktur data, manakah pernyataan berikut yang paling akurat membedakan struktur data non-linear dari linear, serta menjelaskan konsekuensinya terhadap efisiensi algoritma traversal dan pencarian?

• Struktur data non-linear memiliki urutan elemen tetap, sehingga traversal dan pencarian dapat dilakukan dalam kompleksitas waktu konstan O(1).

• Struktur data linear memungkinkan banyak node memiliki lebih dari satu pendahulu, sedangkan struktur non-linear membatasi hanya satu pendahulu dan satu penerus

• Struktur data non-linear seperti graph atau tree tidak mengikuti urutan berurutan, sehingga memerlukan pendekatan traversal khusus (DFS/BFS) dengan kompleksitas tergantung pada struktur dan tingkat kedalaman

• Baik struktur linear maupun non-linear memiliki pola traversal yang identik karena keduanya menyimpan data secara sekuensial dalam memori

Suatu sistem manajemen proyek dirancang untuk merepresentasikan hubungan antar tugas. Tugas-tugas tersebut saling bergantung satu sama lain, dan beberapa tugas memiliki lebih dari satu prasyarat (dependency). Dalam sistem tersebut, juga ditemukan bahwa dalam beberapa kasus, tugas A dapat mengarah kembali ke tugas awal sebagai bentuk pengulangan proses.

Berdasarkan ciri-ciri tersebut, struktur data manakah yang paling tepat digunakan untuk merepresentasikan sistem tersebut, dan mengapa?

• Tree, karena setiap tugas hanya memiliki satu parent dan tidak mungkin membentuk loop.

• Graph, karena hubungan antar tugas bersifat hirarkis dan membentuk struktur akar (rooted)

• Tree, karena semua tugas dapat diurutkan dari node root ke daun tanpa pengulangan

• Graph, karena setiap node dapat memiliki lebih dari satu parent dan memungkinkan terbentuknya cycle

Diberikan tiga jenis graph seperti pada gambar: simple graph, nonsimple graph with multiple edges, dan nonsimple graph with loops.

Manakah dari pernyataan berikut ini yang paling tepat untuk membedakan ketiga jenis graph tersebut secara formal dalam teori graf?

• Simple graph memiliki loop dan edge ganda yang memperkuat konektivitas antar node.

• Nonsimple graph tidak memiliki batasan terhadap jumlah node, tetapi setiap edge harus bersifat arah.

• Simple graph hanya memperbolehkan satu edge antara dua simpul berbeda dan tidak mengandung loop.

• Graph dengan loop selalu dianggap acyclic karena loop hanya mengarah pada satu simpul itu sendiri.

Sebuah simple undirected graph G= (V, E) memiliki n simpul dan jumlah edge maksimum. Misalkan jumlah total derajat dari semua simpul di graf tersebut adalah 300. Berapakah banyaknya simpul (vertices) nnn dalam graf tersebut?

• 20

• 25

• 30

• 15

Perhatikan graf lengkap (complete graph) di atas yang memiliki 5 simpul (A, B, C, D, E). Berapakah jumlah sisi (edge) pada graf lengkap tersebut?

• 20

• 12

• 15

• 10

Berdasarkan weighted directed graph pada gambar, berapakah total bobot dari jalur: V0 → V5 → V2 → V3 → V4?

• 12

• 14

• 19

• 20

Jika graf pada gambar merepresentasikan urutan ketergantungan antar tugas, di mana sebuah simpul hanya dapat dieksekusi setelah semua simpul yang menuju ke arahnya selesai, manakah simpul yang bisa dieksekusi pertama kali?

• d

• a

• e

• c