Latihan Soal OSN Ilmu Komputer SMA 2026

Materi Kelas 10 – 12 | 50 Soal | Pilihan Ganda, Isian Singkat, dan Uraian

Bagian A – Pilihan Ganda

Pilihlah satu jawaban yang paling tepat.

1. Bilangan biner 11011010 jika dikonversi ke bilangan desimal adalah …

• A. 196
• B. 202
• C. 218
• D. 224

2. Bilangan desimal 175 jika dikonversi ke bilangan heksadesimal adalah …

• A. A9
• B. AF
• C. B0
• D. BF

3. Operasi XOR antara 1010 dan 1100 menghasilkan …

• A. 0110
• B. 0111
• C. 1000
• D. 1110

4. Representasi bilangan -37 dalam sistem komplemen dua (two’s complement) 8-bit adalah …

• A. 10100101
• B. 11011011
• C. 10111101
• D. 11000101

5. Kompleksitas waktu algoritma pencarian biner (binary search) pada larik terurut berukuran n adalah …

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

6. Algoritma pengurutan yang membagi larik menjadi dua bagian, mengurutkan masing-masing secara rekursif, kemudian menggabungkannya disebut …

• A. bubble sort
• B. insertion sort
• C. merge sort
• D. selection sort

7. Kompleksitas waktu rata-rata algoritma quick sort adalah …

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(2^n)

8. Struktur data yang mengikuti prinsip LIFO (Last In First Out) adalah …

• A. antrian (queue)
• B. tumpukan (stack)
• C. pohon biner (binary tree)
• D. graf (graph)

9. Pada struktur data antrian (queue), operasi untuk menambahkan elemen ke belakang antrian disebut …

• A. pop
• B. push
• C. enqueue
• D. dequeue

10. Pohon biner dengan n simpul memiliki ketinggian minimum sebesar …

• A. n – 1
• B. log2(n)
• C. akar(n)
• D. n/2

11. Traversal pohon biner dengan urutan: kunjungi simpul kiri, kunjungi akar, kunjungi simpul kanan disebut traversal …

• A. preorder
• B. inorder
• C. postorder
• D. levelorder

12. Perhatikan pseudocode berikut:

function f(n):
    if n <= 1: return n
    return f(n-1) + f(n-2)

Fungsi di atas menghitung …

• A. faktorial n
• B. bilangan Fibonacci ke-n
• C. pangkat dua dari n
• D. jumlah 1 hingga n

13. Algoritma greedy memilih keputusan yang …

• A. mempertimbangkan semua kemungkinan solusi
• B. paling optimal secara lokal pada setiap langkah tanpa mempertimbangkan konsekuensi jangka panjang
• C. selalu menghasilkan solusi optimal global
• D. membagi masalah menjadi submasalah yang tumpang tindih

14. Paradigma pemrograman dinamis (dynamic programming) menyelesaikan masalah dengan cara …

• A. membagi masalah menjadi submasalah independen secara rekursif
• B. menyimpan hasil submasalah yang sudah dihitung (memoization) untuk menghindari perhitungan ulang
• C. mencoba semua kemungkinan solusi secara sistematis
• D. memilih solusi terbaik secara lokal di setiap langkah

15. Graf berarah (directed graph) berbeda dari graf tak berarah (undirected graph) karena …

• A. graf berarah tidak dapat memiliki siklus
• B. setiap sisi (edge) pada graf berarah memiliki arah dari satu simpul ke simpul lain
• C. graf berarah harus memiliki tepat satu komponen terhubung
• D. graf berarah tidak dapat direpresentasikan dengan matriks ketetanggaan

16. Algoritma Dijkstra digunakan untuk menemukan …

• A. pohon merentang minimum (minimum spanning tree)
• B. jalur terpendek dari satu simpul sumber ke semua simpul lain dalam graf berbobot non-negatif
• C. komponen terhubung dalam graf tak berarah
• D. urutan topologis simpul-simpul dalam graf berarah asiklik

17. Algoritma Breadth First Search (BFS) menggunakan struktur data … dalam implementasinya.

• A. stack
• B. priority queue
• C. queue
• D. pohon biner

18. Notasi O-besar (Big-O notation) O(n^2) menggambarkan …

• A. algoritma yang selalu berjalan dalam waktu konstan
• B. pertumbuhan waktu eksekusi yang berbanding lurus dengan kuadrat ukuran input
• C. algoritma yang berjalan dalam waktu logaritmik
• D. algoritma yang tidak efisien dan tidak dapat digunakan

