Font size
WorksheetsUjian Akhir Semester Teori Struktur Data
Total questions: 26
Worksheet time: 35mins
Apa tujuan utama dari algoritma pengurutan (sorting)?
Menambahkan elemen ke dalam array
Menyusun elemen agar berada dalam urutan tertentu
Menghapus elemen duplikat
Menemukan median
Struktur data apa yang paling tepat digunakan untuk merepresentasikan pohon biner secara efisien?
Array 1 dimensi
Linked List
Graph
Pointer ke kiri dan kanan
Manakah dari berikut ini yang merupakan karakteristik utama dari BFS?
Menjelajah graf sampai simpul terdalam
Menggunakan tumpukan (stack)
Menggunakan antrian (queue)
Tidak memperhatikan urutan simpul
Heap termasuk jenis struktur data apa?
Linear
Non-linear
Statik
Hash
Quicksort akan berhenti rekursi jika...
Pivot adalah elemen terbesar
Jumlah elemen dalam array ≤ 1
Semua elemen adalah bilangan prima
Array sudah dalam urutan menurun
Apa yang terjadi pada simpul dalam DFS saat semua successor-nya ditemukan?
Diwarnai putih
Diwarnai abu-abu
Diwarnai hitam
Dihapus dari graf
Apa yang dimaksud dengan "gap" dalam algoritma Shell Sort?
Ukuran array
Jarak antar segmen yang dibandingkan
Jumlah elemen yang belum terurut
Indeks pivot
Dalam pohon biner pencarian (BST), di mana posisi elemen yang lebih besar dari simpul saat ini?
Sub-tree kiri
Sub-tree kanan
Daun
Akar
Manakah dari operasi berikut yang dilakukan paling awal dalam metode Divide and Conquer?
Merge
Conquer
Divide
Combine
Manakah dari berikut ini yang TIDAK benar tentang graf berarah (directed graph)?
Terdapat pasangan (u, v)
Selalu memiliki siklus
Bisa tidak terhubung
Edge memiliki arah
Jika heap direpresentasikan dalam array, maka anak dari indeks ke-i berada di posisi:
i + 1 dan i + 2
2i dan 2i + 1
i - 1 dan i - 2
i/2 dan i/2 + 1
Dalam DFS, "d" dan "f" menunjukkan waktu:
Distance dan Finish
Discovery dan Finish
Degree dan Frequency
Depth dan Front
Kompleksitas waktu Merge Sort adalah:
O(n²)
O(n log n)
O(n)
O(log n)
Manakah yang termasuk struktur data non-linier?
Stack
Array
Queue
Tree
Fungsi FindMin dalam BST mengembalikan simpul dengan:
Jumlah anak terbanyak
Nilai minimum
Jumlah anak nol
Nilai maksimum
Manakah yang merupakan kelemahan representasi graf dengan matriks kedekatan?
Tidak efisien untuk graf padat
Fragmen memori jika graf jarang
Tidak bisa menambahkan atribut simpul
Tidak mendukung graf berarah
DFS berbeda dari BFS karena:
DFS menggunakan queue
DFS tidak menggunakan warna
DFS mengeksplorasi sedalam mungkin terlebih dahulu
DFS hanya untuk graf tidak berarah
Properti heap pada min-heap adalah:
Setiap simpul ≤ semua anaknya
Setiap simpul = semua anaknya
Setiap anak > root
Semua elemen sama
Cara memilih pivot secara median-of-three dilakukan dengan mengambil:
Elemen terbesar dari array
Nilai tengah dari 3 elemen: pertama, tengah, dan terakhir
Elemen acak dari array
Nilai maksimum dari array
Manakah dari berikut ini yang menyebabkan Quicksort memiliki kompleksitas terburuk O(n²)?
Pivot dipilih secara acak
Data sudah dalam urutan menaik atau menurun
Menggunakan median-of-three
Menggunakan Merge sebagai fallback
Jika sebuah Binary Search Tree (BST) memiliki tinggi h, maka dalam kasus terbaik operasi FIND memiliki kompleksitas:
O(n²)
O(log n)
O(n)
O(1)
Heap yang digunakan untuk implementasi priority queue harus memiliki properti:
Semua daun berada di level terakhir
Harus merupakan tree AVL
Setiap sub-pohon juga harus merupakan heap
Harus diurutkan secara global
Dalam representasi graf dengan adjacency list, keunggulan utama dibanding adjacency matrix adalah:
Lebih cepat untuk semua operasi
Tidak ada fragmentasi memori untuk graf jarang
Tidak membutuhkan linked list
Dapat menangani graf lengkap lebih efisien
Manakah dari berikut ini yang merupakan proses "percolate-up" dalam min-heap?
Memindahkan elemen terkecil ke daun
Menukar elemen baru ke atas hingga memenuhi heap order
Menukar elemen terkecil ke kanan
Menyisipkan elemen baru ke dalam akar
Pada penghapusan simpul dengan dua anak dalam BST, langkah yang paling tepat adalah:
Menghapus anak kanan langsung
Mengganti nilai dengan anak kiri
Mengganti simpul dengan nilai minimum di sub-tree kanan
Menukar simpul dengan root
Jelaskan perbedaan pendekatan algoritma Divide and Conquer dan algoritma Incremental dalam konteks pengurutan data. Sertakan contoh algoritma yang menggunakan kedua pendekatan tersebut dan analisis kompleksitas waktunya.
