UAS Struktur Data 2025

UAS Struktur Data, gasal 2025/2026. Senin, 15 Desember 2025. 10.00–11.40 WIB (100 menit). Buku hardcopy terbuka, no gadgets.

Tuliskan NIM dan nama pada setiap lembar jawab. Dilarang plagiasi, bekerja sama, saling pinjam, atau berkomunikasi. Jawab menggunakan pensil 2B dan notasi algoritmik/pseudocode, bila perlu disertai asumsi/gambar.

Studi kasus SIDONA

Sistem Donasi Bencana (SIDONA) mencatat Dermawan berdasarkan NIK, Nama Lengkap, Telepon, Tanggal donasi, besaran Uang (Rp), dan daftar Barang.

No	NIK	Nama Lengkap	Telepon	Tanggal	Uang	Barang
1	337411005	Arif Bijaksana	081234567890	10-12-2025	1.000.000	—
2	332112003	Budiman Luhur	081987654321	12-12-2025	0	120 kg beras
3	337411005	Arif Bijaksana	081234567890	15-12-2025	500.000	—
…	…	…	…	…	…	…

Soal 1 — 30%

Buat definisi semua struktur data abstrak (ADT) yang relevan dan realisasi operator pengisian nilai setiap komponen untuk sebuah objek Dermawan pada SIDONA dengan representasi berkait.

Type Dermawan = …
… {tambahkan type-type lain yang relevan}
Type ListDermawan = …
Function createDermawan( … ) → Dermawan
{Mengkonstruksi sebuah objek Dermawan dari nilai-nilai masukan}

Soal 2 — 35%

Tuliskan definisi, kamus lokal, dan algoritma operator untuk merekapitulasi data Dermawan. List Rekapitulasi Dermawan hanya mencatat rangkuman, sehingga setiap Dermawan muncul sekali dengan total dana dan total barang. Jika perlu operator tambahan, tulis definisi, spesifikasi, kamus lokal, dan algoritmanya.

procedure RekapDermawan(input L:ListDermawan, output R:ListDermawan)
{I.S.: L terdefinisi, mungkin kosong}
{F.S.: R berisi rekapitulasi L}
{Proses: menambahkan elemen L ke R dengan menjumlahkan
 donasi dari Dermawan yang sama}

Soal 3 — 35%

Pengelolaan Dermawan menggunakan pohon terurut. Baca List Rekapitulasi Dermawan, kemudian tambahkan simpul baru. Simpul dengan donasi Uang lebih besar ditempatkan lebih kiri. Simpul dengan donasi lebih kecil ditempatkan lebih kanan.

Buat realisasi prosedur-prosedur yang menerapkan mekanisme tersebut.

type Simpul = < info: Dermawan, left: Tree, right: Tree >
type Tree = pointer to Simpul
function Ftree(A:Dermawan, L:Tree, R:Tree) → Tree
{menghasilkan pohon baru dengan info A, anak kiri L, anak kanan R}
procedure AddDermawanUrut(input/output T:Tree, input D:Dermawan)
{I.S.: T dan D terdefinisi}
{F.S.: T bertambah 1 daun}
{Proses: menambahkan D ke posisi kiri/kanan}

Studi kasus dan soal 1 di halaman PDF 1; soal 2–3 di halaman PDF 2.

1. Representasi dan konstruksi

NIK menjadi identitas; setiap simpul dermawan pada daftar asal mewakili satu transaksi dan dapat memiliki daftar barang kosong. Jumlah barang disimpan menurut nama dan satuan, sehingga 120 kg beras tidak dicampur dengan, misalnya, 10 dus selimut.

type Barang = record { nama: string, jumlah: real, satuan: string }
type NodeBarang = record { info: Barang, next: pointer NodeBarang }
type ListBarang = pointer NodeBarang
type Dermawan = record {
  nik, nama, telepon, tanggal: string,
  uang: integer, barang: ListBarang
}
type NodeDermawan = record { info: Dermawan, next: pointer NodeDermawan }
type ListDermawan = pointer NodeDermawan

function createDermawan(nik, nama, telepon, tanggal: string,
                         uang: integer, barang: ListBarang) → Dermawan
  { kamus: D: Dermawan }
  D.nik ← nik; D.nama ← nama; D.telepon ← telepon
  D.tanggal ← tanggal; D.uang ← uang; D.barang ← salinBarang(barang)
  return D