19. Dalam sistem basis data relasional, perintah SQL untuk mengambil data dari tabel adalah …

• A. INSERT
• B. UPDATE
• C. SELECT
• D. DELETE

20. Normalisasi basis data bertujuan untuk …

• A. mempercepat eksekusi query dengan menambah indeks
• B. mengurangi redundansi data dan mencegah anomali pembaruan (update anomaly)
• C. meningkatkan keamanan data dari akses tidak sah
• D. memperbesar kapasitas penyimpanan basis data

21. Pada model jaringan komputer OSI, lapisan yang bertanggung jawab atas pengalamatan logis (IP address) dan routing paket data adalah lapisan …

• A. lapisan fisik (physical layer)
• B. lapisan data link
• C. lapisan jaringan (network layer)
• D. lapisan transport

22. Protokol TCP berbeda dari UDP karena TCP …

• A. lebih cepat karena tidak ada mekanisme konfirmasi penerimaan
• B. menjamin pengiriman data secara handal dengan mekanisme acknowledgment dan retransmisi
• C. tidak memerlukan koneksi sebelum pengiriman data
• D. digunakan khusus untuk streaming video dan audio

23. Kriptografi simetris menggunakan …

• A. dua kunci berbeda untuk enkripsi dan dekripsi
• B. kunci publik untuk enkripsi dan kunci privat untuk dekripsi
• C. satu kunci yang sama untuk enkripsi dan dekripsi
• D. tidak menggunakan kunci sama sekali

24. Algoritma enkripsi RSA termasuk dalam kategori kriptografi …

• A. simetris
• B. asimetris (kunci publik)
• C. hashing
• D. substitusi klasik

25. Dalam pemrograman berorientasi objek (OOP), konsep yang memungkinkan suatu kelas mewarisi atribut dan metode dari kelas lain disebut …

• A. enkapsulasi
• B. polimorfisme
• C. abstraksi
• D. pewarisan (inheritance)

26. Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri. Kondisi yang harus dipenuhi agar rekursi berhenti disebut …

• A. base case (kasus dasar)
• B. rekursif case
• C. iterasi
• D. stack overflow

27. Bilangan prima yang digunakan dalam kriptografi RSA dipilih yang sangat besar karena …

• A. bilangan prima besar lebih mudah dihitung
• B. pemfaktoran hasil kali dua bilangan prima besar sangat sulit secara komputasi, menjamin keamanan kunci
• C. bilangan prima besar menghasilkan kunci yang lebih pendek
• D. tidak ada alasan matematis khusus

28. Permasalahan NP-Complete adalah permasalahan yang …

• A. tidak dapat diselesaikan oleh komputer apapun
• B. dapat diselesaikan dalam waktu polinomial oleh algoritma deterministik
• C. dapat diverifikasi solusinya dalam waktu polinomial, tetapi belum ditemukan algoritma penyelesaian polinomial
• D. hanya dapat diselesaikan oleh komputer kuantum

29. Automata hingga deterministik (DFA) menerima sebuah string jika dan hanya jika …

• A. string tersebut mengandung simbol tertentu
• B. setelah membaca seluruh string, DFA berada di salah satu state penerima (accepting state)
• C. string tersebut kosong
• D. DFA tidak pernah berada di state error selama pemrosesan

30. Konsep machine learning yang mengklasifikasikan data baru berdasarkan kedekatannya dengan data latihan yang sudah berlabel disebut algoritma …

• A. regresi linear
• B. K-Nearest Neighbors (KNN)
• C. naive Bayes
• D. decision tree

Bagian B – Isian Singkat

Isilah titik-titik berikut dengan jawaban yang tepat.

31. Bilangan oktal 375 jika dikonversi ke bilangan biner adalah …

32. Jumlah maksimum simpul pada pohon biner penuh (full binary tree) dengan ketinggian h adalah …

33. Perhatikan kode berikut (Python):

def hitung(n):
    total = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            total += 1
    return total

Kompleksitas waktu fungsi di atas adalah …

34. Algoritma untuk menemukan pohon merentang minimum (minimum spanning tree) yang bekerja dengan menambahkan sisi berbobot terkecil yang tidak membentuk siklus secara bertahap disebut algoritma …

35. Dalam teori bahasa formal, bahasa yang dapat dikenali oleh automata hingga (finite automata) disebut bahasa …

36. Operasi AND antara bilangan biner 10110101 dan 11001100 menghasilkan …

