uts_sd

5/17/2018 UTS_SD - slidepdf.com

http://slidepdf.com/reader/full/utssd 1/14

D3 Manajemen InformatikaFakultas Teknik (FT)

Universitas Negeri Surabaya

Nama : Uswatun Hasanah

Nim : 105623080

Kelas : D3- Manajemen Informatika /D/2010

UTS Struktur Data dan Algoritma

Penting untuk diperhatikan:

Kerjakan soal-soal berikut sendiri-sendiri dengan baik dan benar, jika ada

dua atau lebih jawaban sama, maka semua jawaban yang sama tersebut

dianggap tidak mengikuti UTS alias nilai uts-nya kosong.

Jawaban diketik di Ms. Word, dan dikumpulkan dalam bentuk hardcopy

(diprint) dan softcopy (file).

Batas akhir pengumpulan jawaban:

Hardcopy : selasa, 8 mei 2012

Softcopy :

jum’at, 4 mei 2012, dikirim via email ke: [email protected], subject:

uts_struktur_data-nim(nama)

Soal:

1. Buat struct untuk data lagu yang berisi tentang judul lagu, penyanyi, tahun

produksi, nomor track dan kode album, dengan ketentuan program memiliki

dua buah struct yakni:

a. Struct lagu(judul_lagu <string>, penyanyi <string>,

tahun_produksi<string>,rbt<struct_koderbt>)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Album{

mailto:[email protected]






int regNo;

char title[15];

char singerName[15];

char* songs[5];

};

typedef struct Album CD;

int main(){/* 1. Deklarasikan sebuah variabel bernama myAlbum yang

bertipe data CD. */

/* 2. Mintalah pengguna program untuk mengisikan no registrasi

CD ke dalam regNo (maksimum 14 karakter) pada myAlbum. */

/* 3. Mintalah pengguna untuk mengisikan judul album ke dalam

title (maksimum 14 karakter) myAlbum. */

/* 4. Mintalah pengguna untuk mengisikan nama penyanyi ke

dalam singerName (maksimum 14 karakter) myAlbum.*/

/* 5. Mintalah pengguna untuk mengisikan nama lagu satu persatu sampai sejumlah 5 lagu ke dalam array songs pada myAlbum.

Lima adalah batas maksimum jumlah lagu dalam setiap album.

Setiap judul lagu terdiri dari maksimum 14 karakter. */

/* 6. Tampilkan deskripsi myAlbum dengan mencetak setiap data

anggotanya ke layar monitor dengan jelas. */

/* 7. Dealokasikan atau bebaskan memori dari pointer yang

sebelumnya pernah dialokasikan memori. */

system("pause");

return 0;}

b. Struct kodeRBT<nomor_track<int>,kode_album<string>)

2. Dengan menggunakan konsep stack (tumpukan), jelaskan logika untuk

mengubah notasi infix menjadi postfix . Buat ilustrasi dalam stack untuk lebih

memperjelas logikanya.

Asumsi:Notasi Infix = (A+B)/(B-D)*E $ F)

Notasi Postfix = A B + C D – E F $ * /



3. Dengan menggunakan Array, jelaskan dan tuliskan logika untuk:

a. Mengisi Elemen Array adalah

b. Menampilkan Isi dari Array

c. Copy isi array ke array yang lain

d. Hitung Jumlah & Rata

e. Maksimum dan Minimumf. Mencari Elemen Array dan Posisinya

g. Menghapus Elemen Array

h. Menyisipkan Elemen ke dalam Array

i. Swap Elemen Array

Silahkan dibuat asumsi sendiri terkait variablel array yang digunakan.

Jawaban :

**** MENU UTAMA ****

1. Mengisi Elemen Array

2. Menampilkan Isi dari Array

3. Copy Isi Array ke Array yang Lain

4. Hitung Jumlah & Rata

5. Maksimum dan Minimum

6. Mencari Elemen Array dan Posisinya

7. Menghapus Elemen Array

8. Menyisipkan Elemen ke dalam Array

9. Swap Elemen Array

Pilihan Anda [1-9]?

Pogram:

#include

