Contoh soal Tree

Tree 1





Tree 2






Tree 3

1. Tentukan root masing masing tree
2. tentukan leaf masing masing tree
3. rubahlah menjadi binary tree
4. tentukan Height dan Width
5. dari ke 3 tree tersebut rubahlah menjadi binary tree
6. dari soal diatas bentuklah 3 aktifitas dalam binary tree

• Pre order
• In order
• Post order

jawaban


1. tree 1 = A, tree 2 = 1, tree 3 =A1


2.tree 1 = (W,P,R,S,Z,H,I,J,U,V,X,L,Y,N,O)
   tree 2 = (3,4,7,8,9,10)
   tree 3 = (A4,A5,A6)


3. Tree1






Tree2












Tree3







4. Tree 1 Height = 6
                 Widht = 15


Tree 2 Height = 5
             Width = 6


Tree 3 Height = 4
             Width = 3






5.










6. Tree 1 

Graph

Graf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual darigraph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc

Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.

• Graph tak berarah (undirected graph atau non-directed graph) :
• Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA
• Graph berarah (directed graph) :
• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.
• Graph Berbobot (Weighted Graph)
• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Istilah-istilah dalam graf
Kemudian terdapat istilah-istilah yang berkaitan dengan graphyaitu:

a. Vertex
Adalah himpunan node / titik pada sebuah graph.
b. Edge
Adalah himpunan garis yang menghubungkan tiap node / vertex.
c. Adjacent
Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3tidak insident dengan titik v1 dan titik v4.

Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidakadjacent dengan titik v4.
-------------------------------------------------
Istilah-istilah dalam graf
Kemudian terdapat istilah-istilah yang berkaitan dengan graphyaitu:

Pertemuan 4


Notasi INFIX, PREFIX, POSTFIX



1.Notasi Infix
Contoh : X + Y

Pertemuan 3

Queue (Antrian)

Implementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array.







Definisi
Queue adalah suatu linear list dimana operasi DELETE terjadi pada sisi depan (FRONT) dan Operasi INSERT terjadi pada sisi belakang (REAR).


Jika diberikan suatu Queue Q dengan elemen-elemennya yang terdiri atas Q1, Q 2 , ......., Qt maka Queue Q dituliskan
Q = [Q1, Q 2 , ......., Qt ]


FRONT (Q) = Q1
REAR (Q) = Qt


Selanjutnya untuk menyatakan jumlah eleen dalam suatu Queue Q digunakan notasi NOEL (Q).
Ø Catatan : Satu pengoperasian berlaku hanya untuk satu elemen.


CONT.
- Pada Queue prinsip yang digunakan adalah “Masuk Pertaa Keluar Pertama” atau FIFO (First In First Out).
- Data-data didalam antrian dapat bertipe integer, real, record.


Operasi – operasi pada Queue (Q) :
Terdapat 4 operasi pada Queue :


- CREATE
Bentuk umum : CREATE (Queue) Suatu operasi CREAT (Q) akan menghasilkan suatu Queue kosong dengan nama Q, dan didefinisikan bahwa :
NOEL (CREATE (Q)) = 0
FRONT (CREATE (Q)) = tidak terdefinisi
REAR (CREATE (Q)) = tidak terdefinisi


- ISEMPTY
Bentuk umumnya adalah : INEMPTY (Queue)
Jika Q adalah Queue, maka ISEMPTY (Q) adalah suatu operasi yang digunakan untuk memerikasa apakah Queue Q adalah Queue kosong. Jika hasil dari operasi ini akan berjenis data boolean (true/false), dengan bentuk sebagai berikut :
ISEMPTY(Q) = True, jika Q adalah Queue kosong
= False, jika Q bukan Queue kosong


- INSERT
Bentuk umumnya : INSERT (Elemen, Queue)
INSERT (E,Q), dimana E = elemen dan Q = Queue, adalah suatu operasi yang digunakan untuk memasukkan elemen E ke dalam Queue Q.
Didefinisiskan, bahwa elemen E akan menjadi elemen yang berada pada posisi REAR dan Queue Q. Akibat dari operasi ini adalah :

Array & Record
Pertemuan 2

Array

Aray juga dapat dikatakan suatu himpunan terurut dengan elemen-elemen homogen. Adalah tipe terstruktur yang terdiri dari sejumlah komponen-komponen yang mempunyai tipe data yang sama. Suatu Array mempunyai jumlah komponen yang banyaknya tetap. Banyaknya komponen dalam suatu larik ditunjukkan oleh suatu indek untuk membedakan variabel yang satu dengan variable yang lainnya.


Array dapat dikelompokkan:

