UTS Struktur Data 2025

Catatan konsep (1)

Stack & Queue →

Buku terbuka UAS 2025

Soal text

Transkripsi dicocokkan dengan 4 halaman naskah asli.

Redaksi dirapikan untuk dibaca. Data, pilihan jawaban, dan subsoal mengikuti naskah; diagram dijelaskan dalam teks atau tabel.

Lompat ke soal

UTS Struktur Data, gasal 2025/2026. Senin, 13 Oktober 2025. 10.00–11.40 WIB (100 menit). Buku terbuka.

Tuliskan NIM, nama, dan nomor kursi pada lembar jawab. Identitas ditulis dengan pulpen dan jawaban dengan pensil 2B. Gunakan notasi algoritmik dan sertakan asumsi/gambar bila perlu. Kerjakan bagian sesuai nomor kursi. Dilarang bekerja sama, pinjam-meminjam alat tulis, atau berkomunikasi. Kumpulkan kembali soal bersama jawaban.

Soal 1 — 40%

Klinik mendata pasien memakai tabel berikut. Nilai kategori menurut prioritas dari tertinggi ke terendah adalah 1 (Lansia), 2 (Anak), 3 (Dewasa).

No	Nomor KTP	Nama	Kategori
1	1001	Ani	1
2	1002	Doni	2
…	…	…	…
100	…	…	…

a. Buat definisi tipe-tipe data abstrak untuk menyimpan data pasien. b. Tuliskan definisi, kamus lokal, dan algoritma operasi sesuai nomor kursi:

Ganjil: cari pasien berdasarkan Nomor KTP. Hasilkan nomor indeks dalam tabel dan data pasien. Jika tidak ditemukan, hasilkan indeks −1 dan null untuk data pasien.
Genap: hitung jumlah pasien pada setiap kategori.

Soal 2 — 30%

Pasien datang acak pada setiap sesi. Pelayanan berdasarkan kedatangan, tetapi lebih memperhitungkan prioritas kelompok. Prioritas lebih tinggi didahulukan dengan menggeser mundur prioritas lebih rendah. Prioritas sama mengikuti urutan kedatangan.

type QueuePasien = < wadah: array [1..5] of Pasien,
                     head: integer, tail: integer >

procedure Enqueue1(input/output Q:QueuePasien, input P:Pasien)
{I.S.: Q dan P terdefinisi}
{F.S.: Q tetap atau bertambah 1 elemen}
{Proses: menambahkan P ke posisi tepat selama Q belum penuh,
 dengan syarat Nomor KTP P belum terdaftar dalam Q;
 model Queue 1: head stabil}

procedure Enqueue2(input/output Q:QueuePasien, input P:Pasien)
{I.S.: Q dan P terdefinisi}
{F.S.: Q tetap atau bertambah 1 elemen}
{Proses: menambahkan P ke posisi tepat selama Q belum penuh;
 model Queue 2: head bergeser}

a. Realisasikan Enqueue1 untuk kursi ganjil atau Enqueue2 untuk kursi genap sesuai definisi/spesifikasi. b. Jelaskan singkat cara kerja algoritma dan tulis kondisi akhir wadah setelah satu kali operasi pada kondisi berikut.

Kursi ganjil

Q.wadah = [<"1001","Ani",1>, <"1002","Doni",2>,
           <"1003","Cici",2>, <"1004","Sari",3>, <"","",0>]
Enqueue1(Q, <"1005","Dini",2>)

Kursi genap

Q.wadah = [<"","",0>, <"1001","Ani",1>, <"1002","Doni",2>,
           <"1003","Cici",2>, <"1004","Sari",3>]
Enqueue2(Q, <"1005","Dini","Anak">)

Soal 3 — 30%

Definisi/spesifikasi ADT Stack:

module Stack
type Tstack = < wadah: array [1..5] of real, top: integer >

procedure createStack(output T:Tstack)
{I.S.: —}
{F.S.: T terdefinisi, semua elemen T.wadah = −999}
{Proses: menginisialisasi T}

