Evaluasi Pemahaman

Setelah membahas konsep dasar DSA, peran struktur data dan algoritma, kategori keduanya, hingga strategi belajar, kini saatnya kita menguji pemahaman secara aktif. Evaluasi ini bukan sekadar menguji hafalan; tujuannya adalah memastikan kita dapat menerapkan konsep pada situasi baru. Kerjakan soal-soal berikut sebelum melihat jawaban. Jika ada jawaban yang salah, kembali ke Chapter terkait dan pelajari ulang bagian yang masih belum kuat.

Soal Pilihan Ganda #

Soal 1 — Definisi Struktur Data #

Manakah pernyataan yang paling tepat mendefinisikan struktur data?

• A. Algoritma untuk mengurutkan data secara cepat.
• B. Cara terorganisir menyimpan, mengelola, dan mengakses data di memori.
• C. Bahasa pemrograman untuk memproses data.
• D. Jenis tipe data bawaan dalam C++.

Jawaban: B

Penjelasan: Struktur data adalah cara penyimpanan dan pengelolaan data. Struktur data bukan algoritma (A salah), bukan bahasa pemrograman (C salah), dan bukan hanya tipe data bawaan (D salah, karena struktur data bisa berupa komposisi seperti tree atau graph).

Soal 2 — Hubungan Struktur Data dan Algoritma #

Algoritma binary search tidak efisien jika dipakai pada linked list. Apa alasan utamanya?

• A. Linked list tidak dapat menyimpan data terurut.
• B. Binary search hanya bekerja pada tipe numerik.
• C. Linked list tidak mendukung akses acak ke elemen ke-i dalam O(1).
• D. Linked list membutuhkan memori terlalu besar.

Jawaban: C

Penjelasan: Binary search memerlukan akses langsung ke elemen tengah rentang (data[tengah]). Linked list hanya mendukung akses berurutan sehingga mengakses elemen ke-i memerlukan O(i) langkah. Akibatnya, binary search pada linked list memiliki kompleksitas O(n log n), lebih buruk daripada linear search pada beberapa skenario. Pilihan A salah karena linked list bisa menyimpan data terurut.

Soal 3 — Kategori Struktur Data #

Manakah dari berikut yang termasuk struktur data non-linier?

• A. std::vector
• B. linked list
• C. stack
• D. binary tree

Jawaban: D

Penjelasan: Binary tree menyusun elemen secara hierarkis dengan simpul yang memiliki anak kiri dan kanan. Struktur seperti ini tidak linier karena satu simpul dapat terhubung ke beberapa penerus. std::vector, linked list, dan stack adalah struktur linier.

Soal 4 — Paradigma Algoritma #

Masalah knapsack 0/1 paling cocok diselesaikan dengan paradigma:

• A. Greedy
• B. Brute force saja
• C. Dynamic programming
• D. Backtracking saja

Jawaban: C

Penjelasan: Knapsack 0/1 memiliki overlapping subproblems dan optimal substructure, dua syarat yang membuat dynamic programming efektif. Greedy tidak selalu optimal untuk knapsack 0/1 (berbeda dengan fractional knapsack yang bisa greedy). Brute force dan backtracking bisa menyelesaikan masalah ini tetapi memiliki kompleksitas eksponensial.

Soal True/False #

Soal 5 #

Pernyataan: “Dua algoritma yang menghasilkan output identik pasti memiliki kompleksitas waktu yang sama.”

• A. Benar
• B. Salah

Jawaban: B (Salah)

Penjelasan: Dua algoritma bisa menghasilkan output identik tetapi memiliki kompleksitas berbeda orde. Contoh: linear search vs binary search pada dataset besar. Output keduanya sama (indeks target), tetapi jumlah operasi pada kasus terburuk berbeda jauh.

Soal 6 #

Pernyataan: “std::vector di C++ bersifat statis karena ukurannya ditentukan saat kompilasi.”

• A. Benar
• B. Salah

Jawaban: B (Salah)

Penjelasan: std::vector adalah struktur data dinamis yang dapat berubah ukuran saat runtime. Yang statis adalah std::array<T, N> yang ukurannya ditentukan oleh parameter template N saat kompilasi.

