Soal problem solving 1. Resep Rahasia

Sumber http://bebras.or.id/v3/pembahasan-soal/

1. Resep Rahasia

Deskripsi Soal
Keluarga Berang-berang sedang mempersiapkan acara Festival Makanan, dan mereka
ingin memanggang kue kering; Kati akan membuat kue. Dia sangat memperhatikan
urutan membuat kue dengan memasukkan bahan kue dengan urutan yang benar.
Ketika dia berjalan ke taman, dia melihat ada secarik kertas petunjuk pada setiap
bahan kue yang akan digunakan. Gambar pada kertas petunjuk menjelaskan bahan
kue yang harus ditambahkan pada urutan berikutnya. Hanya ada satu bahan kue
yang tidak memiliki kertas. Ilustrasi taman seperti di bawah ini:

Pertanyaan
Bahan kue manakah yang harus dimasukkan pertama kali?

Jawaban

Jawaban yang benar adalah B.

Penjelasan

Jika Kati memulai dari B maka dia akan menambahkan kelima bahan kue dengan
urutan yang benar. Bahan kue pertama yang harus ditambahkan adalah yang tidak
dirujuk oleh bahan lain.
Jika dia memulai dari stroberi, maka dia tidak dapat melanjutkan ke tahap berikutnya
karena tidak ada petunjuk bahan kue selanjutnya pada kertas. Jika dia memulai dari
apel maka salah, karena bahan kue bunga merah akan terlewatkan. Jika dia memulai
dari buah pohon cemara juga salah, karena bahan kue bunga merah dan apel akan
terlewatkan.

Ini Informatika!

Struktur data yang digunakan pada soal ini dikenal dengan linked list. Linked list
adalah kumpulan data yang tersusun secara linier yang memiliki sebuah nilai dan
pointer yang menunjukkan data berikutnya. Data pertama pada linked list sangat
penting sekali untuk diketahui karena data tersebut akan digunakan untuk memulai
penelusuran list.
Soal resep kue di atas adalah contoh penggunaan linked list. Bahan kue adalah data
(item) dan kertas adalah pointer yang menunjukkan bahan kue yang harus
ditambahkan berikutnya. Bahan kue pertama adalah bahan kue yang tidak dirujuk
oleh kertas bergambar yang lain, akan tetapi bahan kue tersebut memiliki kertas
penunjuk. Item ini hanya memiliki satu petunjuk ke bahan kue selanjutnya, dan tidak
memiliki petunjuk bahan kue sebelumnya.
Keuntungan menggunakan linked list adalah data yang disimpan dapat memiliki tipe
dan ukuran yang berbeda, seperti buah dan bunga pada soal ini.
Struktur data ini dapat juga berbentuk non-linier. Linked list dapat merujuk pada data
yang sama dari linked list yang berbeda dan juga dapat merujuk data lain pada linked
list yang berbeda.
Kata Kunci