37. Nilai dari ekspresi postfix: 3 4 + 2 * 7 – adalah …

38. Protokol yang digunakan untuk menerjemahkan nama domain (seperti www.google.com) menjadi alamat IP disebut protokol …

39. Teknik pemrograman yang menyimpan hasil pemanggilan fungsi rekursif untuk menghindari perhitungan ulang disebut …

40. Dalam graf dengan V simpul dan E sisi, representasi matriks ketetanggaan membutuhkan ruang memori sebesar …

41. Metode pengurutan yang bekerja dengan cara menyisipkan setiap elemen ke posisi yang tepat dalam bagian larik yang sudah terurut disebut …

42. Jumlah bit yang dibutuhkan untuk merepresentasikan 256 nilai berbeda adalah …

43. Dalam SQL, klausa yang digunakan untuk memfilter hasil pengelompokan (GROUP BY) berdasarkan kondisi tertentu adalah …

44. Kelas kompleksitas yang mencakup semua masalah yang dapat diselesaikan oleh mesin Turing deterministik dalam waktu polinomial disebut kelas …

45. Proses mengubah data terstruktur (seperti objek) menjadi format yang dapat disimpan atau dikirim (seperti JSON atau biner) disebut …

Bagian C – Uraian

Kerjakan soal berikut dengan langkah penyelesaian yang lengkap.

46. Diberikan larik (array) bilangan bulat: [64, 25, 12, 22, 11]. (a) Jelaskan langkah-langkah pengurutan menggunakan algoritma selection sort hingga larik terurut menaik! (b) Berapa banyak perbandingan yang dilakukan oleh selection sort untuk larik berukuran n? Nyatakan dalam notasi Big-O! (c) Bandingkan selection sort dengan merge sort dari segi kompleksitas waktu dan penggunaan memori!

47. Perhatikan graf berikut dengan simpul A, B, C, D, E dan sisi berbobot:

• A-B: 4, A-C: 2
• B-C: 1, B-D: 5
• C-D: 8, C-E: 10
• D-E: 2

(a) Gambarkan representasi matriks ketetanggaan graf tersebut! (b) Gunakan algoritma Dijkstra untuk menemukan jalur terpendek dari simpul A ke semua simpul lainnya! (c) Gunakan algoritma Kruskal untuk menemukan pohon merentang minimum (MST) graf tersebut!

48. Rekursi dan pemrograman dinamis sering digunakan untuk menyelesaikan masalah optimasi. (a) Tuliskan fungsi rekursif (dalam pseudocode atau Python) untuk menghitung bilangan Fibonacci ke-n. Apa masalah utama pendekatan rekursif murni ini? (b) Perbaiki fungsi tersebut menggunakan teknik memoization. Bandingkan kompleksitas waktunya! (c) Selesaikan masalah knapsack 0/1 berikut menggunakan pemrograman dinamis: Kapasitas tas W = 6 kg. Terdapat 4 barang:

• Barang 1: berat 2 kg, nilai 6
• Barang 2: berat 2 kg, nilai 10
• Barang 3: berat 3 kg, nilai 12
• Barang 4: berat 1 kg, nilai 5 Tentukan nilai maksimum yang dapat dimasukkan ke dalam tas!

49. Keamanan jaringan dan kriptografi merupakan bagian penting dari ilmu komputer modern. (a) Jelaskan perbedaan antara kriptografi simetris dan asimetris beserta contoh algoritmanya! (b) Jelaskan cara kerja protokol HTTPS dalam mengamankan komunikasi web menggunakan konsep kriptografi asimetris dan simetris! (c) Apa yang dimaksud dengan serangan man-in-the-middle (MITM) dan bagaimana sertifikat digital (SSL/TLS certificate) mencegah serangan ini?

50. Teori komputasi mempelajari batas-batas kemampuan komputer. (a) Jelaskan apa yang dimaksud dengan mesin Turing dan mengapa ia dianggap sebagai model komputasi universal! (b) Jelaskan perbedaan antara kelas kompleksitas P dan NP, serta berikan contoh masalah dari masing-masing kelas! (c) Jelaskan masalah Travelling Salesman Problem (TSP) dan mengapa masalah ini penting dalam ilmu komputer! Sebutkan pendekatan yang digunakan untuk menyelesaikannya secara praktis!

Kunci Jawaban

Bagian A – Pilihan Ganda

Bagian B – Isian Singkat

Bagian C – Uraian (Pembahasan)

46. Jawaban:

(a) Selection sort pada [64, 25, 12, 22, 11]:

