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.

Category
Computer Science
Level
basic
Languages
id → id
Cards
32
Markdown
Algoritme, graf, pemrograman dinamis, dan basis data relasional (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Bagaimana 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.
2Apa 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”.
3Apa 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.
4Apa 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.
5Apa 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.
6Apa 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.
7Apa 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.
8Apa 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.
9Bagaimana 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.
10Mengapa 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.
11Bagaimana 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.
12Apa 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.
13Bagaimana 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²).
14Apa 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.
15Kapan 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.
16Bagaimana 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.
17Kapan 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.
18Apa 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).
19Bagaimana 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.
20Apa 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.
21Apa 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.
22Apa 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.
23Bagaimana 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.
24Mengapa 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.
25Apa 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).
26Apa 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.
27Apa 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.
28Apa 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.
29Apa 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).
30Bagaimana 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.
31Mengapa 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.
32Apa 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.