1.Array 1 Dimensi
Bentuk Array yang paling sederhana adalah Array 1 Dimensi
-Array ini dapat dianggap sebagai sebuah vektor, yang tersusun dalam bentuk kolom atau baris saja.
-Suatu Array A berdimensi satu dengan N buah elemen, secara fisik dapat digambarkan sebagai berikut:






Yang perlu diketahui disini adalah letak elemen ke I dari Array A(1,N), atau letak masing-masing elemen Array pada storage.

Indeks dan elemen suatu Array menyatakan posisinya dalam urutan secara umum suatu Array A berdimensi satu dengan elemen berjenis data I yang mempunyai Indeks.

2.Array Multi Dimensi
Adalah salah satu contoh array jenis multi dimensi (dimensi banyak).
- Tersusun dalam bentuk baris dan kolom, dimana indeks pertama menunjukkan baris dan indeks kedua menunjukkan kolom.
- Array ini elemen-elemennya merupakan Array pula.
- Bentuk yang danggap dapat mewakili dimensi ini :
Array ditulis :
Array ditulis = B(1:M, 1:N) = {B(I,J)},
Untuk I = 1, 2, ..., M
J = 1,2, ..., N
- Jumlah elemen (range) dari Array B ini adalah M X N
- Secara umum, Array 2 Dimensi B dengan batas bawah indeks pertama L1, batas atas pertama U1, batas bawah Indeks kedua L2, batas atas kedua U2 :
B = (L1: U1, L2:U2) = {B(1,J)}
Untuk L1 < 1< U1 dan L2 < J < U2

- Jumlah elemen baris dari Array B : (U2-L2 + 1)
- Jumlah elemen kolom dari Array B : (U1 – L1 + 1)
- Jumlah total Array B : (U2-L2 + 1)(U1-L1+1)

Cross Section
- Cross Section dari Array 2 dimensi :
Suatu himpunan yang anggotanya adalah elemen-elemen dalam satu baris saja.
- Notasinya menggunakan *
- Misal diberikan Array B (1 : M, 1:N)
B (4,*) = {B(4,1), B (4,2), ..., B (4,N)}
B (*,4) = { B(1,4), B(2,4), ..., B(M,4)}

Tranpose
Tranpose 2 Dimensi : Suatu Array 2 Dimensi pula dengan menukar posisi Indeksnya.
- Tranpose dari Array berukuran M X N adalah suatu Array berukuran N X M
- Tranpose dari suatu Array dari b dinotasikan dengan BT







Semua Karyawan desain pegawai Tetap = Percetakan (*, A, 1 )
Karyawan pria bagian produksi = Percetakan (P, C, *)


Deklarasi Array dalam Bahasa Pemrograman
- Misalkan ada Array nama R dengan 10 elemen dengan masing-masing elemen berjenis data integer, maka deklarasinya dalam bahasa pemrograman adalah sbb:
Var R : Array [1..10] Of Integer;
- Dalam mendeklarasikan suatu Array ada 3 hal :
~ Nama Array
~ Range dari Indeks
~ Tipe elemen-elemen datanya


Pemetaan Aray 1 Dimensi ke Storage


Starting Adress elemen ke 1 dari array, dinyatakan dengan B, disebut juga base-location. Misalkan bahwa masing-masing elemen dari array menduduki S byte. Maka Starting address dari elemen ke I adalah :
Array A (1:N) adalah = B + (i - 1)*S


Pemetaan Array Multi Dimensi ke Storage
- Prinsip yang digunakan disini tetap didasarkan pada Array satu dimensi
Linearisasi menurut Baris :
Record
Himpunan dari elemen-elemen yang heterogen. Adalah komponen-komponen yang mempunyai tipe data yang berbeda.


Beberapa hal yang perlu diketahui dalam record sbb:
- Elementary Item : suatu field (bidang) yang tidak mempunyai sub field
- Group Item : Suatu field yang memiliki subfield
- Tupel : Gabungan atribut yang mempunyai field


File
- Record-record yang tipenya sama
- Untuk menyatakan suatu data dalam dalam record yang mempunyai identifikasi yang khusus, maka harus mempunyai 1 field khusus yang disebut Key (Kunci Field).

Struktur Data


Pertemuan 1


Tipe data dikategorikan menjadi 2 yaitu :

Tipe data tunggal (data primitif) : Integer, Real, Boolean dan karakter

Tipe data majemuk (data campuran) : string (untai)

Tipe Data dalam pemprograman ada 3 yaitu :

1. Sederhana :

Ordinal : Integer, Boolean, char,Real




2. Terstrukur : Array, Record, Set, File

3. Pointer


TIPE DATA TUNGGAL


Integer

- Suatu integer adalah anggota dari himpunan bilangan.