• Pass 1: Cari minimum dari indeks 0-4 → minimum = 11 (indeks 4). Tukar dengan indeks 0. Hasil: [11, 25, 12, 22, 64]
• Pass 2: Cari minimum dari indeks 1-4 → minimum = 12 (indeks 2). Tukar dengan indeks 1. Hasil: [11, 12, 25, 22, 64]
• Pass 3: Cari minimum dari indeks 2-4 → minimum = 22 (indeks 3). Tukar dengan indeks 2. Hasil: [11, 12, 22, 25, 64]
• Pass 4: Cari minimum dari indeks 3-4 → minimum = 25 (indeks 3). Tidak perlu tukar. Hasil: [11, 12, 22, 25, 64]
• Larik sudah terurut: [11, 12, 22, 25, 64]

(b) Jumlah perbandingan selection sort: Pada pass ke-i, dilakukan (n – i) perbandingan. Total = (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n^2)

(c) Perbandingan selection sort vs merge sort:

Selection sort cocok untuk dataset kecil atau memori sangat terbatas. Merge sort jauh lebih efisien untuk dataset besar karena kompleksitas O(n log n).

47. Jawaban:

(a) Matriks ketetanggaan (inf = tidak terhubung):

(b) Algoritma Dijkstra dari simpul A:

Jalur terpendek dari A:

• A → B: 3 (A→C→B)
• A → C: 2 (A→C)
• A → D: 8 (A→C→B→D)
• A → E: 10 (A→C→B→D→E)

(c) Algoritma Kruskal untuk MST:

Urutkan sisi berdasarkan bobot: B-C(1), A-C(2), D-E(2), A-B(4), B-D(5), C-D(8), C-E(10)

• Tambahkan B-C(1): tidak membentuk siklus. MST: {B-C}
• Tambahkan A-C(2): tidak membentuk siklus. MST: {B-C, A-C}
• Tambahkan D-E(2): tidak membentuk siklus. MST: {B-C, A-C, D-E}
• Tambahkan A-B(4): A,B,C sudah terhubung → membentuk siklus. Lewati.
• Tambahkan B-D(5): menghubungkan komponen {A,B,C} dengan {D,E}. MST: {B-C, A-C, D-E, B-D}

MST terbentuk dengan 4 sisi (V-1 = 5-1 = 4). Total bobot MST = 1 + 2 + 2 + 5 = 10

48. Jawaban:

(a) Rekursi Fibonacci:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Masalah utama: kompleksitas waktu O(2^n) karena banyak submasalah yang dihitung berulang kali. Misalnya fibonacci(5) memanggil fibonacci(4) dan fibonacci(3); fibonacci(4) juga memanggil fibonacci(3), sehingga fibonacci(3) dihitung dua kali (dan seterusnya secara eksponensial).

(b) Fibonacci dengan memoization:

