UJIAN AKHIR SEMESTER GANJIL 2005/2006 ALGORITMA & STRUKTUR DATA / CS2014 HARI WAKTU DOSEN SIFAT
: : : :
Rabu, 4 Januari 2006 135 Menit TIM Tutup Buku
NIM: Nama :
Tanda tangan:
Petunjuk • Baca dengan teliti setiap petunjuk soalnya. • Gunakan Pensil untuk menuliskan algoritma atau kode program. • Soal ujian terdiri atas empat bagian. Jawaban seluruh bagian soal dituliskan pada lembar ini. • Bobot Keseluruhan = 100 BAGIAN I : Data Abstraction (40 poin) Anda bekerja di sebuah perusahaan pada bagian gudang yang menyimpan automobile part (onderdil mobil). Perusahaan tsb menyimpan data banyaknya onderdil yang terdapat pada gudang. Basic operational perusahaan dapat dikatakan ada dua, yaitu pemesanan onderdil ke supplier dan pengiriman onderdil ke bengkel-bengkel. Pemilik bengkel biasanya akan marah jika perusahaan automobile part tersebut tidak memiliki onderdil yang dipesannya, karena pelanggan-pelanggannya akan menunggu lama agar mobil mereka dapat segera diperbaiki. Anda harus menulis program agar pengadaan barang (inventory) di gudang selalu tersedia. Inti program Anda adalah menuliskan ADT INVENTORY yang menangani bookkeeping. Primitif-primitif yang harus dimiliki adalah • Menghitung banyaknya onderdil yang ada di gudang • Melakukan update data jika ada pengiriman onderdil baru dari supplier ke gudang • Melakukan update data jika ada pengiriman onderdil ke bengkel-bengkel. • Pimpinan perusahaan juga ingin mengetahui kuantitas onderdil yang telah dibawah standar minimum perusahaan (istilah: low) sehingga perusahaan dapat melakukan pemesanan onderdil ke supplier sebelum onderdil tsb habis di gudang. (dalam hal ini Anda harus mempunyai parameter kuantitas) Untuk menyederhanakan persoalan, Anda boleh berasumsi bahwa setiap ada pengiriman dan pemesanan onderdil hanya untuk satu jenis onderdil dan banyaknya item tidak dibatasi. Dalam hal ini, Anda tidak tahu ada berapa jenis onderdil di dalam gudang dan terkadang Anda menerima pengiriman onderdil yang jenisnya belum ada di gudang.
1. (5 poin)
Lengkapilah tabel ADT Inventory di bawah ini, berdasarkan atribut-atribut yang disediakan.
Primitive name
constructor
Parameter names and type ---
Process
Create empty list
Return type and value List kosong
Hal 1 dari 6
Shipment
Int Idpart Int quantity
Jika part belum ada maka insert, selain itu tambahkan pada quantity yang ada
---
Delivery
Int Idpart Int quantity
Quantity part tsb berkurang sesuai amount yang dipesan.
---
howMany
Int Idpart
---
Quantity part tsb yg tdp di gudang
---
Daftar Idpart yg menunjukkan seluruh part yang quantity-nya telah < minimum
Low
2. (5 poin)
Int minimum
Tuliskan representasi internal dan struktur data yang akan digunakan untuk implementasi ADT Inventory. Jawaban: List berkait dengan representasi pointer. List tsb merupakan list of asosiasi antara Idpart dan quantity.
Tuliskan lengkap kode program dalam bahasa C untuk realisasi setiap primitive names dan 3. deklarasi tipe untuk ADT Inventory tsb dengan mengacu pada tabel di atas. (30 poin) Jawaban:
Lihat di file inventory.zip !
Hal 2 dari 6
BAGIAN II : Binary Search Tree (BST) 15 poin Diketahui sebuah BST dengan deklarasi: KAMUS Type infotype : integer; Type address : pointer to node; Type node : < info : infotype; Left : address; Right : address; > Type BST : address; Tuliskan dan lengkapi algoritma rekursif untuk menuliskan info node secara terurut ‘descending’ di bawah ini. Sebagai ilustrasi, perhatikan BST berikut.
Output: 60 40 25 20 15 12 10 5
Hal 3 dari 6
Procedure cetakUrut(input P:BST) {I.S. terdefinisi BST P} {F.S. menuliskan info node pada BST P secara terurut descending} {Basis: pohon kosong, tidak melakukan apa-apa {Rekurens: traversal kiri, root, kanan dari pohon P
) }
KAMUS ALGORITMA If P=nil then {kasus kosong} Else cetakUrut(right(P)); output(info(P)); cetakUrut(left(P));
BAGIAN III : Procedure Debugging (20 poin) Asumsi telah terdefinisi ADT Stack dengan elemennya bertipe integer. Gambarkan 1. (10 poin) ilustrasi dari kode di bawah ini kemudian tuliskan nilai dari v, w, x, y, dan z setelah kode berikut dieksekusi ! Stack S; Infotype a,v,w,x,y,z; Inisialisasi(); createEmpty(&S); Push(&S,5); Push(&S,6); Push(&S,7); Pop(&S,&a); v=a; w=infoTop(S)); push(&S,8); push(&S,9); pop(&S,&a); x=a; pop(&S,&a); y=infoTop(S); pop(&S,&a); z=a;
Jawaban:
Jawab sendiri aja y.. kan gampang..
Hal 4 dari 6
2. Dengan memanfaatkan algoritma cetakUrut() dan BST pada bagian II, telusuri (10 poin) algoritma di bawah ini (gambarkan tracing algoritma) dan tuliskan outputnya jika x=20. Procedure ApaIni(Input X:integer, P : BST) {I.S : terdefinisi Binary Search Tree P, P tidak kosong} {F.S : Mencetak informasi yang lebih besar dari nilai X dalam binary Search Tree P secara descending} Kamus Procedure CetakUrut(Input P:BST) Algoritma If X = info(P) then CetakUrut(right(P)) Else if X < info(P) then ApaIni (left(P)) else if X > info(P) then ApaIni(right(P))
Jawaban:
Idem…
Hal 5 dari 6
BAGIAN IV : Definition (25 poin) Tuliskan jawaban T/F (true/false) pada ruang yang disediakan. __T__ Memory is released when we set a pointer to NULL. __T__ Two pointers can point to the same memory location. __F__ A stack can never become full when implemented using dynamic memory. __T__ Stacks and queues can be implemented using arrays. __T__ Data is removed from a queue in first-in-first-out order. __T__ A stack can be used to evaluate arithmetic expressions in postfix. __F__ A queue can be used to simulate the behavior of a recursive function. __F__ A recursive function can not access global variables. __T__ All recursive functions must have a terminating condition. __T__ All recursive functions can be rewritten using iteration instead. __F__ A linked list with 100 nodes takes less space than an array with 100 elements. __T__ A unsorted linked list is easier to insert into than a sorted linked list. __T__ A sorted linked list takes less time to search than unsorted list. __T__ It is faster to insert data into a binary search tree than into a sorted array. Pada bagian kiri, tuliskan nomor jawaban dari istilah yang sesuai dengan definisi __4_ a linked list in which the rear item refers back to the head item __9_ reduction of a problem to a smaller instance of the same problem __12_ a repeated computation _1__ a data structure of values linked together in memory by a chain of references _3__ a data structure with last-in first-out behavior, supporting push and pop _10_ how to carry out a computation, may be implemented as a procedure _7__ a data structure with first-in first-out behavior _15_ a predicate that becomes true when a computation ends _5__ a programming language construct that supports iteration _8__ a diagram showing the operators and operands of an expression
1.linked list 2.object 3.stack 4.circular list 5.loop 6.primitive data 7.queue 8.expression tree 9.recursion 10. algorithm 11. reduction 12. iteration 13. semantic 14. abstraction 15. termination condition
_6__, such as numbers and symbols, that are built into the language
Hal 6 dari 6