- Operasi – operasi dasar yang ada dalam integer adalah : penjumlahan, pengurangan, perkalian, pembagian dan sebagainya.

- Operator yang bekerja terhadap sepasang integar (operand) disebut sebagai Binary Operator.

- Operator yang hanya bekerja pada satu operand saja disebut sebagai Unary Operator.

- Contoh Unary Operator adalah operator negasi. Berfungsi untuk mengubah tanda suatu operand.







Real

- Data Numerik yang bukan termasuk integer, digolongkan dalam jenis data real.

- Jenis data ini ditulis menggunakan titik desimal.

- Bilangan real dimasukkan ke dalam memori komputer memakai sistem Floating Point, merupakan versi yang disebut Scientific Notation.

- Penyajian terdiri atas 2 bagian, yaitu : Mantissa (Pecahan) dan Eksponen.

Contoh :bilangan 199000 = 0,199 * 106

Disini 0,199 adalah mantissa (pecahan) sedangkan 6 adalah eksponen

Secara Umum suatu bilangan real X dituliskan M * RE






Boolean



Jenis data ini disebut juga jenis data logical
Elemen dari jenis data ini mempunyai nilai salah satu dari true atau false
Operator yang dikenal adalah: Operator logika yaitu NOT, AND dan OR


- Operator OR akan menghasilkan nilai true jika salah satu/ kedua operand bernilai true

- Operator AND akan menghasilkan nilai true jika kedua operand benilai true

- Operator NOT akan menghasilkan nilai true jika operand bernilai false dan sebaliknya

- Operator NOT merupakan precedence dari operator AND dan OR

- Dalam suatu ekspresi yang tidak menggunakan tanda kurung, operator NOT harus dievaluasi sebelum operator AND dan OR


Operator Relasional yaitu > , <, <= , >=, <> dan =







Karakter

Jenis data karakter merupakan elemen dari suatu himpunan simbol aksara yang terdiri atas bilangan, abjad, dan simbol – simbol khusus.

String


Jenis data string merupakan jenis data campuran karena elemen dibentuk dari karakter – karakter
String adalah barisan hingga simbol yang diambil dari himpunan karakter
Ada beberapa string yang dapat di bentuk, antara lain : CDI, CDD, DDC, CDC, CDCI, termasuk juga “ null string “ , “ empty string “.
Vocabulary, himpunan yang anggotanya adalah semua string yang dapat di bentuk dari suatu himpunan alphabet.
Bitstring, suatu string yang terbentuk dari alphabet.


Dalam suatu string terdapat beberapa operasi utama yaitu :

- Lenght : Menghitung panjang string (Integer)

Panjang dari string di definisikan sebagai banyak karakter dan dapat diltulis S=N atau Lenght (S)=N

Contoh : BUNGA = 7

- Concatenation : menggabungkan

- Operasi ini bekerja terhadap dua string dan hasilnya merupakan resultan dari kedua string tersebut

- Jika S1 dan S2 masing – masing adalah suatu string, maka bentuk operasi concatenation dinotasikan dengan CONCAT “(S1,S2)

Contoh : S1 : BUNGA

S2 : MELATI Concat (S1 ,S2)= BUNGAMELATI

- Sub String = Mengambil

Operasi ini adalah operasi membentuk string baru, yang merupakan bagian dari string yang diketahui

Notasinya adalah SUBSTR (s,i,j)

s = string yang diketahui

i dan j adalah int

i = posisi awal substring 0 ≤ i ≤ length (S)

j = banyak karakter yang diambil 0 ≤ j ≤ length (S) dan

0 ≤ i+j-1≤ lenght (S)






Contoh :

S : Kucing

i : Posisi

j : Banyak

Substr (S, 3, 4) cing

-Insert = Menyisihkan

·Operasi ini adalah untuk menyisipkan suatu string ke dalam string lain

·Bentuk umum adalah : INSERT (S1, S2, i )

·S1 dan S2 masing – masing adalah suatu string dan i adalah posisi awal S2 pada S1

·Misalkan S1 = ‘a1a2 ....an’

S2 = ‘b1b2....bm’

INSERT (S1, S2, 3)= ‘a1a2b1b2 ....bma3a4 ....an’

Contoh : S1 = Bunga

S2 = Mawar

INSERT (S1, S2, 3) = BuMawarnga

- Delete = Menghapus

·Operasi ini digunakan untuk menghapuskan sebagaian karakter dalam suatu string

·Bentuk umum adalah DELETE (s, i, j)

·Maksudnya adalah menghapuskan sebagaian karakter dalam string S, mulai dari posisi i dan panjang j

Contoh :

S : Kucing Delete : (S,2,4) = ucin