function salinBarang(B: ListBarang) → ListBarang
  { kamus: hasil, akhir, p, q: pointer NodeBarang }
  hasil ← null; akhir ← null; p ← B
  while p ≠ null do
    q ← new NodeBarang(p.info, null)
    if hasil = null then hasil ← q else akhir.next ← q
    akhir ← q; p ← p.next
  return hasil

Salinan membuat daftar barang hasil tidak berbagi simpul yang dapat dimutasi dengan masukan. new diasumsikan berhasil; uang disimpan sebagai rupiah utuh.

2. Rekapitulasi

Gunakan satu simpul hasil per NIK, dengan total uang dan daftar barang terakumulasi menurut pasangan nama–satuan. Identitas nama dan telepon diambil dari transaksi pertama; tanggal tidak disimpan karena satu rekap dapat mencakup beberapa tanggal.

type Rekap = record { nik, nama, telepon: string, totalUang: integer, totalBarang: ListBarang }
type NodeRekap = record { info: Rekap, next: pointer NodeRekap }
type ListRekap = pointer NodeRekap

procedure TambahBarang(inout B: ListBarang, input item: Barang)
  { kamus: p: pointer NodeBarang }
  p ← B
  while p ≠ null and (p.info.nama ≠ item.nama or p.info.satuan ≠ item.satuan) do p ← p.next
  if p = null then B ← new NodeBarang(item, B)
  else p.info.jumlah ← p.info.jumlah + item.jumlah

procedure Rekapitulasi(L: ListDermawan, output R: ListRekap)
  { kamus: p: pointer NodeDermawan; q: pointer NodeRekap; b: pointer NodeBarang }
  R ← null; p ← L
  while p ≠ null do
    q ← R
    while q ≠ null and q.info.nik ≠ p.info.nik do q ← q.next
    if q = null then
      q ← new NodeRekap(Rekap(p.info.nik, p.info.nama, p.info.telepon, 0, null), R)
      R ← q
    q.info.totalUang ← q.info.totalUang + p.info.uang
    b ← p.info.barang
    while b ≠ null do
      TambahBarang(q.info.totalBarang, b.info)
      b ← b.next
    p ← p.next

Sebagai contoh, dua transaksi Arif NIK 337411005 sebesar Rp1.000.000 dan Rp500.000 digabung menjadi Rp1.500.000; Budiman NIK 332112003 tetap Rp0 dan 120 kg beras. Pemindaian linear menghasilkan waktu terburuk kuadratik terhadap jumlah transaksi dan item; indeks NIK dapat mempercepatnya.

1 / 3

Transaksi pertama

Arif belum ada; buat rekap Rp1.000.000.

NIK	Nama	Total uang	Barang
337411005	Arif	1.000.000	—

Langkah

3. Pohon berdasarkan uang

Pohon ini memakai isi Rekap untuk informasi dermawan. Aturan sama besar tidak ditentukan soal; di sini nilai sama masuk ke kanan agar setiap rekap tetap menjadi simpul. Sisipkan tiap hasil rekap sekali.

type Simpul = record { info: Rekap, left, right: Tree }
type Tree = pointer Simpul

function Ftree(A: Rekap, L: Tree, R: Tree) → Tree
  return new Simpul(A, L, R)

procedure AdDermawanUrut(inout T: Tree, input D: Rekap)
  if T = null then T ← Ftree(D, null, null)
  else if D.totalUang > T.info.totalUang then AdDermawanUrut(T.left, D)
  else AdDermawanUrut(T.right, D)

procedure Bangun(R: ListRekap, output T: Tree)
  { kamus: p: pointer NodeRekap }
  T ← null; p ← R
  while p ≠ null do
    AdDermawanUrut(T, p.info)
    p ← p.next

Traversal kiri–akar–kanan menghasilkan urutan uang menurun. Contoh jika Arif dimasukkan sebelum Budiman: Arif Rp1.500.000 menjadi akar, Budiman Rp0 menjadi anak kanan. Tinggi pohon dapat mencapai $n$ , sehingga penyisipan terburuk $O(n)$ per simpul.

Pembahasan ditulis independen oleh belajar.myudak, bukan kunci jawaban resmi. Soal asli tetap milik pengampu mata kuliah dan ditampilkan langsung dari arsip Google Drive.