function isEmpty(T:Tstack) → boolean
{true jika wadah kosong}

procedure push(input/output T:Tstack, input e:real)
{I.S.: T terdefinisi}
{F.S.: elemen di top tetap, atau berisi nilai e}
{Proses: mengisi elemen top baru bila belum penuh}

procedure pop(input/output T:Tstack, output e:real)
{I.S.: T terdefinisi}
{F.S.: e diisi elemen top stack lama, atau −999}
{Proses: mengambil elemen top bila belum kosong}

Aplikasi yang harus dilengkapi:

Program EvaluasiPostfix
{Mengevaluasi ekspresi postfix}
{Operand satu digit: 0,1,…,9}
{Ekspresi valid dan tidak ada pembagian dengan 0}

Kamus
  use Tstack
  function length(x:string) → integer
  {panjang x dalam karakter}
  function tipeKarakter(x:character) → integer
  {2 jika digit 0..9; 1 jika operator +,−,*,/; 0 jika lainnya}
  function charToInt(x:character) → integer
  {konversi karakter digit menjadi integer}
  exp: string
  hasil: real
  …

Algoritma
  input(exp)
  …
  output(hasil)

a. Lengkapi program EvaluasiPostfix yang mengaplikasikan ADT Stack untuk mengevaluasi string ekspresi postfix. Definisi/spesifikasi ADT Stack dan fungsi bawaan di kamus tidak perlu ditulis ulang. b. Berikan ilustrasi kondisi stack dari awal hingga akhir untuk:

Kursi ganjil: A B C + * D /
Kursi genap: A B C / + D *

Ganti A, B, C, D dengan empat digit terakhir NIM. Jika suatu digit 0, tambahkan dengan 2.

Soal 1 di halaman PDF 1–2; soal 2 di halaman PDF 2–3; soal 3 di halaman PDF 3–4.

Lihat naskah asli ↗

ADT pasien, antrean prioritas stabil, dan evaluasi postfix dengan stack.

ADTpencarianantrean prioritasstackpostfix

Pembahasan lengkap 3 nomor Visual interaktif · coba tombol langkah

Rujukan halaman naskah

Soal 1 (a, b): halaman PDF 1, 2 — Data pasien dan operasi tabel
Soal 2 (a, b): halaman PDF 2, 3 — Enqueue prioritas
Soal 3 (a, b): halaman PDF 3, 4 — Evaluasi postfix

1. Tabel pasien

Gunakan KTP sebagai string agar nol di depan terjaga, kategori integer 1–3, dan jumlah elemen n agar slot kosong tidak ikut diproses.

type Pasien = record { ktp: string, nama: string, kategori: integer }
type TabelPasien = record { wadah: array[1..100] of Pasien, n: integer }

procedure Cari(T: TabelPasien, key: string, output idx: integer, output data: Pasien or null)
  { kamus: i: integer }
  idx ← -1; data ← null; i ← 1
  while i ≤ T.n and idx = -1 do
    if T.wadah[i].ktp = key then idx ← i; data ← T.wadah[i]
    i ← i + 1
  end while

procedure HitungKategori(T: TabelPasien, output jumlah: array[1..3] of integer)
  { kamus: i, k: integer }
  jumlah ← [0, 0, 0]
  for i ← 1 to T.n do
    k ← T.wadah[i].kategori
    jumlah[k] ← jumlah[k] + 1
  end for

Kedua operasi $O(n)$ dan membutuhkan kategori masukan valid; pencarian mengembalikan kemunculan pertama.

2. Antrean prioritas

Kategori kecil didahulukan dan pasien berkategori sama tetap menurut kedatangan. Berikut indeks 1–5; head=tail=0 menyatakan kosong. Keduanya menjaga elemen aktif kontigu.

