TUGAS 14 (GRAF)

1.   Jelaskan pegertian Graf !

Jawab :

Graph digunakan untuk merepresentasikan objek-objek diskrit  dan hubungan antara objek-objek tersebut.

2.   Sebutkan 5 contoh terminologi Graf dan jelaskan !

Jawab :

a)   Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

b)   Simpul Terpencil (Isolated Vertex)

Simpul yang tidak mempunyai sisi yang bersisian dengannya.

c)    Graf  Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (N_n).

d)   Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

e)   Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan.  

3.   Jelaskan pengertian dari beberapa Graf khusus

Jawab :

v Graf Lengkap (Complete Graph)

Graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

v Graf Lingkaran

Graf sederhana yang setiap simpulnya berderajat 2.

v Graf Teratur (Regular Graphs)

Graf yang simpulnya mempunyai derajat yang sama.

v Graf Bipartite (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi 2 himpunan bagian V₁  dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul tersebut.

4.   Representasi Graf memiliki 3 unsur. Buatlah 1 contoh dari masing-masing unsur tersebut !

Jawab :

a)   Matriks Ketetanggaan (adjacency matrix)

Matriks Bersisian (incidency matrix

)

b)   Senarai Ketetanggaan (adjacency list)

5.   Gambarkan 2 buah graf yang isomorfik dengan graf teratur berderajat 3 yang mempunyai 8 buah  simpul !

Jawab :

TUGAS 13 (TREE)

1.   Apa pegertian tree

Jawab :

Kumpulan kode yang saling terhubung satu sama laindalam suatu  kesatuan yang membentuk layakya struktur sebuah pohon.

2.   Jelaskan pegertian Binary Tree

Jawab :

merupakan salah satu bentuk struktur data tidak linear yang menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.

3.   Buatlah program tree

Jawab :

4.    sebutkan Jenis-jenis Binary Tree dan pegertian nya

Jawab :

     Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

     Complete Binary Tree

 Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

     Skewed Binary Tree

Akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child

5.    sebutkan Langkah-Langkahnya Traverse

Jawab :

¨       PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

¨       InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

¨       PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

TUGAS 12 (STUKTUR DATA PROGRAM)

1.   Buatlah satu contoh tentang insertion sort

Jawab :

      

2.   Apa perbedaan exchange sort dan bubble sort

Jawab :

dalam hal bagaimana membandingkan antar elemen-elemennya :

•         Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.  Jadi ada elemen yang selalu menjadi elemen pusat (pivot).

•         Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya

3.   buatlah lima contoh tentang metode pengurutan data

Jawab :

1)   Pengurutan berdasarkan perbandingan (comparison-based sorting)

•         Bubble sort, exchange sort

2)   Pengurutan berdasarkan prioritas (priority queue sorting method)

•         Selection sort, heap sort (menggunakan tree)

3)   Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

•         Insertion sort, tree sort

4)   Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

•         Quick sort, merge sort

5)   Pengurutan berkurang menurun (diminishing increment sort method)

•         Shell sort (pengembangan insertion)

4.   Apa yang dimaksud dengan pengurutan (sorting)

Jawab :

adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

5.   Buatlah contoh program selection sort

Jawab :

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <iomanip.h>

main()

{

int x[5];

int i;

int temp;

int minindex;

int j;

clrscr();

cout<<" >> Welcome To The Program Selection Sort << \n" <<endl;

cout<<"masukkan nilai x :\n";

for(i=0; i<5; i++)

{

cout<<"x["<<i<<"] = ";cin>>x[i];

}

cout<<"\n data sebelum di sort :";

for(i=0; i<5;i++)

{

cout<<setw(4)<<x[i];

}

for(i=0; i<5-1; i++) //perulangan iterasi

{

minindex=i;

for(j=i+1; j<5; j++) //perulangan membandingkan data

{

if(x[minindex]>x[j])

{

minindex=j;

}

}

temp=x[i];

x[i]=x[minindex];

x[minindex]=temp;

}

cout<<"\n\nData setelah di sort :";

for(i=0; i<5; i++)

{

cout<<setw(4)<<x[i];

}

                           

getch();

}

TUGAS 11 (SHORTING)

1.   Apa yg dimaksud dengan Sorting dan searching ?

Jawab :

searching merupakan salah satu operasi dasar dalam ilmu komputer. Sorting merupakan suatu proses (operasi) yang mengurutkan data dalam suatu urutan yang diberikan (increasing atau decreasing). Searching merupakan suatu proses (operasi) untuk mencari lokasi dari data yang diberikan dalam suatu urutan data.

2.   Jelaskan pengertian dari Bubble Sort ?

Jawab :

Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen struktur data yang semestinya berada pada posisi awal.

3.   Apa yang dimaksud dengan Selection Sort ?

Jawab :

sort yang melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data.

4.   Jelaskan pengertian dari insertion sort , merge sort ,Quick sort ?

Jawab :

í Insertion sort

adalah metode dengan cara menyisipkan elemen larik pada posisi yang tepat.Cara kerja insertion sort, Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan.  Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting. 

í Merge sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma  algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu.

í Quick sort

adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.

5.   Sebutkan  lima algoritma sorting yang  populer  dipakai didunia informatika?

Jawab :

í Bubble Sort

í Selection Sort

í Insertion Sort

í Merge Sort, dan

í Quick Sort.

TUGAS 10 (PENERAPAN TEKNIK SEARCH)

1.   Apa yang dimaksud dengan sequential search?

Jawab :

Adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

2.   Sebutkan kelebihan dan kekurangan dari sequential search?

Jawab :

§  Kelebihan dari teknik pencarian ini adalah jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat.

§  Kekurangannya adalah jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya. Dan apabila jumlah datanya banyak, tentu juga akan membutuh waktu yang lama dan beban yang besar pula.

3.   Jelaskan apa yang dimaksud dengan best case dan worst case?

Jawab :

§  Best case : jika data yang dicari terletak di depan sehingga waktu yang dibutuhkan minimal.

§  Worst case : jika data yang dicari terletak di akhir sehingga waktu yang dibutuhkan maksimal.

4.   Buatlah algoritma dari sequential search?

Jawab :

Algoritma Sequential Search

i ← 0

ketemu ←false

Selama (tidak ketemu) dan (i < N) kerjakan baris 4

Jika (Data[i] = key) maka

ketemu ←true

jika tidak

i ←i+1

Jika (ketemu) maka

i adalah indeks dari data yang dicari

jika tidak

data tidak ditemukan

5.   Buatlah program dari sequential search?

Jawab :

#include <iostream.h>

#include <conio.h>

int i;

void main()

{

    int A[100]  ;

    int cari,ketemu;

   cout<<"masukkan 7 buah data : \n\n";

   cout<<"PROGRAM SEARCHING\n";

   for (i=1;i<=7;i++)

     cin>>A[i] ;

   {

     cout<<"masukkan data ke-"<<i<<endl;

   }