int main(){

int n,i,pilih,average,indekcari,s,p,l,t,r,maks,min;



char cek, indekhapus;

long mul;

mul=0;

float a[100],b[100];

do {

cout<<" ***** MENU UTAMA *****\n";

cout<<"1. Mengisi Elemen Array\n";

cout<<"2. Menampilkan Isi dari Array\n";

cout<<"3. Copy isi array ke array yang lain\n";

cout<<"4. Hitung Jumlah & Rata\n";

cout<<"5. Maksimum dan Minimum\n";

cout<<"6. Mencari Elemen Array dan Posisinya\n";

cout<<"7. Menghapus Eleman Array\n";

cout<<"8. Menyisipkan Elemen ke dalam Array\n";

cout<<"9. Swap Elemen Array\n";

cout<<"Pilihan Anda [1 - 9]= ";

cin>>pilih;

switch(pilih){

case 1:

{cout<<"Banyak Elemen= ";cin>>n;

for(i=0;i<n;i++){< span=""></n;i++){<>

cout<<"a["<<i<<"]= cin="">>a[i];}}</i<<"]=>

break;

case 2:

{cout<<"Isi dari array adalah\n";



for(i=0;i<n;i++){< span=""></n;i++){<>

cout<<"a["<<i<<"]= span=""></i<<"]=>

break;

case 3:

{cout<<"Isi Array A\n";

for(i=0;i<n;i++){< span=""></n;i++){<>

cout<<"a["<<i<<"]= span=""></i<<"]=>

cout<<"\nIsi Array B\n";

for(i=0;i<n;i++){< span=""></n;i++){<>

b[i]=a[i];

cout<<"b["<<i<<"]= span=""></i<<"]=>

break;

case 4:

{cout<<"jumlah dan Rata-rata dari Isi Array berikut:\n";

for(i=0;i<n;i++){< span=""></n;i++){<>

cout<<"a["<<i<<"]= span=""></i<<"]=>

mul=mul+a[i];}

average=mul/n;

cout<<"Jumlah dari Isi Array= "<<mul<<"\n";< span=""></mul<<"\n";<>

cout<<"Rata-rata Array= "<<average<<"\n";}< span=""></average<<"\n";}<>

break;

case 5:

{maks=a[0];

min=a[0];

for(int i=0;i<n;i++)< span=""></n;i++)<>



{if(a[i]>maks)

{maks=a[i];}

else

{min=a[i];}}

cout<<"Nilai maksimum="<<maks<<"\n";< span=""></maks<<"\n";<>

cout<<"Nilai minimum="<<min<<"\n";} span=""></min<<"\n";}>

break;

case 6:

{indekcari=-1;

cout<<"Data yang Dicari= ";cin>>s;

for(i=0;i<n;i++){< span=""></n;i++){<>

if(s==a[i]){

indekcari=i;cek='y';break;}}

if(cek=='y'&&indekcari>=0)

cout<<"Berada di posisi= "<<"a["<<indekcari<<"]"<<"\n";<

span=""></indekcari<<"]"<<"\n";<>

else

cout<<"Data yang Anda Cari Tidak Ada"<<"\n";}

break;

case 7:

{cout<<"Masukkan Data yang Akan Dihapus= ";cin>>s;

for(i=0;i<n;i++){< span=""></n;i++){<>

a[i]=a[i];

if(s==a[i]){

indekhapus=i;break;}}



if(s==a[i]){

cout<<"Data Setelah dihapus= \n";

indekhapus=i;

for (i=indekhapus;i<n-1;i++)< span=""></n-1;i++)<>

a[i]=a[i+1];

for(i=0;i<n-1;i++)< span=""></n-1;i++)<>

cout<<"a["<<i<<"]="<<a[i]<<"\n";}< span=""></i<<"]="<<a[i]<<"\n";}<>

else

{cout<<"Data yang Akan Anda Hapus Tidak Ada"<<"\n";

cout<<"maka Isi Data Tidak Berubah\n";

for(i=indekhapus;i<n-1;i++){< span=""></n-1;i++){<>

a[i]=a[i];}

for(i=0;i<n;i++){< span=""></n;i++){<>

cout<<"a["<<i<<"]="<<a[i]<<"\n";}}}< span=""></i<<"]="<<a[i]<<"\n";}}}<>

break;

case 8:

{cout<<"masukkan nilai yang disisipkan:";cin>>p;

cout<<"masukkan elemen array yang akan digeser:";cin>>l;

if(n<maks)< span=""></maks)<>

{if((l>0)&&(l<=n))

{l--;

for(i=n;i>=l;i--)

{a[i+1]=a[i];}

a[l]=p;

n+=1;}



else

cout<<"posisi di luar jangkauan\n";}

else

{cout<<"array penuh\n";}

cout<<"data baru:\n";

for(int m=0;m<n;m++)< span=""></n;m++)<>

cout<<"a["<<m<<"]= span=""></m<<"]=>

break;

case 9:

