Latihan Soal Algoritma dan Struktur Data

 

1. Seorang programmer yang baik harus mengetahui cara pembuatan program yang bagus. Berikan penjelasan tentang program yang bagus itu seperti apa!
Jawab :
Program yang bagus maupun baik adalah program yang mudah penggunaannya dan bisa memudahkan penggunanya untuk menyelesaikan masalah – masalah yang dihadapinya. Program dikatakan bagus, jika :
a. Terstruktur
b. Program berjalan secara benar
c. Program mudah dibaca dan dimengerti
d. Program mudah di Debug
e. Program mudah dimodifikasi

2. Struktur data merupakan suatu cara untuk menyimpan dan mengatur sebuah data supaya dapat digunakan secara efektif dan efisien. Sebutkan dan jelaskan jenis-jenis struktur data secara umum.
Jawab :

1.         Struktur Data Sederhana

a.    Array  (Larik)

Larik adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipe sama. Setiap elemen diakses langsung melalui indeksnya. Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter. Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi. Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur, atau tipe larik lain. Nama lain array adalah larik, tabel, atau vektor.

b.   Record  (Catatan)

ADT adalah definisi tipe dan sekumpulan primitif (operasi dasar) terhadap tipe tersebut. Tipe diterjemahkan menjadi tipe terdefinisi dalam bahasa pemrograman yang bersangkutan.

2.         Struktur Data Majemuk 

a.    Linier 

1.   Stack (Tumpukan)

Stack (tumpukan) adalah list linier yang dikenali elemen puncaknya (top), aturan penyisipan dan penghapusan elemennya tertentu (penyisipan selalu dilakukan “di atas” (top), penghapusan selalu dilakukan pada top). Karena aturan penyisipan dan penghapusan semacam itu, top adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan tersusun secara LIFO (Last In First Out). 

2.   Queue (Antrian)

Queue (antrian) adalah list linier yang dikenali elemen pertama (head) dan elemen terakhirnya (tail); Aturan penyisipan dan penghapusan elemennya disefinisikan sebagai penyisipan selalu dilakukan setelah elemen terakhir, penghapusan selalu dilakukan pada elemen pertama; Satu elemen dengan elemen lain dapat diakses melalui informasi next. 

3.   List dan Multi-List (Daftar)

List linier adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian. Sebuah list linier dikenali dengan (1) Elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut (first); (2) Alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah elemen, yang dapat diakses melalui field next; (3) Setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu. Untuk mengacu sebuah elemen, alamat harus terdefinisi. Dengan alamat tersebut informasi yang tersimpan pada elemen list dapat diakses; (4) Elemen terakhirnya. 

b.   Non-Linier 

1.   Binary Tree (Pohon Biner)

Sebuah pohon biner (binary tree) adalah himpunan terbatas yang mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai sub pohon kiri (left) dan sub pohon kanan (right) dari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting dari struktur data dan banyak dijumpai dalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwa setiap simpul paling banyak hanya memiliki dua buah anak, dan mungkin tidak punya anak. Istilah-istilah yang digunakan sama dengan istilah pada pohon secara umum. 

2.   Graph (Graf)

Graph merupakan struktur data yang paling umum. Jika struktur linier memungkinkan pendefinisian keterhubungan sekuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian.

3. Jelaskan beberapa aplikasi perangkat lunak komputer yang menggunakan struktur data sebagai dasar pengembangannya.
Jawab :

1. Antrian pada kasir pada sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setiap pelanggan dilayani, antrian yang berada didepan akan maju. Jika kita ada di antrian kedua, maka kita akan menunggu antrian pertama melakukan prosesnya. Ketika selesai proses dari antrian pertama dia akan pergi, dan giliran kita untuk maju untuk melakukan proses. Begitu juga arti dari antrian dalam bahasan kali ini, jika pengantri pertama datang maka dia juga yang akan keluar pertama kali atau FIFO(First In First Out) dan FCFS (First Come First Serve). 
2. Pembelian tiket kereta api, tiket pesawat, tiket kapal laut, pembayaran tiket tol, pembayaran listrik, pembayaran air, dan lain sebagainya. Saat mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakaiseseorang masuk dalam sebuah antrian adalah DeQueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah deQueue. 
3. Antrian Mobil di pintu Tol. Ketika sebuah mobil datang, dari belakang akan menuju kedepandari antrian. Setelah mobil mendapatkan karcis tol, antrian yang berada didepan akan maju. Pada saat menempatkan data pada ujung (tail) dari queue disebut dengan Enqueue. Pada saat memindahkan data dari kepala(head) sebuah queue disebut dengan dequeue. 

 4. Abstract Data Type (ADT) merupakan cara untuk melihat struktur data, dengan fokus pada apa yang dilakukan dan mengabaikan proses yang terdapat didalamnya saat menjalankan eksekusi. Buatlah algoritma yang menganalogikan abstraksi perangkat elektronik. 
