# Algoritme, graf, pemrograman dinamis, dan basis data relasional

> 32 kartu ulasan tingkat sarjana tentang pengurutan, algoritme graf, pemrograman dinamis, SQL, indeks, dan transaksi. Memerlukan dasar pemrograman, struktur data, dan SQL.

- **Canonical URL:** https://flashcards.world/flashcards/sets/a8b1bfaf-56f1-4959-a317-c9a0ee59b5fb/
- **Markdown URL:** https://flashcards.world/flashcards/sets/a8b1bfaf-56f1-4959-a317-c9a0ee59b5fb.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** id → id
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Bagaimana perbandingan matriks ketetanggaan dan daftar ketetanggaan biasa? | Untuk V simpul dan E sisi, matriks memakai ruang O(V²) dan menguji sisi dalam O(1). Daftar memakai O(V+E); mencari sisi (u,v) dalam daftar tak terurut memerlukan O(deg(u)), dengan deg(u) panjang daftar itu. |  |  |
| 2 | Apa perbedaan algoritme rakus dan pemrograman dinamis? | Algoritme rakus menetapkan pilihan lokal dan memerlukan bukti bahwa pilihan itu mempertahankan optimum. DP membandingkan alternatif melalui rekurensi dan menggunakan ulang hasil submasalah. Optimum global memerlukan model dan rekurensi yang benar, bukan sekadar label “DP”. |  |  |
| 3 | Apa urutan pemrosesan logis sederhana untuk kueri SQL SELECT? | Untuk kueri tanpa CTE, fungsi jendela, atau operasi himpunan: FROM/JOIN → WHERE → GROUP BY dan agregat → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Ini model logis, belum tentu urutan eksekusi fisik oleh pengoptimal. |  |  |
| 4 | Apa arti sifat transaksi ACID? | Atomisitas: dampak seluruhnya atau tidak sama sekali. Konsistensi: transaksi yang benar mempertahankan batasan dan invarian aplikasi. Isolasi: perilaku serentak mematuhi tingkat isolasi yang dipilih. Durabilitas: dampak yang telah di-commit bertahan terhadap kegagalan yang tercakup oleh jaminan basis data yang dikonfigurasi. |  |  |
| 5 | Apa rekurensi standar knapsack 0/1 dengan kapasitas bilangan bulat W? | Misalkan D[i,w] adalah nilai terbaik memakai i barang pertama dengan kapasitas w, dan bobot bilangan bulat positif wᵢ. Tetapkan D[0,w]=0. Jika wᵢ>w, salin D[i−1,w]; jika tidak, ambil max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Waktu O(NW) bersifat pseudo-polinomial. |  |  |
| 6 | Apa perbedaan INNER JOIN dan LEFT JOIN? | INNER JOIN mengembalikan kombinasi baris yang memenuhi kondisi join. LEFT JOIN juga mempertahankan setiap baris kiri tanpa pasangan, dengan NULL untuk kolom kanan. Beberapa baris kanan yang cocok dapat menghasilkan beberapa baris keluaran untuk satu baris kiri. |  |  |
| 7 | Apa perbedaan WHERE dan HAVING dalam kueri berkelompok? | WHERE menyaring baris masukan sebelum pengelompokan. HAVING menyaring kelompok hasil dan dapat memakai kondisi agregat, seperti COUNT(*)>1. |  |  |
| 8 | Apa itu pembacaan kotor, dan tingkat isolasi standar terendah mana yang mencegahnya? | Membaca data transaksi lain yang belum di-commit, baik transaksi itu nantinya dibatalkan maupun tidak. READ COMMITTED dan tingkat isolasi standar yang lebih kuat melarang pembacaan kotor. |  |  |
| 9 | Bagaimana pencarian mendalam mendeteksi siklus pada graf berarah? | DFS menelusuri secara mendalam memakai rekursi atau tumpukan eksplisit. Sisi ke simpul yang masih aktif pada lintasan DFS saat ini adalah sisi balik dan membuktikan adanya siklus berarah; sisi ke sembarang simpul yang pernah dikunjungi tidak cukup. |  |  |
| 10 | Mengapa pohon B+ berguna untuk indeks basis data dan kueri rentang? | Percabangan yang tinggi membuat pohon dangkal, sehingga akses halaman berkurang. Kunci terurut dan daun tertaut mendukung pemindaian rentang. Indeks hash ditujukan untuk pencarian kesamaan dan tidak secara inheren menyediakan akses rentang terurut yang sama. |  |  |
| 11 | Bagaimana merge sort standar pada array bekerja, dan apa batas waktu serta ruangnya? | Algoritme ini mengurutkan dua bagian secara rekursif lalu menggabungkannya dalam waktu linear. Versi standar memerlukan waktu Θ(n log n) dan ruang tambahan O(n), dengan asumsi perbandingan berwaktu konstan. |  |  |
| 12 | Apa syarat bentuk normal pertama, kedua, dan ketiga? | 1NF: nilai atribut atomik. 2NF: 1NF dan tidak ada atribut nonprima yang bergantung pada bagian sejati dari kunci kandidat mana pun. 3NF: 1NF dan setiap dependensi nontrivial X→A memiliki X sebagai superkey atau A sebagai atribut prima. Atribut prima termasuk dalam setidaknya satu kunci kandidat. |  |  |
| 13 | Bagaimana insertion sort bekerja, dan apa yang menentukan waktunya pada masukan hampir terurut? | Setiap elemen disisipkan ke prefiks yang sudah terurut. Versi umum dengan pergeseran atau pertukaran elemen bersebelahan memerlukan waktu Θ(n+I), dengan I jumlah inversi. Waktunya linear saat I=O(n); masukan kecil saja tidak mengubah batas kasus terburuk Θ(n²). |  |  |
| 14 | Apa itu pembacaan tak berulang, dan tingkat isolasi standar mana yang mencegahnya? | Membaca ulang baris menghasilkan data yang berubah atau barisnya hilang setelah transaksi lain melakukan commit atas pembaruan atau penghapusan. REPEATABLE READ dan SERIALIZABLE melarang anomali ini. |  |  |
| 15 | Kapan counting sort atau radix sort berjalan dalam waktu linear? | Counting sort memerlukan O(n+k) untuk n kunci dalam rentang k nilai. Radix sort dengan d lintasan digit stabil dan basis b memerlukan O(d(n+b)). Keduanya linear hanya jika parameternya memungkinkan; keduanya memakai struktur kunci di luar perbandingan. |  |  |
| 16 | Bagaimana algoritme Kruskal dan Prim membangun pohon merentang minimum? | Untuk graf terhubung, tak berarah, dan berbobot, Kruskal memeriksa sisi menurut bobot menaik dan memakai Union–Find untuk menolak siklus. Prim mengembangkan satu pohon dengan berulang kali memilih sisi berbobot minimum yang menghubungkan pohon ke simpul di luarnya. |  |  |
| 17 | Kapan algoritme Dijkstra valid, dan apa batas umum berbasis heap? | Dengan bobot sisi tak negatif, algoritme ini berulang kali menetapkan simpul dengan jarak sementara terkecil. Implementasi daftar ketetanggaan dengan min-heap biner memerlukan O((V+E) log V). Sisi negatif dapat membatalkan argumen tentang jarak yang telah ditetapkan. |  |  |
| 18 | Apa syarat pencarian biner, dan kapan waktunya O(log n)? | Pencarian ini berulang kali membagi dua interval pencarian dalam data yang terurut sesuai urutan pembanding. Pada array dengan akses indeks O(1) dan perbandingan waktu konstan, pencarian n elemen memerlukan waktu O(log n). |  |  |
| 19 | Bagaimana WAL PostgreSQL mendukung durabilitas pada commit sinkron biasa? | Catatan log terkait mencapai penyimpanan tahan lama sebelum commit diakui dan sebelum halaman data yang berubah ditulis. Setelah kegagalan, WAL dapat memutar ulang perubahan yang belum ada pada halaman data. Commit asinkron dapat kehilangan transaksi yang baru diakui. |  |  |
| 20 | Apa perbedaan indeks rowstore terkluster dan nonkluster dalam SQL Server? | Indeks terkluster menyimpan baris tabel menurut urutan kunci, sehingga satu tabel memiliki paling banyak satu. Indeks nonkluster memiliki kunci dan penunjuk lokasi baris sendiri serta dapat mencakup kolom lain. Istilah dan rincian penyimpanan berbeda antar sistem basis data. |  |  |
| 21 | Apa itu urutan topologis, dan bagaimana algoritme Kahn menemukannya? | Dalam DAG, setiap sisi u→v menempatkan u sebelum v. Keluarkan berulang kali simpul berderajat masuk nol dan hapus sisi keluarnya, sambil memasukkan simpul baru berderajat masuk nol ke antrean. Jika kurang dari V simpul dikeluarkan, graf berarah itu memiliki siklus. |  |  |
| 22 | Apa perbedaan memoisasi dan pemrograman dinamis dari bawah ke atas? | Memoisasi menghitung submasalah sesuai kebutuhan, biasanya secara rekursif, lalu menyimpan hasilnya. DP dari bawah ke atas menghitung keadaan dalam urutan ketika dependensinya sudah tersedia, biasanya dengan mengisi tabel. |  |  |
| 23 | Bagaimana pencarian melebar menemukan lintasan terpendek pada graf tanpa bobot? | BFS memakai antrean FIFO dan menelusuri simpul menurut jarak dalam jumlah sisi. Menandai simpul saat dimasukkan ke antrean mencegah kunjungan berulang. Lintasan pertama yang ditemukan ke simpul terjangkau memiliki jumlah sisi minimum. |  |  |
| 24 | Mengapa quicksort dapat memerlukan Θ(n²), dan bagaimana pengacakan membantu? | Partisi yang berulang kali sangat tidak seimbang, misalnya selalu memilih kunci terkecil ketika kunci-kuncinya berbeda, menghasilkan kerja kuadratik. Dengan kunci berbeda atau penanganan duplikat yang tepat, pivot acak memberi waktu harapan O(n log n). Median-dari-tiga adalah heuristik berguna, bukan jaminan kasus terburuk. |  |  |
| 25 | Apa batas waktu kasus terburuk dan ruang tambahan heapsort di tempat? | Membangun heap memerlukan O(n), diikuti total kerja ekstraksi O(n log n). Dengan sift-down iteratif di array masukan, heapsort memerlukan waktu kasus terburuk O(n log n) dan ruang tambahan O(1). |  |  |
| 26 | Apa itu pembacaan fantom, dan bagaimana mencegahnya? | Pengulangan kueri berpredikat menemukan himpunan baris cocok yang berbeda setelah transaksi lain melakukan commit perubahan. SERIALIZABLE mencegah fantom dalam model standar; beberapa implementasi, termasuk PostgreSQL REPEATABLE READ, juga mencegahnya pada tingkat lebih rendah. |  |  |
| 27 | Apa yang membuat algoritme pengurutan stabil? | Elemen berkunci sama mempertahankan urutan relatif semula. Merge sort dapat stabil dengan mengambil elemen kiri dahulu saat kunci sama; quicksort standar yang bekerja di tempat umumnya tidak stabil. Stabilitas bergantung pada implementasi. |  |  |
| 28 | Apa perbedaan kunci primer dan kunci asing dalam PostgreSQL? | Kunci primer mengidentifikasi baris dengan nilai unik yang bukan NULL. Kunci asing mensyaratkan nilai yang cocok dengan kunci rujukan, sesuai aturan NULL-nya. Kunci asing dapat merujuk kunci UNIQUE yang memenuhi syarat atau kunci primer dalam tabel yang sama ataupun berbeda. |  |  |
| 29 | Apa rekurensi DP untuk panjang subsekuens bersama terpanjang, LCS? | Misalkan L[i,j] adalah panjang LCS dari prefiks berpanjang i,j. Tetapkan L[0,j]=L[i,0]=0. Jika karakter terakhir sama, L[i,j]=1+L[i−1,j−1]; jika tidak, L[i,j]=max(L[i−1,j],L[i,j−1]). Tabel lengkap memakai waktu dan ruang O(mn). |  |  |
| 30 | Bagaimana Bellman–Ford menangani sisi negatif dan mendeteksi siklus negatif yang terjangkau? | Relaksasi semua sisi hingga V−1 kali. Perbaikan lebih lanjut dari simpul terjangkau menunjukkan siklus negatif yang terjangkau dari sumber. Waktu kasus terburuknya O(VE); simpul yang terjangkau dari siklus itu tidak memiliki biaya lintasan terpendek yang berhingga. |  |  |
| 31 | Mengapa pemrograman dinamis berguna bagi banyak masalah optimasi? | Substruktur optimal memungkinkan optimum dinyatakan melalui optimum submasalah. Jika submasalah tumpang tindih, menyimpan jawabannya menghindari kerja berulang. Definisi keadaan dan relasi rekurensi harus mewakili masalah asli dengan benar. |  |  |
| 32 | Apa dua fase penguncian dua fase, 2PL? | Fase tumbuh: memperoleh kunci tanpa melepasnya. Fase menyusut: melepas kunci tanpa memperoleh yang baru. Dengan kunci baca/tulis yang berkonflik secara tepat, 2PL menjamin jadwal yang dapat diserialkan berdasarkan konflik, tetapi kebuntuan tetap mungkin terjadi. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/a8b1bfaf-56f1-4959-a317-c9a0ee59b5fb/).
