UJIAN TENGAH SEMESTER GANJIL 2008/2009 Algoritma dan Struktur Data / CS2014 HARI
:
Rabu, 5 November 2008
WAKTU
:
135 menit
DOSEN
:
TIM
SIFAT
:
Tutup Buku
NIM: Nama : Tanda tangan:
Petunjuk: • Periksalah kelengkapan halaman soal. Tidak ada toleransi penilaian bagi mahasiswa yang lalai memeriksa kelengkapan halaman soal. • Soal terdiri atas dua bagian dengan rincian: empat soal studi kasus dan lima soal pilihan ganda, dan semua dikerjakan pada lembar soal ini.
A. Bagian I. Studi Kasus 1.
BUKU Diketahui data pengarang dan buku. Aturan yang berlaku adalah : seorang pengarang dapat mengarang dapat mengarang lebih dari satu buku, dan satu buku dapat dikarang oleh lebih dari 1 buku dapat dikarang oleh lebih dari satu pengarang. Pengarang dan buku memiliki identitas yang unik Contoh : B1 B2 B3
P1 P2 P3 P2 P1 P3
KodeBuku : B1, B2, B3 IdPengarang : P1, P2, P3 Representasi :
a. Tuliskan kamus untuk mendefinisikan tipe data berdasarkan representasi struktur Halaman 1 dari 15
data di atas ! Jawab: type type type type type type type type
adrPengarang = ^ElmtPengarang adrBuku = ^ElmtBuku adrRelasi = ^ElmtRelasi ElmtPengarang =
ElmtBuku = ElmtRelasi = ListPengarang = ListBuku =
b. Tuliskan procedure untuk mencetak idpengarang jika diketahui kodebuku. Contoh : input : B3 maka yang dicetak adalah idpengarang dari pengarang buku B3 yaitu: P1, P3 Procedure CetakIdPengarang (input LBuku:ListBuku; input LPengarang:ListPengarang; input KodeCari:string) {I.S. LBuku adalah list buku dan LPengarang list Pengarang, keduanya terdefinisi dan tidak kosong} {F.S. Data pengarang dengan KodeCari diketahui telah dicetak } Kamus pBuku: adrBuku pPengarang: adrPengarang pRel: adrRelasi Algoritma pBuku ← LBuku.First {Pencarian KodeBuku yang bersesuaian dengan KodeCari} while (pBuku^.Next<>NIL) and (pBuku^.KodeBuku<>KodeCari) do pBuku ← pBuku^.Next {EndWhile} if pBuku^.KodeBuku = KodeCari then pPengarang ← LPengarang.First while pPengarang<>NIL do pRel ← pPengarang^.Mengarang while pRel<>NIL do if pRel^.Pengarang=pBuku then output(pPengarang^.IdPengarang) pRel ← pRel^.Next {EndWhile} pPengarang ← pPengarang^.Next else 0utput (‘data tidak ada’) Petunjuk : Selain perintah output yang ada di template soal, tidak ada perintah output lagi
c. Tuliskan algoritma procedure untuk mencetak jumlah buku yang sudah dikarang oleh masing-masing penulis. Halaman 2 dari 15
Procedure JmlBukuPenulis (input LPengarang :ListPengarang; input LBuku:ListBuku) {I.S. ListPengarang adalah list Pengarang dan LBuku list buku, keduanya terdefinisi dan tidak kosong} {F.S. Kode setiap pengarang beserta jumlah buku yang dikarangnya telah dicetak} Kamus pPengarang: adrPengarang pRel: adrRelasi JumBuku : integer {Jumlah buku} Algoritma pPengarang ← LPengarang.First while pPengarang<>NIL do output(pPengarang^.IdPengarang) pRel ← pPengarang^.Mengarang JumBuku ← 0 while pRel<>NIL do JumBuku ← JumBuku + 1 pRel ← pRel^.Next {pRel=NIL} Output(JumBuku) pPengarang ← pPengarang^.Next {pMK=NIL} Petunjuk : Selain perintah output yang ada di template soal, tidak ada perintah output lagi
2.
BILANGAN GANJIL Jika diketahui definisi kamus sebagai berikut: Kamus address:^Element_list Element_list=Record < info:integer next:address > List=Record < First : address >
Tuliskan algoritma untuk menghapus semua bilangan ganjil, baik positif maupun negatif. Gambar di bawah ini menggambarkan kondisi initial state dan final state dari persoalan tersebut.
Function DeleteOdd(I/O L:List) integer
{ mengembalikan jumlah elemen yang dihapus jika berhasil, dan nilai 0 jika tidak ada Halaman 3 dari 15
elemen yang terhapus. List L terdefinisi, mungkin kosong.} Kamus p,prec : address count: integer Algoritma count 0 prec nil p first(L) while p<>nil if (info(p)mod 2 = 1) then count++ /* periksa posisi p */ if prec=nil then /*delete first*/ first(L) next(first(L)) p first(L) else /* delete after and last */ next(prec) next(next(prec)) p next(prec) else { jika elemen bilangan genap } prec p p next(p) {end while} count
3.
DATA PROYEK Suatu sistem harus mengelola data pegawai terhadap proyek yang dikerjakannya. Hal ini untuk keperluan honor yang akan diterima oleh setiap pegawai sesuai kontribusi waktu. Informasi lengkapnya dapat dilihat pada tabel di bawah ini: Tabel Pegawai Id_Pegawai
Nama
TanggalLahir
P1 P2 P3 P4 P5
Joe Mary Andrew Joe Jill
7 Juli 1949 3 Juni 1961 11 Pebruari 1965 22 April 1964 17 Mei 1966
Tabel Proyek Id_Proyek Proj 1 Proj 2 Proj 3
Deskripsi SIM Akademik SIM Perpustakaan SIM Kepegawaian
Tarif per satuan waktu 100000 200000 150000
Tabel Pegawai_Proyek Id_Pegawai
No Proyek
Total waktu untuk proyek
P1 P3 P2 P2 P3 P2 P5
Proj 1 Proj 1 Proj 2 Proj 3 Proj 2 Proj 1 Proj 3
20 16 35 42 17 83 41 Halaman 4 dari 15
Jika informasi tersebut direpresentasikan dengan struktur data internal seperti gambar di bawah ini
a. Tuliskan kamus untuk representasi tersebut Jawab: Kamus Type adrRelasi: pointer to ElmtRelasi Type adrPeg: pointer to ElmtPeg Type adrProj: pointer to ElmtProj Type ElmtRelasi: < waktu: integer; Pegawai: adrPeg; Proyek: adrProj; nextRelasi: adrRelasi > Type ElmtPeg: < idPeg: string; tglLahir: date; namaPeg: string; nextPeg: adrPeg > Type ElmtProj: < id_Proj: string; Deskripsi: string; Tarif: integer; nextProj: adrProj > Type ListPProj: adrRelasi Type ListPeg: adrPeg Type ListProj: adrProj
b. Tuliskan procedure untuk menuliskan data pegawai lengkap beserta data proyek, jika terlibat dalam proyek. Procedure ListProjLengkap(input ListPProj) {Menuliskan daftar id pegawai
FirstPeg: &
nama
ListPeg,
pegawai
Halaman 5 dari 15
input
beserta
FirstPProj: proyek
yang
dikerjakan oleh pegawai tersebut I.S: List Pegawai & pegawai_proyek terdefinisi, mungkin kosong. F.S: Menuliskan informasi pegawai beserta proyek yang dikerjakan. Jika list pegawai kosong, tuliskan ”List pegawai kosong”.} Kamus ptrPeg: adrPeg ptrRelasi: adrRelasi Algoritma ptrPeg firstPeg If ptrPeg=nil then output ”List pegawai kosong” Else Repeat Output (idPeg(ptrPeg)) Output (namaPeg(ptrPeg)) ptrRelasi firstPProj while (ptrRelasi<>nil) if pegawai(ptrRelasi)=ptrPeg then output (id_proj(proyek(ptrRelasi))) ptrRelasi nextRelasi(ptrRelasi) {seorang pegawai sudah ditulis informasinya} {cek pegawai berikutnya} ptrPeg nextPeg(ptrPeg) Until ptrPeg=nil
c. Tuliskan procedure untuk menghitung honor proyek yang diterima setiap pegawai yang terlibat berdasarkan kontribusi waktu. Tampilan yang diharapkan sebagai berikut: Pegawai P1 P2 P3 P5
Total Honor Nominal 1 Nominal 2 Nominal 3 Nominal 4
Procedure HitungHonorProj(input FirstPeg: ListPeg, input FirstPProj: ListPProj) {Menuliskan daftar honor setiap pegawai berdasarkan kontribusi waktu I.S: List Pegawai & Pegawai_Proyek terdefinisi, mungkin kosong F.S: Hanya pegawai yang mempunyai kontribusi waktu didalam proyek, dihitung honornya sesuai tarif proyek. Jika list pegawai kosong, tuliskan ”List Pegawai kosong”. Ada kemungkinan seorang pegawai mendapat honor lebih dari satu proyek} Kamus ptrPeg: adrPeg ptrRelasi: adrRelasi honor: integer Algoritma ptrPeg FirstPeg if ptrPeg=nil then output (”List Pegawai Kosong”) else
Halaman 6 dari 15
repeat output(namaPeg(ptrPeg)) ptrRelasi FirstPProj honor 0 while (ptrRelasi<>nil) if pegawai(ptrRelasi)=ptrPeg then honor honor + waktu(ptrRelasi)*tarif(proyek(ptrRelasi)) ptrRelasi nextRelasi(ptrRelasi) {honor seorang pegawai selesai dihitung, tuliskan} Output (“Total honor: ”,honor) ptrPeg nextPeg(ptrPeg) until ptrPeg=nil
d. Tuliskan procedure untuk menuliskan nama-nama pegawai yang terlibat dalam proyek berdasarkan Id_Proyek-nya. Procedure ProyekPeg(input FirstPProj:ListPProj, input IdProyek: string) {Mencari nama-nama pegawai yang mengerjakan proyek IdProyek I.S: List Pegawai_Proyek tidak kosong. F.S: Jika ditemukan Id_proyek=IdProyek, dituliskan nama pegawai yang terlibat. Jika tidak ada IdProyek, tidak menuliskan apa-apa. } Kamus ptrRelasi: adrRelasi Algoritma ptrRelasi FirstPProj while (ptrRelasi<>nil) if id_proj(proyek(ptrRelasi))=IdProyek then output(namaPeg(pegawai(ptrRelasi))) ptrRelasi nextRelasi(ptrRelasi)
4.
Diketahui sebuah list berisi sejumlah elemen, beberapa procedure primitive telah disediakan, antara lain: function IsEmpty(L:List) boolean /* I.S. sembarang*/ /* F.S. Mengembalikan nilai True jika list kosong Mengembalikan nilai False jika list tidak kosong */ Procedure CreateList(Output L:List) /* I.S. sembarang*/ /* F.S. Terbentuk List Kosong*/ function Alokasi(L: integer) address /* I.S. sembarang*/ /* F.S. Terbentuk List Kosong*/ Procedure InsertFirst(I/O L:List, P:address) /* I.S. L mungkin kosong, P Sudah di alokasi */ /* F.S. P elemen pertama List L*/ Procedure InsertLast(I/O L:List, P:address)
Halaman 7 dari 15
/* I.S. L mungkin kosong, P Sudah di alokasi */ /* F.S. P elemen Terakhir dari List L */
Tugas anda adalah sebagai berikut : a. Mendefinisikan Struktur List yang akan anda buat Type address: ^ElemenList Type ElemenList = < info: integer; next: address; > Type List = < First: address >
b. List tersebut akan dipisah menjadi 2 buah list yang baru dan berbeda (List L akan di pisah menjadi L1 dan L2), buatlah algoritma untuk memisahkan list tersebut Function JumlahElemenList(L:List) integer /* I.S. sembarang*/ /* F.S. mengembalikan banyaknya elemen list, mengirimkan 0 jika list kosong */ Kamus JmlElmn : int; P : address Algoritma P First(L); JmlElmn 0; while (P <> Nil) do JmlElmn JmlElmn + 1; P next(P); end while; JmlElmn Procedure PisahList(output L1:List, output L2:List, input L:List) /* I.S. L mungkin kosong */ /* F.S. dibuat dua buah list L1 dan L2 */ /* seharusnya ada tambahan statemen bahwa L tetap */ /* L1 berisi setengah elemen dari List L, */ /* dan L2 sisanya */ /* jika banyak elemen di L ganjil, maka separuh nya adalah JumlahElemenList(L) div 2 */ Kamus JmlL1 : int; Counter : int; Last, newP : address; Algoritma CreateList(L1); CreateList(L2); if First(L) <> Nil then
Halaman 8 dari 15
JmlL1 JumlahElemenList(L) div 2; Counter 0 {traversal list L sampai akhir} Last First(L) while (next(Last) <> Nil) do newP=alokasi(info(Last)) if (Counter <= JmlL1) then if First(L1) = Nil then InsertFirst(L1, newP); else InsertLast(L1, newP); endif else if First(L2) = Nil then InsertFirst(L2, newP); else InsertLast(L2, newP); endif endif Counter Counter + 1: Last next(Last); end while else print “LIST KOSONG…!” endif
B. Bagian II. Pilihan Ganda Berilah tanda silang (X) pada jawaban yang tepat. 1.
Diketahui definisi kamus dan gambar sebagai berikut: Kamus : {List direpresentasi dg pointer} Type Address : ^ElmtList {pointer to ElmList type InfoType : …………….{terdefinisi} type ElmtList : type List : address
juga boleh}
First
A
B
C
D
Dibawah ini adalah potongan algoritma yang benar agar P menunjuk elemen terakhir dari list adalah : A.
Procedure NunjukAkhir (input L: list , output P:address ) {IS : Terdefinisi L FS : P menunjuk elemen terakhir dari List, elemen list tidak berubah} Halaman 9 dari 15
Kamus : Algoritma : P← ← L.First while P <> nil do P← ←P^.next B. Procedure NunjukAkhir (input L: list, output P:address ) {IS : Terdefinisi L FS : P menunjuk elemen terakhir dari List, elemen list tidak berubah} Kamus : Algoritma : P← ← L.First while P ^.next<> nil do P← ←P^.next C. Procedure NunjukAkhir (input First: list, output P:address ) {IS : Terdefinisi L FS : P menunjuk elemen terakhir dari List, elemen list tidak berubah} Kamus : Algoritma : P← ← First while P <> nil do P← ←P^.next D. Procedure NunjukAkhir (input First: list, output P:address ) {IS : Terdefinisi L FS : P menunjuk elemen terakhir dari List, elemen list tidak berubah} Kamus : Algoritma : P← ← First while P^.next <> nil do P← ←P^.next E. Procedure NunjukAkhir (input L : list, output P:address ) {IS : Terdefinisi L FS : P menunjuk elemen terakhir dari List, elemen list tidak berubah} Kamus : Algoritma : while P^.next <> nil do L.First← ←L.First^.next P← ←L.First Jawab: D
Halaman 10 dari 15
2.
Diketahui Potongan program sebagai berikut : [01]typedef struct tElmtList *address; [02]typedef int infotype; [03]typedef struct tElmtList [04] { [05] infotype info; [06] address next; [07] }Elmlist; [08] [09]typedef struct [10] { [11] address first; [12] }list; [13] [14]void BalikList(list *L) [15]{ [16] address p,preclast,last; [17] /*mencari alamat elemen terakhir*/ [18] last= (*L).first; [19] while (last->next!=NULL) [20] { [21] last=last->next; [22] } [23] /*last->next=nil*/ [24] p=(*L).first; [25] /*Proses membalik list*/ [26] (*L).first = last; [27] do [28] { [29] preclast=p; [30] /*mencari alamat sebelum elemen yang ditunjuk last*/ [31] while (preclast->next != last) [32] preclast=preclast->next; [33] last->next=preclast; [34] last=preclast; [35] }while (last !=p); [36] last->next=NULL; [37] } Procdure Balik List di atas digunakan untuk membalik susunan list Ilustrasi :
Statement yang salah dari potongan program di atas adalah : A. baris [35] harusnya while (last->next !=p); B. baris [33] harusnya last=preclast; C. baris [33] harusnya last=preclast->next; D. baris [19] harusnya while (last->next!=NULL) E. Tidak ada statement yang salah Jawab: E
Halaman 11 dari 15
3.
Jika diketahui representasi fisik suatu list dengan menggunakan pointer adalah sebagai berikut : Kamus type adrElmt type Elmt
= ^Elmt =
>
First P
A
B
C
D
manakah bagian algoritma yang tepat untuk menghapus elemen C dari list : A. P^. Kiri^. Kanan P^. Kanan P^. Kiri Nil P^. Kanan^. Kiri P^. Kiri P^. Kanan Nil free(P) B.
P^ Kiri^ Kanan P^ Kanan P^ Kanan^ Kiri P^ Kiri P^ Kiri Nil P^ Kanan Nil free(P)
C.
P^. Kiri^. Kanan P^. Kanan P^. Kanan^. Kiri P^. Kiri P^. Kiri Nil P^. Kanan Nil free(P)
D.
P^ Kiri^ Kanan P^ Kanan P^ Kiri Nil P^ Kanan^ Kiri P^ Kiri P^ Kanan Nil free(P)
E.
P^. Kiri Nil P^. Kanan Nil P^. Kiri^. Kanan
P^. Kanan P^. Kanan^. Kiri P^. Kiri free(P)
Halaman 12 dari 15
Jawab: C
4.
Jika suatu list dideklarasikan sebagai berikut : Kamus type adrElmt type Elmt
= ^Elmt = type List =
Pada gambar di bawah ini, manakah instruksi yang tepat untuk menambahkan elemen sesudah elemen yang ditunjuk oleh pointer P : Q First
E
P
A
D
A.
Next(P) Q Next (Q) Next(P)
B.
Next(Q) Next (P) Next (P) Q
C.
Next (Q) P Next (P) Q
D.
Next(P) Q Next (Q) P
E.
F
Next (P) Q
Next (Q) Next (P) Jawab: B 5.
Diketahuhi deklarasi list seperti berikut : Kamus (Deklarasi) Type adrCabangOR = ^ElmtCabangOR Type adrKontingen = ^ElmtKontingen
Halaman 13 dari 15
Type adrAtlet = ^ElmtAtlet Type ElmtCabangOR = : string; Type ElmtKontingen= : integer; Type ElmtAtlet = Type List = Var L :List
Representasi logik list dengan deklarasi seperti di atas adalah : A.
First
... First
... First
...
B. First
...
...
C.
First
...
Halaman 14 dari 15
D. ...
E.
Tidak ada jawaban yang tepat
Jawab: B
Halaman 15 dari 15