procedure Enqueue1(inout Q: QueuePasien, P: Pasien)
  { kamus: i, pos: integer }
  if Q.head = 0 then Q.head ← 1; Q.tail ← 1; Q.wadah[1] ← P; return
  if Q.tail = 5 then return
  for i ← Q.head to Q.tail do
    if Q.wadah[i].ktp = P.ktp then return
  pos ← Q.head
  while pos ≤ Q.tail and Q.wadah[pos].kategori ≤ P.kategori do pos ← pos + 1
  for i ← Q.tail downto pos do Q.wadah[i+1] ← Q.wadah[i]
  Q.wadah[pos] ← P; Q.tail ← Q.tail + 1

procedure Enqueue2(inout Q: QueuePasien, P: Pasien)
  { kamus: i, pos, n: integer }
  if Q.head = 0 then Q.head ← 5; Q.tail ← 5; Q.wadah[5] ← P; return
  n ← Q.tail - Q.head + 1
  if n = 5 then return
  { ratakan ke kanan bila ada ruang di kanan }
  while Q.tail < 5 do
    for i ← Q.tail downto Q.head do Q.wadah[i+1] ← Q.wadah[i]
    Q.head ← Q.head + 1; Q.tail ← Q.tail + 1
  pos ← Q.head
  while pos ≤ Q.tail and Q.wadah[pos].kategori ≤ P.kategori do pos ← pos + 1
  for i ← Q.head to pos - 1 do Q.wadah[i-1] ← Q.wadah[i]
  Q.wadah[pos-1] ← P; Q.head ← Q.head - 1

Enqueue1 menggunakan model head stabil dengan asumsi head tetap 1 dan aktif hingga tail; ia menolak KTP duplikat sebagaimana spesifikasi. Enqueue2 tidak mensyaratkan pemeriksaan duplikat. Ruang kosong yang tersisa pada array boleh ditandai dengan sentinel dan tidak termasuk rentang head–tail.

Pada contoh ganjil, KTP 1005 belum ada dan Dini kategori 2 masuk setelah Cici dan sebelum Sari: [Ani, Doni, Cici, Dini, Sari]. Contoh genap menyatakan kategori Dini sebagai teks “Anak”; normalisasikan ke kode 2 seperti definisi kategori. Semula slot pertama kosong dan elemen berada pada 2–5; setelah prefix bergeser ke kiri hasilnya sama dengan head=1 dan tail=5.

3. Postfix

Untuk operator biner, pop pertama adalah operand kanan dan pop kedua operand kiri. Abaikan karakter selain digit dan operator.

{ kamus tambahan: T: Tstack; i: integer; c: character; kiri, kanan, hasil: real }
input(exp); createStack(T)
for i ← 1 to length(exp) do
  c ← exp[i]
  if tipeKarakter(c) = 2 then push(T, charToInt(c))
  else if tipeKarakter(c) = 1 then
    pop(T, kanan); pop(T, kiri)
    if c = '+' then hasil ← kiri + kanan
    if c = '-' then hasil ← kiri - kanan
    if c = '*' then hasil ← kiri * kanan
    if c = '/' then hasil ← kiri / kanan
    push(T, hasil)
  end if
end for
pop(T, hasil); output(hasil)

Asumsi ekspresi valid seperti soal dan kedalaman maksimum stack tidak lebih dari 5. Penggantian digit 0 menjadi 2 dilakukan sebelum evaluasi. Daftar berikut menulis dasar stack di kiri dan puncak di kanan; huruf menyatakan digit NIM setelah penggantian.

Token	Ganjil: `A B C + * D /`	Genap: `A B C / + D *`
awal	[]	[]
A	[A]	[A]
B	[A,B]	[A,B]
C	[A,B,C]	[A,B,C]
operator pertama	[A,B+C]	[A,B/C]
operator kedua	[A×(B+C)]	[A+B/C]
D	[A×(B+C),D]	[A+B/C,D]
operator akhir	[A×(B+C)/D]	[(A+B/C)×D]

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

Aktifkan JavaScript untuk panel belajar dan visual interaktif. Buka naskah PDF.body { height: auto; overflow: auto; } #exam-viewer { display: none; } #exam-text-MIK1624302-uts-2025, #exam-content-MIK1624302-uts-2025 { display: block !important; padding: 1rem; }