memo = {}
def fibonacci_memo(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    return memo[n]

Kompleksitas waktu menjadi O(n) karena setiap nilai fibonacci(k) hanya dihitung sekali dan disimpan. Kompleksitas ruang O(n) untuk menyimpan hasil.

(c) Knapsack 0/1 dengan pemrograman dinamis:

Tabel dp[i][w] = nilai maksimum menggunakan i barang pertama dengan kapasitas w:

Nilai maksimum = 27 (ambil barang 2 + barang 3 + barang 4: 10+12+5=27, berat 2+3+1=6 kg)

49. Jawaban:

(a) Kriptografi simetris vs asimetris:

(b) Cara kerja HTTPS:

1. Client (browser) menghubungi server dan meminta sertifikat SSL/TLS.
2. Server mengirimkan sertifikat digital yang berisi kunci publik server, diverifikasi oleh Certificate Authority (CA) tepercaya.
3. Browser memverifikasi sertifikat; jika valid, browser membuat kunci sesi (session key) acak yang simetris, mengenkripsinya menggunakan kunci publik server, dan mengirimkannya ke server.
4. Server mendekripsi kunci sesi menggunakan kunci privatnya — hanya server yang bisa melakukan ini.
5. Selanjutnya seluruh komunikasi dienkripsi menggunakan kunci sesi simetris (AES) yang jauh lebih cepat. Kriptografi asimetris hanya digunakan di awal (handshake) untuk bertukar kunci simetris secara aman.

(c) Serangan MITM dan pencegahannya: Serangan man-in-the-middle terjadi ketika penyerang menyisipkan dirinya di antara komunikasi client dan server, mencegat dan berpotensi memodifikasi data yang dikirimkan tanpa sepengetahuan kedua pihak.

Sertifikat digital mencegah serangan ini karena: sertifikat diterbitkan oleh Certificate Authority (CA) tepercaya yang memverifikasi identitas pemilik domain. Sertifikat berisi kunci publik yang terikat pada nama domain tertentu dan ditandatangani secara digital oleh CA. Browser memiliki daftar CA tepercaya bawaan. Jika penyerang mencoba mengganti sertifikat dengan sertifikatnya sendiri, browser akan mendeteksi bahwa sertifikat tersebut tidak ditandatangani oleh CA tepercaya dan menampilkan peringatan kepada pengguna. Seorang penyerang tidak dapat memalsukan tanda tangan CA tanpa kunci privat CA.

50. Jawaban:

(a) Mesin Turing: Mesin Turing adalah model komputasi abstrak yang dikemukakan Alan Turing (1936) yang terdiri dari: pita tak terbatas yang dibagi menjadi sel-sel berisi simbol, kepala baca-tulis yang dapat bergerak ke kiri atau kanan, dan tabel aturan transisi (finite state control) yang menentukan tindakan berdasarkan state saat ini dan simbol yang dibaca.

Mesin Turing dianggap universal karena tesis Church-Turing menyatakan bahwa segala sesuatu yang dapat dihitung oleh algoritma apapun dapat dihitung oleh mesin Turing. Mesin Turing universal dapat mensimulasikan mesin Turing lainnya — prinsip ini menjadi dasar konsep komputer yang dapat diprogram untuk menjalankan program apapun.

(b) Kelas P vs NP:

• Kelas P (Polynomial): himpunan semua masalah keputusan yang dapat diselesaikan oleh algoritma deterministik dalam waktu polinomial O(n^k). Contoh: pencarian biner, pengurutan, jalur terpendek (Dijkstra), pencocokan string.
• Kelas NP (Nondeterministic Polynomial): himpunan semua masalah keputusan yang solusinya dapat diverifikasi dalam waktu polinomial, meskipun belum tentu dapat ditemukan dalam waktu polinomial. Contoh: Travelling Salesman Problem (TSP), satisfiability (SAT), knapsack, graph coloring.

Pertanyaan apakah P = NP (apakah setiap masalah yang dapat diverifikasi cepat juga dapat diselesaikan cepat) adalah salah satu masalah terbuka terbesar dalam ilmu komputer dan matematika, dengan hadiah $1 juta dari Clay Mathematics Institute.

(c) Travelling Salesman Problem (TSP): TSP adalah masalah mencari rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal, dengan diberikan sekumpulan kota dan jarak antarkota. TSP adalah masalah NP-Hard, artinya tidak ada algoritma yang diketahui dapat menyelesaikannya dalam waktu polinomial untuk kasus umum.

Pentingnya TSP dalam ilmu komputer: TSP muncul dalam banyak aplikasi nyata seperti optimasi rute pengiriman logistik, perencanaan jalur robot manufaktur, dan penjadwalan. TSP juga menjadi benchmark standar untuk menguji algoritma optimasi.

Pendekatan praktis:

1. Algoritma aproksimasi: seperti algoritma Christofides yang menjamin solusi tidak lebih dari 1,5 kali optimal dalam waktu polinomial.
2. Heuristik: seperti nearest neighbor (selalu ke kota terdekat belum dikunjungi), atau 2-opt/3-opt (perbaikan iteratif dengan menukar segmen rute).
3. Metaheuristik: algoritma genetika, simulated annealing, atau ant colony optimization yang mencari solusi mendekati optimal dalam waktu yang wajar untuk dataset besar.

• Author
• Recent Posts

Krisna Dwi Wardhana

Lahir di Padang pada tahun 1991, saya telah tinggal di berbagai wilayah di Indonesia sejak TK hingga kuliah, termasuk Aceh, Palembang, dan Bogor. Saya meraih gelar Sarjana Sains dari FMIPA Universitas Indonesia. Saat ini, saya bekerja sebagai Pendidik di sebuah sekolah swasta di Bogor, Tutor privat sambil tetap fokus mengembangkan Bisakimia.

Latest posts by Krisna Dwi Wardhana (see all)

• Latihan Soal OSN Ilmu Komputer SMA 2026 - June 1, 2026
• Latihan Soal OSN Kebumian SMA 2026 - May 31, 2026
• Latihan Soal OSN Geografi SMA 2026 - May 30, 2026