UJIAN AKHIR SEMESTER GANJIL 2009/2010 Algoritma dan Struktur Data / CS CS2014 HARI
:
Rabu, 6 Januari 2010
WAKTU
:
135 menit
DOSEN
:
TIM
SIFAT
:
Tutup p Buku
1
2
3
NIM: Nama : Tanda tangan:
4
5
T
Petunjuk: • Periksalah kelengkapan halaman soal. Tidak ada toleransi penilaian bagi mahasiswa yang tidak lengkap halaman soalnya. , dan semua dikerjakan pada lembar soal • Soal terdiri atas .... bagian dengan rincian: ini.
BAGIAN I. Decimal to Binary Conversion [9] Tuliskan Procedure rocedure Dec2Bin( Dec2Bin(I/O I/O S: Stack; input Number: integer) integer untuk melakukan konversi bilangan desimal ke biner & menuliskan hasilnya. Implementasikan dengan struktur data STACK. Asumsi beberapa primitif beri berikut kut telah diimplementasikan. Function IsEmpty(S: Stack) Stack) boolean {Mengirimkan TRUE jika stack kosong} Procedure Push(I/O S: Stack, input X: integer); {Menambahkan X sebagai elemen stack S} {I.S. S mungkin kosong, tabel penampung elemen stack TIDAK penu penuh F.S. X menjadi TOP yang baru, TOP bertambah 1} Procedure Pop(I/O S: Stack, output X: integer); {Menghapus X dari stack S} {I.S. S tidak mungkin kosong} {F.S. X adalah nilai elemen TOP yang lama, TOP berkurang 1} Procedure Dec2Bin(I/O S: Stack; input Number: integer) {Mengkonversi Number kedalam representasi bilangan biner} {I.S. Stack kosong} {F.S. Menuliskan ke layar hasil konversi Number dalam representasi biner. Stack kosong} Kamus lokal Quotient, remainder : integer Hasil : integer
Halaman 1 dari 9
Algoritma {proses konversi decimal to binary} While Number <> 0 Quotient number div 2; Remainder number mod 2; Push(S,remainder); Number quotient; {tulis hasil ke layar} While (!IsEmpty(S)) Pop(S,hasil); Output(hasil);
Bagian II. Recursive Problem [9] Diketahui kamus sebagai berikut: Type Address : ^node Type node :
Type bintree : address
Tuliskan algoritma rekursif untuk mencari sebuah nilai x pada BST. Function TreeSearch (P : bintree , x : infotype) address {Mengembalikan alamat dari info x jika ditemukan, mengembalikan NIL jika tidak ditemukan} Kamus if (P = NIL) OR (x = info(P)) then return P else if (k < info(P)) then return TreeSearch (left(P),x) else return TreeSearch (right(P),x)
Bagian III. Graph [37] Diberikan sebuah graf berarah dengan 4 buah simpul seperti yang ditunjukkan gambar berikut.
Halaman 2 dari 9
a. Gambarkan representasi graf di atas dengan menggunakan representasi adjacency list dimana vertex direpresentasikan secara kontigu dan relasi antar vertex dalam representasi berkait pointer [6] Jawab:
b. Gambarkan representasi graf di atas dengan menggunakan varian dari representasi adjacency list yaitu vertex dan relasi antar vertext dalam representasi berkait pointer.[6] Jawab:
c. Tuliskan deklarasi struktur data untuk representasi berkait pointer graf di atas [6] Jawab: Type Type
simpul : pointer to tagSimpul sisi : pointer to tagSisi Halaman 3 dari 9
Type tagSimpul : < firstsisi : sisi ; infonya di mana? Nextsimpul : simpul> Type tagSisi : <endpoint : simpul; Nextsisi : sisi> Type graf : simpul
d. Tuliskan algoritma Topological Sort dari graf di atas dengan mengimplementasikan struktur data queue. Asumsi beberapa primitif queue berikut sudah diimplementasikan. [15] Procedure CreateEmpty(Output Q: Queue); I.S sembarang F.S sebuah Q kosong terbentuk Proses. Membuat sebuah Q kosong Function IsEmpty(Q:Queue) boolean Mengembalikan nilai TRUE jika Q kosong, FALSE jika tidak Procedure Add(I/O Q: Queue, x: vertex); I.S Q mungkin kosong, tabel penampung elemen Q tidak penuh F.S x menjadi tail yang baru, tail “maju” Procedure Del(I/O Q:Queue, output x:vertex); I.S Q tidak mungkin kosong F.S X adalah nilai elemen head pada I.S
Jawab: Procedure TopSort(input G:graph; output TopS: Tabel) I.S Graph G terdefinisi & indegrees tiap vertex telah disimpan dalam tabel indegree yang didefinisikan secara global. F.S Urutan node hasil pengurutan tersimpan dalam tabel TopS Kamus Q: Queue; i: integer; v,w: vertex; Algoritma CreateEmpty(Q); for each vertex v do if indegree[v]=0 then Add(Q,v); If (IsEmpty(Q)) then Output(“Graph has a cycle”) Else i=1; Repeat Halaman 4 dari 9
Del(Q,v); TopS[i]=v; i=i+1; for each w adjacent to v do indegree[w]=indegree[w]-1 if indegree[w]=0 then add(Q,w); Until (IsEmpty(Q))
e. Tuliskan hasil urutan topologis dari graf di atas [4] Jawab: 4-1-2-3-5
Bagian IV. Queue [24] Perhatikan ilustrasi queue di bawah ini.
a. Tuliskan kamus yang merepresentasikan queue di atas [6]. Kamus Data type ElementQueue : type adrQueue : ^ElementQueue type QQueue :
b. Tuliskan algoritma untuk melayani antrian yang sudah ada [9] Procedure QueueRemove(Input/Output QQ: QQueue) {Mengambil sebuah element pada Queue dan menampilkan Info Namanya dengan aturan FIFO I.S. Queue Terdefinisi dan mungkin kosong F.S. Queue berkurang sebuah Elemen atau mungkin menjadi Kosong, jika Queue yang akan dilayani ternyata Kosong, maka akan menampilkan Queue Masih Dalam Keadaan Kosong } Kamus : P : AdrQueue; Algoritma Halaman 5 dari 9
P QQ.FrontQueue Output (P^.Nama) QQ.FrontQueue P^.nextQueue Dealokasi (P)
c. Tuliskan algoritma untuk menampilkan seluruh elemen yang ada pada Queue tersebut [9] Procedure QueueDisplay(Input QQ: QQueue) {Menampilkan seluruh element pada Queue I.S. Queue Terdefinisi dan mungkin kosong F.S. Seluruh Element Queue Ditampilkan Info Namanya } Kamus : P : AdrQueue; Algoritma P QQ.FrontQueue While (P <> Nil) Output (P^.Nama) P P^.nextQueue
Bagian V. Heap Tree [21] Diketahui kumpulan integer tersimpan dengan struktur Heap, dengan representasi Berkait Pointer. Nilai maksimum menempati posisi root, dan diasumsikan tiap nilai adalah unik. a. Buatlah deklarasi struktur Heap tersebut [6] type adrHeap : Pointer to Elmt type Elmt :
: adrHeap,
Right : adrHeap> type Heap : adrHeap H : Heap
b. Buatlah prosedur insert pada pohon Heap, dengan menggunakan stack dan queue yang masing-masing
elemennya bertipe adrHeap. Diketahui pada kamus global telah terdefinisi sejumlah primitif [15]: {Kamus Global} Procedure CreateEmptyS (Output S : Stack) {Membuat sebuah stack kosong}
Halaman 6 dari 9
{I.S : sembarang} {F.S : sebuah stack S kosong siap dipakai terdefinisi} Function StackEmpty (S: Stack) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong} Procedure PushS (Input/Output S : Stack Input E : Infotype) {Menambahkan sebuah elemen baru pada TOP, dengan elemen informasinya} {IS. Terdefinisi stack S mungkin kosong, dan elemen E FS. Info E ditambahkan sebagai elemen Top dari S}
yang
diketahui
Procedure PopS (Input/Output S : Stack; Output E : Infotype) {I.S : stack tidak kosong} {F.S : info elemen TOP disimpan pada E, alamat TOP yang lama didealokasi} {Menghapus elemen stack, stack tidak boleh kosong dan mungkin setelah penghapusan stack menjadi kosong} Procedure CreateEmptyQ (output Q : Queue) {IS. – FS. Terdefinisi Queue kosong} boolean Function QueueEmpty (Q : Queue) {Test terhadap Queue, True jika kosong, False jika tidak} Procedure AddQ (input/output Q : Queue; input E : infotype) {IS. Terdefinisi queue Q mungkin kosong, dan elemen E FS. Info E ditambahkan sebagai elemen pertama dari Q} Procedure DelQ (input/output Q : Queue; output E : infotype) {IS. Terdefinisi queue Q tidak kosong FS. E berisi info elemen yang dihapus dari Q, elemen pertama didealokasi} Procedure Tukar(input/output X,Y : integer) {IS. Terdefinisi nilai X dan Y} {FS. Nilai X = Y, dan Y = X}
Jawaban : Procedure Insert_Heap (input/Output
H : Heap, input X : adrHeap)
{IS. Terdefinisi pohon Heap H mungkin kosong, dan elemen X } {FS. Elemen X ditambahkan pada pohon Heap} Kamus P : adrHeap V, Child, Parents :adrHeap Q : Queue; S : Stack Stop : boolean {variabel boolean untuk menghentikan looping}
Halaman 7 dari 9
Algoritma {kasus kosong, Elemen X menjadi Root} If (H=Nil) then H X Else {Meletakkan Elemen X pada node terakhir dari pohon Heap} CreateEmptyQ(Q) {Create Empty Queue} CreateEmptyS(S) {Create Empty Stack} Stop False {Inisialisasi variabel boolean} P H {P menunjuk ke H} AddQ(Q,P) While Not Stop do DelQ(Q,P) If (Left(P)≠Nil and Right(P)≠Nil) then AddQ(Q,Left(P)) AddQ(Q,Right(P)) PushS(S,P) Kok ngga ada P = Next(P)?? else Stop True {Stop = True, (Left(P)=Nil) or (Right(P) =Nil) }
If
Left(P)=Nil then Left(P) X
Else Right(P) X PushS(S,P)
{Heapifying : membentuk struktur Heap, nilai parents > nilai children} Child X Stop False While Not StackEmpty(S)and not Stop do PopS(S,P) Parents P If Left(Parents) = Child or Right(Parents)=Child then If Info(Parents) < Info(Child) then Tukar(Info(Parents),Info(Child)) Child Parents else Stop True {StackEmpty or Stop}
Halaman 8 dari 9
Halaman 9 dari 9
