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.

Category
Computer Science
Level
basic
Languages
tr → tr
Cards
32
Markdown
Veri Yapıları, Karmaşıklık Analizi (Big-O) ve Temel Algoritmalar (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Tabloda 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.
2Kuyruğ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.
3Yol 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.
4Negatif 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.
5Yalnı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.
6BST'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.
7Sabit 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.
9Yığı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.
10Tek 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.
11Açı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.
12n öğ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.
13Ayrı 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.
14O, Ω 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.
15Kı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.
16n → ∞ 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!.
17Farklı 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.
18Dairesel 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.
19Yol 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.
20AVL 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.
21Sı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.
22Seviye 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.
23Kapasite 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.
24Ayrı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.
25Ayrı 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.
26Hash 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.
28Farklı 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.
29Trie 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.
30AVL 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.