Soal Isian Singkat #

Soal 7 #

Sebutkan tiga kriteria algoritma yang baik yang dibahas pada Chapter Konsep Dasar DSA.

Jawaban: Tepat (correct), terbatas (finite), dan efisien (efficient). Kriteria keempat yang juga sering disebut: tentu (deterministic).

Soal 8 #

Apa dua syarat agar greedy algorithm menghasilkan solusi optimal global?

Jawaban:

1. Greedy choice property: pilihan optimal lokal membawa solusi optimal global.
2. Optimal substructure: solusi optimal masalah mengandung solusi optimal submasalah.

Soal Implementasi Mini #

Soal 9 — Mencari Indeks Nilai Maksimum #

Tulis fungsi C++ indeksMaksimum(const std::vector<int>& data) yang mengembalikan indeks elemen dengan nilai terbesar pada std::vector<int>. Jika data kosong, kembalikan -1. Jika ada beberapa elemen dengan nilai maksimum sama, kembalikan indeks pertama yang ditemukan.

Contoh Solusi #

#include <iostream>
#include <vector>
#include <climits>

// Mencari indeks nilai maksimum dalam std::vector<int>
// Jika vector kosong, kembalikan -1
int indeksMaksimum(const std::vector<int>& data) {
    if (data.empty()) return -1;

    int idxMax = 0;
    for (int i = 1; i < (int)data.size(); ++i) {
        if (data[i] > data[idxMax]) {
            idxMax = i;
        }
    }
    return idxMax;
}

int main() {
    std::vector<int> data = {7, 12, 3, 19, 8, 19, 5};

    int idx = indeksMaksimum(data);
    std::cout << "Indeks maksimum : " << idx << "\n";
    std::cout << "Nilai maksimum  : " << data[idx] << "\n";

    // Kasus vector kosong
    std::vector<int> kosong;
    int idxKosong = indeksMaksimum(kosong);
    std::cout << "Indeks pada vector kosong: " << idxKosong << "\n";

    return 0;
}

Output yang Dihasilkan:

Indeks maksimum : 3
Nilai maksimum  : 19
Indeks pada vector kosong: -1

Bedah Kode Baris-per-Baris #

1. Baris 7 (if (data.empty()) return -1;): penanganan edge case vector kosong. Tanpa ini, data[0] pada baris 9 akan undefined behavior pada vector kosong.
2. Baris 9 (int idxMax = 0;): inisialisasi indeks maksimum ke 0. Artinya elemen pertama diasumsikan menjadi maksimum sementara.
3. Baris 11 (if (data[i] > data[idxMax])): pembandingan ketat > (bukan >=) memastikan kita menyimpan indeks pertama jika ada beberapa elemen dengan nilai maksimum sama.
4. Baris 16–17 (output): menampilkan indeks dan nilai maksimum untuk verifikasi visual.

Analisis Kompleksitas #

• Time complexity: O(n), karena loop menjelajah n - 1 elemen.
• Space complexity: O(1), hanya menyimpan satu variabel idxMax.

Tabel Ringkasan Jawaban #

Penilaian Diri #

Setelah mengecek jawaban, gunakan rubrik berikut untuk menilai pemahaman:

Refleksi dan Langkah Berikutnya #

Sebelum melanjutkan ke Section berikutnya, jawab pertanyaan refleksi berikut secara jujur:

1. Apakah saya bisa menjelaskan perbedaan struktur data linier dan non-linier dengan kalimat sendiri?
2. Apakah saya bisa menyebutkan minimal tiga paradigma algoritma dan kapan masing-masing cocok dipakai?
3. Apakah saya punya rencana belajar mingguan yang konkret untuk Course ini?
4. Apakah saya sudah mencoba menulis minimal satu program C++ sederhana dari nol?

Jika jawaban semua pertanyaan di atas “ya”, kita siap melanjutkan ke Section 2 — Persiapan C++. Pada Section tersebut kita akan menyiapkan toolchain C++ modern yang dipakai sepanjang Course ini.