Struktur Data, Analisis Kompleksitas (Big-O), dan Algoritma Inti

Tinjauan tingkat sarjana yang memerlukan dasar pemrograman: 32 kartu tentang larik, senarai, hashing, pohon, heap, trie, Union–Find, filter Bloom, dan kompleksitas.

Category
Computer Science
Level
basic
Languages
id → id
Cards
32
Markdown
Struktur Data, Analisis Kompleksitas (Big-O), dan Algoritma Inti (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Apa faktor muat tabel hash dan mengapa ukurannya dapat berubah?α = n/m: n entri tersimpan dan m bucket atau slot. Melewati ambang implementasi dapat memicu pembesaran dan hashing ulang; 0,75 bukan ambang universal.
2Di mana induk dan anak simpul i pada larik heap sepanjang n dengan indeks mulai nol?Induk: ⌊(i−1)/2⌋ untuk i>0. Anak: 2i+1 dan 2i+2, hanya jika indeks tersebut kurang dari n. Indeks 0 tidak memiliki induk.
3Berapa biaya membangun heap dari bawah ke atas dengan n elemen?O(n). Sebagian besar simpul dekat daun dan hanya memerlukan sedikit penurunan; penjumlahan kerja berdasarkan tinggi simpul memberi total linear.
4Jawaban apa yang dapat diberikan filter Bloom yang hanya mengizinkan penyisipan?Hasil negatif berarti item belum pernah disisipkan; positif berarti mungkin pernah. Hash menyetel bit pada larik bit; positif palsu mungkin terjadi, tetapi negatif palsu tidak jika keadaan tetap utuh.
5Bagaimana penelusuran per tingkat mengunjungi pohon biner?Gunakan antrean FIFO untuk mengunjungi satu tingkat kedalaman setiap kali. Masukkan anak kiri sebelum anak kanan agar urutannya dari kiri ke kanan.
6Apa hasil penelusuran inorder BST dengan kunci berbeda?Semua kunci dalam urutan naik ketat, dengan mengunjungi n simpul dalam O(n).
7Urutkan laju pertumbuhan dari paling lambat ke paling cepat saat n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.Secara asimtotik: 1 < log n < n < n log n < n² < 2ⁿ < n!.
8Berapa biaya harapan dan biaya terburuk operasi tabel hash dengan perantaian terpisah?Dengan muatan terbatas, hash tersebar baik, dan operasi kunci berbiaya konstan, pencarian/penghapusan berbiaya harapan O(1). Penyisipan dengan pertumbuhan geometris berbiaya harapan teramortisasi O(1). Rantai n kunci bertabrakan dapat membuat operasi O(n).
9Bagaimana perantaian terpisah menyelesaikan tabrakan hash?Setiap bucket menyimpan kumpulan entri dengan indeks bucket tersebut, sering berupa senarai berantai. Kunci berbeda dalam satu bucket tetap menjadi entri terpisah.
10Mengapa senarai berantai ganda dapat menghapus simpul yang diberikan dalam O(1)?Tautan sebelumnya dan berikutnya memungkinkan tetangga disambungkan langsung. Perbarui kepala/ekor bila perlu; tidak perlu mencari pendahulu.
11Untuk fungsi nonnegatif f dan g, apa arti f(n) ∈ O(g(n))?Ada konstanta c > 0 dan n₀ ≥ 0 sehingga f(n) ≤ c·g(n) untuk setiap n ≥ n₀.
12Bandingkan penyisipan di awal dan akses indeks pada senarai berantai tunggal dan larik dinamis.Senarai: penyisipan awal O(1), akses indeks O(n). Larik: penyisipan awal O(n), akses indeks O(1); penyisipan di awal menggeser elemen.
13Apa perbedaan kompresi jalur, penggabungan berdasarkan rank, dan berdasarkan ukuran?Kompresi mengarahkan simpul yang dikunjungi ke akar. Berdasarkan rank, akar ber-rank rendah ditautkan di bawah yang lebih tinggi; berdasarkan ukuran, himpunan kecil di bawah yang besar. Rank tidak harus sama dengan tinggi saat ini.
14Apa dua sifat yang mendefinisikan min-heap biner?Berbentuk pohon biner lengkap, dan kunci setiap induk tidak lebih besar daripada kunci anaknya. Jadi akar menyimpan suatu nilai minimum.
15Apa syarat keseimbangan AVL?Di setiap simpul, tinggi(kiri) − tinggi(kanan) ∈ {−1, 0, 1}. Pohon juga memenuhi invarian urutan BST.
16Mengapa akses indeks pada larik berukuran tetap memerlukan O(1)?Slot berukuran sama tersimpan berurutan: alamat(i) = dasar + i·ukuran_slot. Perhitungan alamat diasumsikan memerlukan waktu konstan.
17Jika kapasitas digandakan, berapa biaya teramortisasi penambahan di akhir larik dinamis?O(1) per penambahan. Perubahan ukuran bisa berbiaya O(n), tetapi n penambahan dari larik kosong hanya berbiaya total O(n).
18Apa aturan akses dan biaya operasi umum antrean?FIFO: tambah di belakang, keluarkan dari depan. Keduanya O(1) dengan tautan kepala/ekor atau penyangga melingkar berkapasitas tetap; menggeser larik membuat pengeluaran O(n).
19Berapa biaya penyisipan, penghapusan akar, dan melihat akar pada heap biner?Berturut-turut O(log n), O(log n), dan O(1) jika ukuran larik tidak perlu diubah. Perubahan ukuran dapat berbiaya O(n).
20Bagaimana tumpukan bekerja dan kapan operasinya O(1)?LIFO: yang terakhir masuk keluar pertama. Pada kepala senarai berantai, menambah, mengeluarkan, dan melihat puncak berbiaya O(1); perubahan ukuran larik dapat membuat satu penambahan O(n).
21Apa perbedaan probing linear dan kuadratik dalam pengalamatan terbuka?Entri tetap di larik. Untuk ukuran tabel m dan indeks awal h, posisi yang dicoba adalah (h+i) mod m atau (h+c₁i+c₂i²) mod m. Probing kuadratik memerlukan parameter yang sesuai.
22Bagaimana pencarian, penyisipan, dan penghapusan BST bergantung pada tinggi h?Ketiganya O(h). Pohon seimbang memiliki h = O(log n); rantai memiliki h = O(n). Biaya harapan O(log n) memerlukan asumsi seperti urutan penyisipan acak.
23Aturan warna apa yang menjaga keseimbangan BST merah-hitam?Simpul berwarna merah atau hitam; akar dan daun NIL hitam. Simpul merah tidak memiliki anak merah. Setiap jalur dari suatu simpul ke daun NIL keturunannya memiliki jumlah simpul hitam yang sama. Aturan ini membatasi tinggi menjadi O(log n).
24Bagaimana antrean larik melingkar menghindari pergeseran setelah pengeluaran?Indeks depan dan belakang berputar modulo kapasitas. Pengeluaran memajukan indeks depan, sehingga slot kosong bisa dipakai kembali tanpa memindahkan elemen lain.
25Apa sifat fungsi hash yang diperlukan untuk pencarian tabel?Harus deterministik dan menyebarkan kunci yang diperkirakan dengan baik. Menghitung hash kunci berukuran tetap bisa O(1); string baru sepanjang L karakter biasanya O(L).
26Apa itu trie dan kapan pencarian kunci sepanjang L karakter berbiaya O(L)?Pohon prefiks menyimpan kunci sepanjang jalur karakter, dengan penanda kunci lengkap. Pencarian O(L) jika setiap transisi ke karakter berikutnya O(1).
27Invarian urutan apa yang mendefinisikan pohon pencarian biner (BST) dengan kunci berbeda?Pada setiap simpul, semua kunci subpohon kiri lebih kecil dan semua kunci subpohon kanan lebih besar. Aturan ini berlaku rekursif.
28Apa fungsi find dan union dalam struktur himpunan saling lepas?find(x) mengembalikan wakil himpunan x. union(x,y) menggabungkan himpunan mereka jika berbeda; jika sudah sama, partisi tidak berubah.
29Apa perbedaan O, Ω, dan Θ?Masing-masing menyatakan batas asimtotik atas, bawah, dan ketat. Ketiganya menggambarkan fungsi biaya tertentu; O sendiri tidak berarti kasus terburuk.
30Berapa biaya teramortisasi union/find dengan kompresi jalur dan penggabungan berdasarkan rank?O(α(n)) per operasi, dengan α fungsi invers Ackermann dan n jumlah elemen. Inisialisasi O(n); batas berlaku untuk rangkaian operasi, bukan biaya terburuk konstan untuk setiap panggilan.
31Apa urutan penelusuran preorder, inorder, dan postorder pada pohon biner?Preorder: simpul → kiri → kanan. Inorder: kiri → simpul → kanan. Postorder: kiri → kanan → simpul.
32Bagaimana ketidakseimbangan kiri-kanan akibat penyisipan AVL diperbaiki?Putar anak kiri ke kiri terlebih dahulu, lalu putar simpul yang tidak seimbang ke kanan.