{cout<<"\nelemen array yang ditukar :";cin>>t;

cout<<"Ditukar dengan elemen: ";cin>>r;

for(i=0;i<n;i++)< span=""></n;i++)<>

b[i]=a[i];

a[t-1]=b[r-1];

a[r-1]=b[t-1];

cout<<"\nIsi array setelah ditukar\n";

for(i=0;i<n;i++)< span=""></n;i++)<>

cout<<"a["<<i<<"]= span=""></i<<"]=>

break;

}}while(pilih!=10);}

4. Jelaskan tentang implementasi stack dengan menggunakan linked list. Operasi

yang dijelaskan dengan linked list antara lain:

a. pop

b. push



c. BacaStack

Jawaban :

Pengertian Linked list :

sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap

elemennya terdiri dari dua bagian

struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan

elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk

mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak

bersebelahan secara fisik di memori.

Bentuk Umum :

Infotypesebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list

Nextaddress dari elemen berikutnya (suksesor)

Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan

notasi :

Sebelum digunakan harus dideklarasikan terlebih dahulu :

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :

Beberapa Definisi :

1. List l adalah list kosong, jika First(L) = Nil

2. Elemen terakhir dikenali, dengan salah satu cara adalah karena

Next(Last) = Nil

Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null

Single Linked List

Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area.

Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan

sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya



sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer.

Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus

yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan

menunjuk ke NULL).

Pembuatan Single Linked List dapat menggunakan 2 metode:

LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

FIFO (First In First Out), aplikasinya : Queue (Antrean)

Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak

satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list

hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapatmenggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list

berpointer Ganda atau Double Linked List.

Circular Double Linked List

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya

menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Operasi-Operasi yang ada pada Linked List

Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

Find First

Fungsi ini mencari elemen pertama dari linked list

Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

Retrieve



Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu

dikembalikan oleh fungsi.

Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen

pertama dari linked list (head), head akan berpindah ke elemen berikut.

Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen

sesudahnya.

Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda

ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-

data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di

dalam memori.

A. STACK DENGAN SINGLE LINKED LIST

Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat

diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah

penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.

Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen,

sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan

memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat

yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.

Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak

menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh

pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi

oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List



IsEmpt y

Fungsi memeriksa apakah stack yang adamasih kosong.

Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam

single linked list biasa.

Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

Clear

Fungsi ini akan menghapus stack yang ada.

5. Jelaskan dan ilustrasikan serta tuliskan algoritma sorting sebagai berikut:

a. Selection sortLakukan pengulangan dari 0 sampai dengan (N-1). Pada setiap pengulangan dicari data

terkecil diantara data(I+1) sampai data terakhir(N). Data terkecil ini kemudian ditukar

dengan data ke I jika data terkecil tersebut lebih kecil dari data ke i.Algoritma :

1. I 0

2. Selama I < juml data-1 kerjakan no 3 sampai 93. min = I4. j I+1

5. Selama j < juml data kerjakan no 6 sampai 7

6. Jika (data[j] < data[min]) maka min j7. j j+1

8. Tukar data[I] dengan data[min]

9. I I+1

b. Insertion sortAlgoritma :

1. I 12. Kerjakan no 3 sampai 9 jika I < jumlah data

3. index data[I]

4. j I

5. Kerjakan no 6 sampai 7 jika j>0 dan data[j-1] > index

6. data[j] data[j-1]

7. j j-1

8. data[j] = index



9. I I+1

c. Buble sort

Algoritma :

1. i jumlah data-1

2.

Selama i > 0 kerjakan no 3 sampai no 73. j 1

4. Selama j <= i kerjakan no 5 sampai no 65. Jika data[j-1] > data[j] tukarkan data

6. j j+1

7. i i-1

d. Quick sort

Algoritma :

1. pivot data[[L+R]/2]

2. I L3. j R4. Selama <I <= j) kerjakan baris 5 sampai dengan 12

5. Selama (data[I] < pivot) kerjakan I I+1

6. Selama (data[j] > pivot) kerjakan I j-17. Jika (I<=j) maka kerjakan baris 8 sampai dengan 10 jika tidak kerjakan baris 11

8. Tukar data[I] dengan data[j]

9. I I+1

10. j j-111. Jika (L<j) kerjakan lagi baris 1 dengan R=j

12. Jika(I<R) kerjakan lagi baris 1 dengan L=i

6. Jelaskan dalam bentuk gambar dan tuliskan potongan program untuk proses

menyisipkan node pada posisi tertentu dari suatu linked list. Algoritmanya

adalah sebagai berikut:

uts_sd

Documents