# Veri Yapıları, Karmaşıklık Analizi (Big-O) ve Temel Algoritmalar

> Temel programlama bilgisi gerektiren lisans düzeyinde tekrar: diziler, listeler, hash, ağaçlar, yığınlar, trie, Union–Find, Bloom filtreleri ve karmaşıklık üzerine 32 kart.

- **Canonical URL:** https://flashcards.world/flashcards/sets/98311363-8b36-4eb7-a825-fb42fb9923d5/
- **Markdown URL:** https://flashcards.world/flashcards/sets/98311363-8b36-4eb7-a825-fb42fb9923d5.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** tr → tr
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Tabloda arama için bir özetleme (hash) fonksiyonu hangi özellikleri taşımalıdır? | Deterministik olmalı ve beklenen anahtarları iyi dağıtmalıdır. Sabit boyutlu anahtarı özetlemek O(1) olabilir; yeni bir L karakterli dizgeyi özetlemek genellikle O(L) sürer. |  |  |
| 2 | Kuyruğun erişim kuralı ve tipik işlem maliyetleri nelerdir? | FIFO: arkadan eklenir, önden çıkarılır. Baş/son bağlantıları veya sabit kapasiteli dairesel tamponla ikisi de O(1) sürer; dizi elemanlarını kaydırmak çıkarmayı O(n) yapar. |  |  |
| 3 | Yol sıkıştırma ve rütbeye göre birleştirmeyle union/find'ın amortize maliyeti nedir? | İşlem başına O(α(n)); α ters Ackermann fonksiyonu, n eleman sayısıdır. Başlatma O(n) sürer; sınır bir işlem dizisine aittir, her çağrının en kötü maliyetinin sabit olduğunu söylemez. |  |  |
| 4 | Negatif olmayan f ve g fonksiyonları için f(n) ∈ O(g(n)) ne demektir? | Her n ≥ n₀ için f(n) ≤ c·g(n) olacak biçimde c > 0 ve n₀ ≥ 0 sabitleri vardır. |  |  |
| 5 | Yalnızca eklemeye izin veren bir Bloom filtresi hangi yanıtları verebilir? | Negatif sonuç öğenin eklenmediğini, pozitif sonuç eklenmiş olabileceğini söyler. Hash değerleri bit dizisindeki bitleri kurar; yanlış pozitifler mümkündür, durum bozulmamışsa yanlış negatifler yoktur. |  |  |
| 6 | BST'de arama, ekleme ve silme h yüksekliğine nasıl bağlıdır? | O(h) sürerler. Dengeli ağaçta h = O(log n), zincirde h = O(n) olur. Beklenen O(log n), rastgele ekleme sırası gibi varsayımlar gerektirir. |  |  |
| 7 | Sabit boyutlu bir dizide indisle erişim neden O(1) sürer? | Eşit boyutlu hücreler bitişiktir: adres(i) = başlangıç + i·hücre_boyutu. Adres aritmetiğinin sabit zaman aldığı varsayılır. |  |  |
| 8 | İkili yığında ekleme, kökü çıkarma ve kökü okuma maliyetleri nedir? | Dizi boyutlandırılmıyorsa sırasıyla O(log n), O(log n) ve O(1). Boyutlandırma O(n) sürebilir. |  |  |
| 9 | Yığın nasıl çalışır ve işlemleri ne zaman O(1) olur? | LIFO: son eklenen ilk çıkar. Bağlı listenin başında ekleme, çıkarma ve tepeyi okuma O(1) sürer; diziyi boyutlandırmak tek bir eklemeyi O(n) yapabilir. |  |  |
| 10 | Tek bağlı liste ile dinamik dizide başa ekleme ve indisle erişimi karşılaştırın. | Liste: başa ekleme O(1), indisle erişim O(n). Dizi: başa ekleme O(n), indisle erişim O(1); başa ekleme elemanları kaydırır. |  |  |
| 11 | Açık adreslemede doğrusal ve karesel yoklama nasıl farklılaşır? | Kayıtlar dizide kalır. Tablo boyutu m, ilk indis h ise sırasıyla (h+i) mod m ve (h+c₁i+c₂i²) mod m denenir. Karesel yoklama uygun parametreler gerektirir. |  |  |
| 12 | n öğeden aşağıdan yukarıya yığın kurmanın maliyeti nedir? | O(n). Düğümlerin çoğu yapraklara yakındır ve az aşağı süzülme gerektirir; düğüm yüksekliklerine göre iş toplamı doğrusaldır. |  |  |
| 13 | Ayrı zincirleme, hash çakışmalarını nasıl çözer? | Her kova o kova indisine sahip kayıtların bir koleksiyonunu, çoğunlukla bağlı listeyi tutar. Aynı kovadaki farklı anahtarlar ayrı kayıtlar olarak kalır. |  |  |
| 14 | O, Ω ve Θ arasındaki fark nedir? | Sırasıyla asimptotik üst, alt ve sıkı sınırlar verirler. Belirtilmiş bir maliyet fonksiyonunu tanımlarlar; O tek başına en kötü durum demek değildir. |  |  |
| 15 | Kırmızı-siyah BST'yi hangi renk kuralları dengede tutar? | Düğümler kırmızı veya siyahtır; kök ve NIL yaprakları siyahtır. Kırmızı düğümlerin kırmızı çocukları yoktur. Bir düğümden altındaki NIL yapraklarına giden her yol eşit sayıda siyah düğüm içerir. Böylece yükseklik O(log n) ile sınırlanır. |  |  |
| 16 | n → ∞ iken büyüme hızlarını yavaştan hızlıya sıralayın: n!, n, 1, n², log n, 2ⁿ, n log n. | Asimptotik olarak: 1 < log n < n < n log n < n² < 2ⁿ < n!. |  |  |
| 17 | Farklı anahtarlı BST'nin iç-sıra dolaşımı ne üretir? | Tüm anahtarları kesin artan sırada verir; n düğümü O(n) zamanda ziyaret eder. |  |  |
| 18 | Dairesel dizi kuyruğu, çıkarma sonrası kaydırmayı nasıl önler? | Baş ve son indisleri kapasiteye göre modüler olarak döner. Çıkarma baş indisini ilerletir; boşalan hücreler diğer elemanlar taşınmadan yeniden kullanılır. |  |  |
| 19 | Yol sıkıştırma, rütbeye göre birleştirme ve boyuta göre birleştirme nasıl farklıdır? | Sıkıştırma ziyaret edilen düğümleri köke yönlendirir. Rütbeye göre düşük rütbeli kök yükseğin altına; boyuta göre küçük küme büyüğün altına bağlanır. Rütbe güncel yüksekliğe eşit olmak zorunda değildir. |  |  |
| 20 | AVL eklemesi sonrası sol-sağ dengesizliği nasıl düzeltilir? | Önce sol çocuk sola, sonra dengesiz düğüm sağa döndürülür. |  |  |
| 21 | Sıfırdan indislenen, uzunluğu n olan yığın dizisinde i düğümünün ebeveyni ve çocukları nerededir? | Ebeveyn: i>0 için ⌊(i−1)/2⌋. Çocuklar: yalnızca indisler n'den küçükse 2i+1 ve 2i+2. İndis 0'ın ebeveyni yoktur. |  |  |
| 22 | Seviye sıralı dolaşım bir ikili ağacı nasıl ziyaret eder? | FIFO kuyruğuyla her seferinde bir derinlik seviyesi işlenir. Soldan sağa sıra için sol çocuk sağ çocuktan önce kuyruğa eklenir. |  |  |
| 23 | Kapasite iki katına çıkarılıyorsa dinamik dizinin sonuna eklemenin amortize maliyeti nedir? | Ekleme başına O(1). Boyutlandırma O(n) sürebilir; ancak boş diziden başlayarak n ekleme toplam O(n) sürer. |  |  |
| 24 | Ayrık kümeler yapısında find ve union ne yapar? | find(x), x'in kümesinin temsilcisini döndürür. union(x,y), farklıysa kümelerini birleştirir; zaten aynı kümedeyseler bölümleme değişmez. |  |  |
| 25 | Ayrı zincirlemeli hash tablosunda beklenen ve en kötü işlem maliyetleri nelerdir? | Sınırlı yük, iyi dağılmış hash değerleri ve sabit maliyetli anahtar işlemleriyle arama/silme beklenen O(1) sürer. Geometrik büyümeyle ekleme beklenen amortize O(1) sürer. Çakışan n anahtarlı zincir O(n) maliyet doğurabilir. |  |  |
| 26 | Hash tablosunun yük faktörü nedir ve neden boyutlandırılabilir? | α = n/m: n kayıt, m kova veya hücre. Uygulamanın eşiği aşılırsa daha büyük tabloya geçilip yeniden hash hesaplanabilir; 0,75 evrensel değildir. |  |  |
| 27 | İkili ağaçta ön-sıra, iç-sıra ve son-sıra dolaşım sıraları nelerdir? | Ön-sıra: düğüm → sol → sağ. İç-sıra: sol → düğüm → sağ. Son-sıra: sol → sağ → düğüm. |  |  |
| 28 | Farklı anahtarlı ikili arama ağacını (BST) hangi sıralama değişmezi tanımlar? | Her düğümde sol alt ağacın tüm anahtarları daha küçük, sağ alt ağacınkiler daha büyüktür. Kural özyinelemeli olarak geçerlidir. |  |  |
| 29 | Trie nedir ve L karakterli anahtar araması ne zaman O(L) sürer? | Önek ağacı, anahtarları karakter yollarında ve tam anahtar işaretleriyle tutar. Sonraki karaktere her geçiş O(1) ise arama O(L) sürer. |  |  |
| 30 | AVL denge koşulu nedir? | Her düğümde yükseklik(sol) − yükseklik(sağ) ∈ {−1, 0, 1}. Ağaç ayrıca BST sıralama değişmezini sağlar. |  |  |
| 31 | Çift bağlı liste, verilen bir düğümü neden O(1) zamanda silebilir? | Önceki ve sonraki bağlantıları komşuları doğrudan yeniden bağlamayı sağlar. Gerektiğinde baş/son güncellenir; önceki düğümü aramaya gerek yoktur. |  |  |
| 32 | İkili min-yığını hangi iki özellik tanımlar? | Son seviye dışında tüm seviyeler doludur; son seviye soldan doldurulur. Her ebeveynin anahtarı çocuklarınınkinden büyük değildir. Dolayısıyla kökte bir minimum bulunur. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/98311363-8b36-4eb7-a825-fb42fb9923d5/).
