AUZEF Veri Yapıları Çıkmış Sorular

Veri Yapıları dersi; verinin bilgiye dönüşümünü, dizi ve bağlı liste gibi temel yapıları, yığın ile kuyruğun çalışma düzenini, işaretçi ve dinamik bellek yönetimini, ayrıca algoritma verimliliğinin Big-O ile ölçülmesini anlatır.

Veri, enformasyon ve bilgi

• Veri; gözlem, ölçüm veya olaylardan elde edilen ham ve işlenmemiş gerçeklerdir, tek başına anlam taşımaz.
• İşlenip anlam kazanan veri enformasyon olur.
• Bilgi edinim piramidinde alttan yukarı sıra: veri, enformasyon, bilgi, bilgelik.

Algoritma analizi ve Big-O

• Big-O, girdi büyüdükçe çalışma süresinin en kötü durumda nasıl arttığını, yani üst sınırı gösterir.
• Asimptotik gösterimler verimliliği işlemci hızından bağımsız ölçer.
• Bağlı listede doğrusal arama ortalama ve en kötü durumda O(n)'dir; çünkü doğrudan indeksle erişim yoktur.
• Dengeli İkili Arama Ağacında arama O(log n)'dir; her adımda adayların yaklaşık yarısı elenir.

İşaretçiler ve dinamik bellek

• İşaretçi bir değişkenin adresini taşır; önüne * konunca adresteki değere ulaşılır (dereference).
• -> operatörü, işaretçinin gösterdiği yapının üyesine erişmek için kullanılır.
• sizeof, bir veri tipinin bellekte kapladığı byte miktarını verir.
• new ile ayrılan belleğin delete ile iade edilmemesi bellek sızıntısıdır.
• Tek değişken delete ptr; ile, new ile oluşturulan dizi delete[] ptr; ile serbest bırakılır.

Diziler ve bağlı listeler

• Dizi elemanları bellekte ardışıktır; bu mekansal yerellik sayesinde önbellek isabet oranı artar.
• Bağlı liste düğümleri bellekte bitişik olmak zorunda değildir; işaretçilerle bağlanır ve boyutu çalışma sırasında değişebilir.
• Tek yönlü listede düğüm, veri ve sonraki düğümü gösteren next alanından oluşur.

Tek yönlü liste işlemleri

• Baştaki eleman silinirken önce baş düğüm geçici işaretçide saklanır; aksi halde adres kaybolup bellek sızıntısı olur.
• Tek elemanlı listede son düğüm silinince head (varsa tail) nullptr olmalıdır.

Çift yönlü bağlı liste

• Her düğümde veri, prev (önceki adres) ve next (sonraki adres) alanları bulunur.
• Tek yönlüye göre asıl üstünlüğü geriye doğru dolaşmaya izin vermesidir; prev biraz ek bellek harcar.
• Tarayıcı geri-ileri düğmeleri ve LRU önbellek uygulamalarında kullanılır.
• Ters çevirmede next ve prev yer değiştirir; döngü sonunda son ziyaret edilen düğümden head güncellenir.
• Arama yine O(n)'dir.

Dairesel bağlı liste

• Son düğümün next işaretçisi null yerine head'i gösterir; halka oluşur.
• Sona gelince otomatik başa dönülür ve sürekli dolaşım sağlanır.
• Round Robin CPU zamanlayıcılarında kullanılır.
• Ek işaretçi gereksinimini ortadan kaldırmaz.

Yığın ve kuyruk

• Yığın (Stack) tek uçtan (Top) çalışır ve LIFO düzenindedir: son giren ilk çıkar.
• Yığın; fonksiyon çağrıları, geri alma ve parantez eşleştirmede kullanılır.
• Kuyruk (Queue) FIFO düzenindedir: ilk giren ilk çıkar.
• Kuyrukta ekleme arka uçtan (rear), çıkarma ön uçtan (front) yapılır.

Veri (data)

Ölçüm, gözlem ya da olaydan gelen ham, işlenmemiş gerçeklerdir.

Enformasyon

İşlenerek anlam kazanmış veridir.

Big-O

Algoritmanın en kötü durumdaki büyüme eğilimini gösteren üst sınır gösterimidir.

Dereference (*)

İşaretçinin tuttuğu adresteki değere erişme veya onu değiştirme işlemidir.

Bellek sızıntısı

Dinamik ayrılan belleğin işi bitince iade edilmemesi sonucu alanın dolu kalmasıdır.

Mekansal yerellik

Komşu elemanların birlikte önbelleğe gelmesi; dizilerde verimi artırır.

Düğüm (node)

Bağlı listede veri ile bir ya da iki işaretçi taşıyan temel birimdir.

prev / next

Çift yönlü listede sırasıyla önceki ve sonraki düğümün adresini tutan alanlardır.

Dairesel liste

Son düğümün başa bağlandığı halka biçimli listedir.

LIFO

Son giren ilk çıkar; yığının çalışma ilkesidir.

FIFO

İlk giren ilk çıkar; kuyruğun çalışma ilkesidir.

İkili Arama Ağacı (BST)

Solda küçük, sağda büyük değerlerin durduğu ağaçtır; dengeliyse arama O(log n)'dir.

• LIFO yığına, FIFO kuyruğa aittir; sorularda bu eşleşme sık karıştırılır.
• delete ile delete[] ayrımına dikkat: tek değişken için delete, dizi için delete[].
• Bağlı listede arama O(n), dengeli BST'de O(log n)'dir; ikisini karıştırmamak gerekir.
• Silme sorularında önce düğümü geçici işaretçide saklama adımı ve boşalan listede head'in nullptr olması aranır.
• Çift yönlü listenin asıl üstünlüğü geriye gezinmedir; dairesel listenin yararı kesintisiz dolaşımdır.