Jawab :

Program Tiket_Di_Bioskop

Algoritma:

          type tiketBioskop: < nama_film : string,

                                                         kode_film : string,

                                                         jadwal_film : string,

                                                         harga_tiket : string,

                                                         quota : integer >

          T : array [1..4] of tiketBioskop

          type datapembeli: < nama_pembeli : string,

                                                         kode_pembelian : string >

          D : array [1..9999] datapembeli

          jumlah_pembeli : integer

          pilihan : integer;

          procedure lihatBioskop()

          procedure beliTiket()

          function  buatKodePembelian( T : tiketBioskop) -> string

5. Berikan penjelasan dan bandingkan beberapa pendekatan yang dapat digunakan untuk merancang sebuah algoritma.
Jawab :
Terdapat dua pendekatan secara umum yang bisa digunakan dalam merancang algoritma, yakni pendekatan secara Top-Down, dan pendekatan secara Bottom-up.
1. Top-Down
Pendekatan perancangan secara top-down dimulai dengan cara membagi algoritma yang kompleks menjadi satu atau lebih dari satu modul. Modul yang terbagi ini masih bisa diuraikan lagi menjadi beberapa sub-modal, dan proses ini dilakukan berulang-ulang hingga kompleksitas modul yang diinginkan terpenuhi. Metode perancangan top-down merupakan bentuk perbaikan secara bertahap yang dimulai dengan modul paling atas kemudian secara bertahap menambah modul lain yang dipanggil.
2. Bottom-up
Pendekatan perancangan bottom-up merupakan kebalikan dari pendekatan top-down. Dimana dalam pendekatan ini dimulai dengan pembuatan modul paling dasar, kemudian dilanjutkan ke perancangan modul tingkat yang lebih tinggi. Modul yang memiliki tinggkat lebih tinggi diimplementasikan menggunakan operasi yang dilakukan ikeh modul tingkat lebih rendah. Dengan demikian sub-modul pada pendekatan ini dikelompokkan secara bersama untuk membentuk tingkat modul yang lebih tinggi. Semua modul tingkat yang lebih tinggi  dikumpulkan bersama-sama untuk membentuk modul tingkat yang lebih tinggi. Proses ini diulang hingga desain algoritma yang lengkap terpenuhi.

6. Sebuah program dapat memiliki lebih satu algoritma. Rancang algoritma untuk program kalkulator yang dapat melakukan operasi penjumlahan dan pengurangan.
Jawab :
   x,y       : integer
   hasil     : real
operator        : char
begin
Input(x)
Input(operator)
Input(y)
if operator = ‘+’ {jika operator adalah +}
then
hasil ← x+y
else
if operator = ‘-‘ {jika operator adalah -}
then
hasil ← x-y
endif
endif
{menampilkan penginputan oleh user}
Output(x,operator,y)
{menampilkan hasil penghitungan}
Output(hasil)

7. Ukurlah kompleksitas algoritma yang Anda rancang menggunakan notasi Big O!
Jawab :

            input : x, y dan operator

            if  operator = ‘+’  then

               hasil ← x+y

            else

              operator = ‘-‘ then

              hasil ← x-y

            endif

            //output : nilai hasilⁿ

endfunction

REFERENSI :

1. Wantoro, jan dan Sukirman 2017. Algoritma & Struktur Data Dalam Bahasa C++. Surakarta:MUP
2. https://www.dictio.id/t/bagaimana-cara-membuat-program-yang-baik/12809/2 
3. http://www.academia.edu/26340400/MAKALAH_STRUKTUR_DATA_Aplikasi_Struktur_Data_Queue_Semester_2
4. https://bayubayyz.blogspot.co.id/2014/03/program-kalkulator-sederhana.html 
5. http://danangdprasetyo.blogspot.co.id/2013/02/contoh-algoritma-adt-tugas-kelompok.html