Kisi-Kisi Ujian Akhir Semester 2015.2 Algoritma dan Pemrograman Lanjut
A. Materi Ujian Tengah Semester 1. Array Array adalah
kumpulan
data
yang bertipe
sama yang
menggunakan
menggunakan array, sejumlah variabel dapat memakai nama yang sama. Antara variabel
lain
di
dalam
array
nama yang sama. Dengan satu
variabel
dengan
dibedakan berdasarkan nomor elemen (subscript/indeks) Variabel dapat
dideklarasikan ber-type array dari suatu type tertentu. Setiap elemen array diakses dengan alamat berupa indeks yang bertype integer. Contoh : int TabInt[10]; Array bernama TabInt Setiap elemen bertype integer, Dengan ukuran 10 elemen, Dengan alamat setiap elemen array (indeks) adalah dari indeks ke-0 s.d. 9. a. Deklarasi Array int main() { // Kamus int TabJumlahHari[12]; float TabNilai[15]; char TabHuruf[100]; string TabKata[100]; Point TabTitik[20]; // Algoritma …..
// indeks 0..11 // indeks // indeks // indeks // indeks
0..14 0..99 0..99 0..19
Elemen dari array dapat diakses langsung jika dan hanya jika indeks terdefinisi Cara mengacu sebuah elemen : TabInt[2] TabInt[i] jika i terdefinisi b. Mengisi Array Mengisi array merupakan aktifitas memberi nilai elemen array Pemberian nilai satu elemen Contoh : TabInt[0]=31; Pemberian nilai beberapa elemen
Contoh : for (i=0;i<10;i++) { TabInt[i]=i*10; }
Page 1
c. Mengisi Dan Membaca Isi Array Elemen array yang telah diberi nilai dapat diakses kembali. Contoh : menampilkan semua isi array ke layar #include
using namespace std; int main () { // Kamus int TabInt[10]; int i; // Algoritma mengisi array for (i=0; i<10; i++) { TabInt[i]=i*10; } // Algoritma membaca dan menuliskan // isi array ke layar for (i=0; i<10; i++) { cout << TabInt[i] << endl; } return 0;
2. Algoritma Sorting a.
Penyisipan langsung (straight insertion sort) Algoritma :
Cara mengurutkannya adalah dicek satu persatu mulai dari yang kedua sampai dengan yang terakhir.
Apabila ditemukan data yang lebih kecil dari data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Subrutin Insertion Sort void insertion_sort(int arr[], int length) { int i, j ,tmp; for (i = 1; i < length; i++) { j = i; while (j > 0 && arr[j - 1] > arr[j]) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; j--; } //end of while loop print_array(arr,5); } //end of for loop
Page 2
b. Seleksi (selection sort) Algoritma :
Cara mengurutkannya adalah dengan membandingkan elemen sekarang dengan elemen yang berikutnya sampai terkahir.
Jika ditemukan elemen paling kecil, kemudian ditukar dengan elemen sekarang. Subrutin Selection Sort void selectSort(int arr[], int n) { int pos_min,temp; for (int i=0; i < n-1; i++) { pos_min = i; for (int j=i+1; j < n; j++) { if (arr[j] < arr[pos_min]) pos_min=j; } if (pos_min != i) { temp = arr[i]; arr[i] = arr[pos_min]; arr[pos_min] = temp; } } }
c.
Gelembung (buble sort) Algoritma :
Cara mengurutkannya adalah membandingkan elemen yang sekarang dengan elemen yang berikutnya.
Jika elemen sekarang> elemen berikutnya, maka tukar Subrutin Buble Sort void bubble_sort(int arr[], int size){ bool not_sorted = true; int j=0,tmp; while (not_sorted){ not_sorted = false; j++; for (int i = 0; i < size - j; i++){ if (arr[i] > arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; not_sorted = true; }//end of if print_array(arr,5); } //end of for loop } //end of while loop } //end of bubble_sort
Page 3
3. Algoritma Searching a. Pencarian Sekuensial (Linier) Pencarian Sekuensial (Linier) merupakan model pencarian yang paling sederhana yang dilakukan terhadap kumpulan data Algoritma :
Terdapat sebuah larik yang berisi n buah data ( L[0], L[1], … , L[n-1])
k adalah data yang dicari L[i]=k
i adalah bilangan indeks terkecil , yang memenuhi kondisi 0 ≤ k ≤ n-1
k adalah data yang dicari L[i]=k
Berikut ini merupakan implementasi algoritma pencarian secara sekuensial. Subrutin akan menghasilkan nilai balik berupa :
-1 jika data yang dicari tidak ditemukan dan
Bilangan antara 0 sampai dengan n-1 (dengan n adalah jumlah elemen larik) jika data yang dicari ditemukan
b. Pencarian Terhadap Data Terurut (Binary) Apabila kumpulan data sudah dalam keadaan terurut, pencarian data dengan menggunakan pencarian sekuensial akan memakan waktu yang lama jika jumlah data dalam kumpulan data tersebut sangat banyak. Untuk mengatasi hal tersebut terdapat algoritma yang dirancang agar pencarian lebih efesien yaitu pencarian biner (Binary Search) . Algoritma :
Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama atau berbeda 1 jika jumlah data semula ganjil
Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama Dalam hal ini akan terjadi 3 kemungkinan yang terjadi :
Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan.
Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
Data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.
4. Structure and Pointer a. Structure Structure adalah kumpulan data yang saling berhubungan, yang disimpan dalam satu unit penyimpanan. Misalkan pada suatu database peyimpanan data pegawai, dimana setiap pegawai akan menyimpan nama, alamat dan gaji. Bila menggunakan array biasa, maka diperlukan tiga variable yang bebas satu dengan yang lain, yaitu variabel nama, alamat dan gaji. Dengan menggunakan structure, data tersebut diorganisasikan dalam satu kesatuan.
Page 4
Gambar 1. Perbedaan Array dan Structure b.1. Deklarasi Dan Menginisialisai Structure Biodata pegawai mempunyai properties nama, alamat, dan gaji. Bila menggunakan array biasa, maka diperlukan tiga variable yang bebas satu dengan yang lain, yaitu variabel nama, alamat dan gaji dengan deklarasi sebagai berikut. int main() { // Kamus string TabNama[10]; string TabAlamat[10]; int TabGaji[10]; // Algoritma
// indeks 0..9 // indeks 0..9 // indeks 0..9
Dengan menggunakan structure, data tersebut diorganisasikan dalam satu kesatuan struct data //Deklarasi structure { char name[20]; char address[20]; int salary; }; data employee1; //Inisialisasi variabel structure b.2. Memanggil Elemen Tertentu Dari Suatu Structure int main() { cout << "Employee's name : "; cin >> employee1.name; cout << "Employee's address : "; cin >> employee1.address; cout << "Employee's salary : "; cin >> employee1.salary; cout cout cout cout
<< << << <<
endl << "Employee's data : "; employee1.name << ", "; employee1.address << ", "; employee1.salary;
return 0; }
Page 5
Memanggil elemen name pada structure employee1(Inisialisasi variabel structure Data)
b. Pointer Pointer adalah built-in type di C dan C++, dimana C++ mengambil konsep pointer dari C. Sebenarnya sangat terkait dengan "Abstract C Machine", yaitu model mesin abstrak dimana program C bekerja. Abstract C Machine adalah mesin abstrak dimana mesin tersebut memiliki prosesor untuk menginterpretasikan stream of instruction, dan addressable memory b.1. Operator Pointer
& Operator menghasilkan alamat dari operand-nya. Operator & merupakan operator alamat. Pada saat pendeklarasian variable, user tidak diharuskan menentukan lokasi sesungguhnya pada memory, hal ini akan dilakukan secara otomatis oleh kompiler dan operating sysem pada saat run-time. Jika ingin mengetahui dimana suatu variable akan disimpan, dapat dilakukan dengan memberikan tanda ampersand (&) didepan variable , yang berarti "address of". Contoh : ted = &andy;
* Menghasilkan nilai yang berbeda pada sebuah alamat. Operator * merupakan operator reference. Dengan menggunakan pointer, kita dapat mengakses nilai yang tersimpan secara langsung dengan memberikan awalan operator asterisk (*) pada identifier pointer, yang berarti "value pointed by". Contoh : beth = *ted; (dapat dikatakan:"beth sama dengan nilai yang ditunjuk oleh ted") beth = 25, karena ted dialamat 1776, dan nilai yang berada pada alamat 1776 adalah 25. b.2. Pointer Bertipe Void Pada C++ terdapat pointer yang dapat menunjuk ke tipe data apapun, pointer semacam ini dideklarasikan dengan tipe void sehingga sering dikenal dengan istilah Void Pointer. Listing Program Pointer
void *p; int a=10; double b=23.4; char c='s'; p=&a; //p menunjuk ke tipe data int cout<<"alamat (a=10) = "<
