ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 6

İkili ağaç

Büyüklük-küçüklük

Pivot

En küçük elemanı bulma, en küçük elemanı silme ve ağaca eleman ekleme

Hash fonksiyonu

Ayrık Zincirleme

Ağaç veri yapısında bilinmesi gereken başlıca kavramlar şunlardır: Kök, dal, yol, yol uzunluğu, ebeveyn, çocuk, ağaç yüksekliği, düğüm yüksekliği, düğüm derinliği.

İkili ağaçlar, her bir düğümün en fazla 2 çocuğa sahip olabildiği ağaç türüdür. Bu veri yapısında ekleme, silme ve arama işlemleri çok hızlı bir şekilde yapılabilmektedir. Şekil verilen ağaçta A ve B düğümlerinin 2’şer çocuğu, D düğümünün 1 çocuğu vardır. C, E ve F düğümlerinin ise herhangi bir çocuğu yoktur. Bu ağaçtaki her bir düğümün en fazla 2 çocuğu bulunduğu için, gösterilen ağaç ikili ağaç sınıfına girer. Dolasıyla doğru cevap E seçeneğidir.

Bu örnekte var olan ağaca, 4 değerine sahip yeni bir düğüm eklenmektedir. Ekleme işleminde öncelikle kök düğümün değerine bakılır. Kök düğümün değeri 5 olup bu değer 4’ten büyüktür. Dolayısıyla yeni düğümü eklemek için sol alt ağaca gidilir. Sol alt ağacın kökünde yer alan düğümün değeri 2 olup bu değer 4’ten küçüktür. Yeni düğümü eklemek için sağ alt ağaca gidilir, sağ alt ağaç boş olduğu için yeni düğüm buraya eklenir. Dolayısıyla doğru cevap D seçeneğidir.

Verilen maddelerden I, II de belirtilen ifadeler doğrudur. III. ifadenin doğru tanımı şu şekilde olması gerekir: "Çıkarılacak düğümün 2 çocuğu var ise düğümün sağ alt ağacındaki en küçük değerli düğüm bulunur, bulunan düğüm ile çıkarılacak düğüm yer değiştirilir, düğüm hafızadan silinir." Dolayısıyla doğru cevap B seçeneğidir.

Verilen şekilde bir AVL ağacıdır. AVL (Adelson –Velsky – Landis) ağaçları, ikili arama ağaçlarının özel bir türüdür. Bu veri yapısında ağaç içerisindeki denge korunmakta, sol alt ağaç ile sağ alt ağaç arasındaki yükseklik farkı en fazla 1 olabilmektedir

Denge faktörleri hesaplandığında şekildeki gibi sonuç çıkmaktadır. Dolayısıyla doğru cevap A seçeneğidir.

Yığın ağacının en küçük elemanı ağaçtan çıkarılırken, ağacın son düzeyinin en sağındaki düğüm ile ağacın kökü yer değiştirilir. Yer değiştirme işleminden sonra en küçük elemanı içeren ağacın son düzeyindeki en sağ düğüm ağaçtan çıkarılır. Ağacın heap özelliğini korumak için, ağacın kökü üzerine aşağı yönlendirme işlemi uygulanır. Bu düğüm, ağaç içerisinde doğru yere gelinceye kadar çocukları ile karşılaştırılır ve değer olarak en küçük çocuk ile yer değiştirilir. Bu aşamalar dikkate alındığında doğru seçenek A şıkkı olur.

Özetleme tabloları ekleme, silme ve arama işlemlerinin çok hızlı bir şekilde yapılmasını sağlayan, verileri bir anahtar ve veri çifti şeklinde saklayan veri yapısıdır. Özetleme tablolarındaki genel çalışma mantığı, verileri N boyutlu bir dizide tutmak ve verilere erişim için sayı veya dizgiden oluşan anahtarı kullanmaktır. Özetleme tablosunda saklanacak bir veri için hash fonksiyonuna anahtar değeri gönderilir, fonksiyonun hesapladığı değer, verinin dizide tutulacağı indis olur. Dolayısıyla doğru cevap C şıkkıdır.

Fonksiyon A seçeneğinde doğru verilmiştir. C seçeneğindeki fonksiyon "Anahtar olarak dizgi değeri alan bir hash fonssiyonudur. Diğer şıklardakiler bir doğru bir fonksiyon oluşturmazlar. Dolayısıyla doğru cevap A seçeneğidir.

Açık adreslemede çatışma çözümü için kullanılan üç çeşit temel ikinci hash fonksiyonu bulunmaktadır: a. Doğrusal Sınama (Linear Probing): F(i)=i b. Karesel Sınama (Quadratic Probing): F(i)=i2 c. İkili Hash (Double Hashing): F(i)=i*Hash2(i) Dolayısıyla cevap B seçeneğidir.

Ağaç veri yapısı, verilerin birbirlerine temsili bir
ağaç oluşturacak şekilde bağlandığı hiyerarşik bir
veri modelidir. Bir ağaç düğümlerden ve düğümleri birbirine bağlayan dallardan meydana gelir.

Ağaç veri yapısında bilinmesi gereken başlıca kavramlar aşağıda listelenmiştir:
• Kök (Root): Bir ağacın en üst noktasında bulunan düğümdür.
• Dal (Edge): Düğümleri birbirine bağlayan kenara verilen isimdir.
• Yol (Path): Birbirleri ile bağlantılı dal dizisine yol adı verilir.
• Yol Uzunluğu (Length of a Path): Bir yolu oluşturan dal dizisindeki dal sayısıdır.
• Ebeveyn (Parent): Bir düğümden önce yer alan ve o düğüme bir dal ile bağlı olan
düğüme ebeveyn denir. Kök hariç her düğümün bir ebeveyni bulunmaktadır

Basit Bir Ağaç Yapısı
Gösterimi.

İkili ağaçlar, her bir düğümün en fazla 2 çocuğa sahip
olabildiği ağaç türüdür. Bu veri yapısında ekleme, silme
ve arama işlemleri çok hızlı bir şekilde yapılabilmektedir.