UJIAN TENGAH SEMESTER GANJIL 2010/2011 Algoritma dan Struktur Data / CS2014 HARI WAKTU DOSEN SIFAT
: : : :
Kamis, 30 Oktober 2009 110 menit TIM Tutup Buku, No Electronic Device
NIM: Nama : Tanda tangan:
Petunjuk: Periksalah kelengkapan halaman soal. Tidak ada toleransi penilaian bagi mahasiswa yang tidak lengkap halaman soalnya. Soal terdiri atas dua bagian dengan rincian: tiga soal studi kasus dan lima soal pilihan ganda, dan semua dikerjakan pada lembar soal ini.
Bagian I. Studi Kasus [82] Studi Kasus 1. Property Warna RGB Diperlukan sebuah struktur data untuk menyimpan property warna RGB sebuah gambar digital. Struktur data yang akan digunakan adalah sebuah list linier. Dalam list tersebut disimpan property warna pixel yang terdapat dalam gambar, dan sebuah kombinasi RGB hanya disimpan 1 kali (unik). Properti warna yang disimpan terdiri dari Red,Green,Blue dengan rentang nilai 0-255. 1. Buatlah definisi type List Warna (list linier sederhana) Type InfoType :
{nilai integer komponen Blue} Type ElmtList :
{komponen sebuah elemen list}
Type Address
: pointer to ElmtList
Type ListWarna:
2. Tuliskan implementasi prosedur InvertColor yang akan melakukan inverse warna (per komponen, Red, Green, dan Blue). Misal nilai komponen Red sebuah elemen 0, maka inverse-nya adalah 255, nilai komponen Green sebuah elemen 10, maka inversenya adalah 245, dan nilai komponen Bluenya adalah 230, maka inversenya adalah 25. Procedure InvertColor(input/output LW : ListWarna) {I.S : ListWarna terdefinisi, TIDAK kosong, minimal terdapat 1 elemen} {F.S: nilai komponen Red, Green, dan Blue tiap elemen diubah menjadi inverse dari nilai awal} Kamus P : address Algoritma Halaman 1 dari 10
Paraf
P First(LW) {awal traversal List} repeat info(P).red 255 – (^P.info).red {invers nilai komponen Red} info(P).green 255 - info(P).green{invers nilai komponen Green} info(P).blue 255 - info(P).blue{invers nilai komponen Blue} P next(P) {next elemen} Until (P=Nil){kondisi berhenti} 3. Tuliskan implementasi prosedur untuk menambahkan sebuah kombinasi warna. Pastikan terlebih dahulu bahwa kombinasi warna tersebut belum ada di list awal. Procedure AddElmt(input/output LW : ListWarna, input r,g,b : integer) {I.S : ListWarna terdefinisi, mungkinkosong} {F.S: menambahkan sebuah elemen dengan info r,g,b, jika pada list belum terdapat kombinasi RGB tersebut} {asumsi : alokasi elemen baru pasti berhasil} Kamus Prev,P,PNew : address Found : Boolean {true jika sebuah elemen nilai rgbnya=rgb yg akan diinsert} Algoritma Prev Nil {inisialisasi} P First(LW) {awal traversal List} If (P=Nil)then{list kosong} {insert first} Alokasi(P) Info(P).red r Info(P).green g Info(P).blue b Next(P) Nil First(LW) P else
Halaman 2 dari 10
Paraf
found false {inisialisasi} repeat if ((info(P).red=r) and (info(P).green=g) and (info(P).blue=b))then {cek apakah rgb current=rgb yang akan diinsert} Found true Else Prev P {next element} P Next(P) Until (P=Nil OR found){kondisi berhentinya di Prev sbg Elmt terakhir yg bukan Nil} If (not found) {insert last} Alokasi(PNew) {alokasi} Info(PNew).red r{set atribut elemen baru} Info(PNew).green g {set atribut elemen baru} Info(PNew).blue b{set atribut elemen baru} Next(PNew) Next(Prev) {insert last} Next(Prev) PNew 4. Tulisakan implementasi fungsi yang akan menghitung jumlah kombinasi warna dengan nilai komponen RGB yang sama, misal R=100,G=100,B=100. Function GetCountEqElmt(LW : ListWarna) integer {mengembalikan 0 jika List kosong} Kamus count : integer {variable untuk menyimpan jumlah sementara} P : address Algoritma {inisialisasi} P First(LW) count 0 While (P<>Nil){kondisi perulangan} Halaman 3 dari 10
Paraf
If ((Info(P).red= Info(P).green) and (Info(P).red= Info(P).blue))then{kondisi penjumlahan} count count+1 P Next(P) {next element} count {terminasi}
Studi Kasus 2 : Kelola Data Macebook Suatu sistem harus mengelola informasi keanggotaan jejaring Macebook yang dapat mengelola anggota, dan relasi (hubungan pertemanan antar anggota). Aturan yang ada adalah anggota harus terdaftar pada list anggota. Masing-masing member bisa berteman dengan member yang lain. Hubungan ini didaftarkan pada suatu list relasi. List Relasi List Anggota IDAnggota Nama RelasiA RelasiB 001 Spongebob 002 001 002 Patrick 002 004 003 Mr Crab 003 001 004 Squidward 001 003 Pada list relasi, Relasi A menyatakan pointer ke member yang meminta hubungan pertemanan, sedangkan relasi B merupakan pointer ke member yang menyetuijui pertemanan. Jika informasi di atas direpresentasikan dengan struktur data internal akan terlihat seperti gambar di bawah ini :
1. Tuliskan kamus untuk representasi struktur data di atas ! Jawab: kamus type ElmtAnggota : type ElmtRelasi
:
Halaman 4 dari 10
Paraf
NextRelasi : adrRelasi> type adrAnggota
: ^ElmtAnggota
type adrRelasi
: ^ElmtRelasi
type ListAnggota
:
type ListRelasi
:
LAnggota
: ListAnggota
LRelasi
: ListRelasi
b.
Tuliskan algoritma procedure untuk menampilkan seluruh daftar pertemanan (siapa berteman dengan siapa)!
Procedure PrintPertemanan(input LAnggota: ListAnggota, input LRelasi: ListRelasi) {Menuliskan daftar pertemanan pada data Macebook I.S: List Anggota & List Relasi terdefinisi, mungkin kosong. F.S: Menuliskan seluruh daftar pertemanan pada media output. Jika list anggota kosong, tuliskan ”List Anggota kosong”, Jika list relasi kosong, tuliskan ”List Relasi kosong”, } Kamus pAng: adrAnggota pRel: adrRelasi Algoritma {mengecek apakah list anggota kosong} if FirstAngg(LAnggota)= nil then output(”List Anggota kosong”) elseif FirstRelasi(LRelasi) = nil then {mengecek apakah list relasi kosong} output(”List Relasi kosong”) else pRel FirstRelasi(LRelasi) repeat {mengambil dan mengoutputkan nama peminta Pertemanan } pAng RelasiA(pRel) output(NamaAnggota(pAng))
Halaman 5 dari 10
Paraf
{mengambil dan mengoutputkan nama yang menyetujui Pertemanan } pAng RelasiB(pRel) output(NamaAnggota(pAng)) {memproses relasi berikutnya} pRel nextRel(pRel) until ( pRel=nil )
c.
Tuliskan algoritma procedure untuk menampilkan jumlah pertemanan (number of friends)!
Procedure printCountRelasi(input LAnggota: ListAnggota, input LRelasi: ListRelasi) {Menuliskan jumlah pertemanan member yang terdaftar pada data Macebook I.S: List Anggota & List Relasi terdefinisi, asumsi tidak kosong. F.S: Menuliskan jumlah pertemanan dari semua member pada media output. Relasi bisa berupa permintaan atau persetujuan terhadap pertemanan. } Kamus pAng: adrAnggota; Algoritma
pRel: adrRelasi;
count : Integer
pAng FirstAnggota(LAnggota) repeat {Inisialisasi loop} Count 0;
pRel FirstRelasi(LRelasi)
{menuliskan nama anggota yang akan dihitung} output(NamaAnggota(pAng)) While pRel <> Nil do If ( pAng = RelasiA(pRel)) or ( pAng = RelasiB(pRel)) then Count Count + 1 pRel nextRel(pRel) output(Count)
{proses relasi berikutnya}
{menampilkan jumlah}
pAng nextAng(pAng) {proses anggota berikutnya} until ( pAng=nil ) d.
Tuliskan algoritma procedure untuk menampilkan daftar teman dari seseorang anggota!
Procedure printTeman(input LAnggota: ListAnggota, input LRelasi: ListRelasi, Halaman 6 dari 10
Paraf
input NamaMember : string) {Menuliskan semua teman oleh seorang member yang diinputkan pada parameter. I.S: List Anggota & List Relasi terdefinisi, asumsi tidak kosong. NamaMember terdefinisi F.S: Menuliskan semua nama teman dari seorang member (NamaMember) ke media output. } Kamus pAng: adrAnggota pRel: adrRelasi Algoritma pAng FirstAnggota(LAnggota) while (NamaAnggota(pAng) <> NamaMember) and (nextAng(pAng) <> Nil) do pAng nextAng(pAng) // bila pAng = nil program akan NULL POINTER EXCEPTION if (NamaAnggota(pAng) <> NamaMember) then output(”bukan anggota member”) else pRel FirstRelasi(LRelasi) while pRel <> Nil do If ( pAng = RelasiA(pRel)) then output(NamaAnggota(RelasiB(pRel))) If ( pAng = RelasiB(pRel)) then output(NamaAnggota(RelasiA(pRel))) pRel nextRel(pRel)
Halaman 7 dari 10
Paraf
Bagian II. Pilihan Ganda [18] Berilah tanda silang (X) pada jawaban yang tepat. Poin setiap soal adalah 3 1. Sebuah modul ADT dalam bahasa C terdiri atas beberapa file. Definisi type dituliskan dalam file : a. Main b. Driver c. Header d. Implementasi e. Dictionary 2. Suatu list direpresentasikan sebagai berikut :
Misal last adalah address yang akan melakukan traversal sampai menemukan elemen list terakhir, maka skema traversal yang benar adalah : a. Last First(L) b. Last First(L) While last <> nil do
While next(last) <> nil do
Last next(last) c.
Last First(L) While next(last) <> First(L) do
Last next(last) d.
Last First(L) While last <> First(L) do
Last next(last) e.
Last next(last)
Last First(L) While next(last) <> A do Last <-- next(last)
3. Diketahui penggalan algoritma berikut ini : Procedure Tebak(input/output L : List, output P : address) {IS. Terdefinisi List L dan address P} {FS. Silahkan ditebak} Kamus Last, PrecLast : address Algoritma Last First(L) While (Next(Last)≠ nil)do Halaman 8 dari 10
Paraf
PrecLast Last Last Next(Last) {end while} P Last if (PrecLast = NIL) then First(L)=NIL else Next(PrecLast)=NIL a. b. c. d. e.
Algoritma di atas melakukan proses : Delete first pada circular list Delete last pada circular list Delete first pada linear list Delete last pada linear list Delete first pada linear list dengan first dan last
4. Perhatikan ilustrasi double linked list berikut ini:
Ilustrasi di atas adalah ilustrasi untuk insert after pada double linked list. Mana dari pernyataan berikut yang benar untuk proses algoritma insert after. a. {a, b, c, d} b. {a, d, c, b} c. {a, c, b, d} d. {d, c, b, a} e. Jika urut-urutan langkah di atas dikerjakan tidak ada yang benar. 5. Apa yang menjadi kesamaan antara representasi data Sigle Circular List dengan Linear List? a. Struktur Datanya b. Algortima InsertFirst-nya c. Algortima InsertLast-nya d. Algoritma DeleteFirst-nya e. Algoritma DeleteLast-nya Halaman 9 dari 10
Paraf
6. Berikut ini cara yang paling tepat untuk menghapus elemen terakhir ialah .....
a.
b.
c.
P First(L) While Next(P)<>First(L) do P Next(P) Next(P) First(L) Last(L) P P First(L) While Next(P)<>Last(L) do P Next(P) Last(L) P Next(P) Last(L) P First(L) While Next(Next(P))<>First(L) do P Next(P) Next(P) Next(Next(P)) Last(L) Next(P)
Halaman 10 dari 10
d.
e.
P First(L) While Next(P)<>First(L) do P Next(P) Last(L) P Next(P) First(L) P First(L) While Next(P)<>Last(L) do P Next(P) Next(P) First(L) Last(L) P
Paraf
