Veriyapıları ve algoritmalar final imtihanı çözümü

Soru 0) Bir ağacın eleman sayısını bulan kodu yazınız (ağacın ikili ağaç olma zorunluluğu yoktur, ağaçtaki her düğümün çocuklarının bir dizide tutulduğunu kabul edebilirsiniz).(20 puan)

int elemanSayisi(node *tree){

if(tree==null)

return 0;

int sayi = 0;

for(int i =0;i<cocuklar;i++){

sayi += elemanSayisi(cocuk[i]);

}

sayi++;

return sayi;

}

Soru 1) Aşağıdaki şekilde bir adet başlangıç ve bir adet hedef düğümü alarak (Aldığınız bu düğümleri belirtiniz) aşağıdaki sorulara cevap veriniz. (30 puan)

1. BFS (Breadth first search, sığ öncelikli arama) ve DFS( Depth first search, derin öncelikli arama) yöntemleri ile dolaşma sonuçlarını yazınız.
   

Başlangıç A ve bitiş E olarak kabul edilmiştir.

BFS :

ACDFBE

DFS:

ABFDE

2. Kruskal ve Prims algoritmalarına göre asgari tarama ağacı (minimum spanning tree) sonuçlarının nasıl bulunduğunu adım adım gösteriniz.

Kruskal için en kısa düğümden en uzun düğüme doğru ağaç dolaşılır:

Yukarıdaki tabloda sağdaki sütun, o adımda alınan kenarı, soldaki sütun ise o ana kadar alınmış düğümleri gösterir. Soldaki sütunda – işareti ile farklı adalar ayrılmıştır.

Prims algoritması

Sırasıyla alınan kenarlar: A-C, C-D,C-F,A-B,B-E

3. Yukarıdaki sorularda verdiğiniz cevaplar ışığında, bu soru için, hangi algoritmaların daha başarılı olduğunu (DFS / BFS, Kruskal / Prims) açıklayınız.

DFS/BFS için aynıdır. Kontrol edilen komşu düğüm sayıları (adjacency list):

DFS: A 2, C 2, D 2, F 1, B 1 , toplam : 8

BFS: A 2, B 2, F 2, D 2 , toplam : 8

Kruskal / Prims için:

Kruskal algoritması daha hızlıdır.

Kontrol edilen kenarlar.

Kruskal algoritması, 5 kenar kontrol etmiştir.

Prims algoritması 13 kenar kontrol etmiştir. Kontrol edilen kenar sayıları aşağıda sıralanmıştır:

2,3,4,2,2 , toplam : 13

Soru 2) Çalıştığınız firmada, bir kelime işlem programı (örneğin MS Word benzeri bir program düşünebilirsiniz) üzerinde yapılan işlemlerin geri / ileri alınmasını sağlayacak (Undo/Redo) kodu yazmanız isteniyor. Bu programda birden çok kişi, birden çok zamanda metin üzerinde değişiklik yapabiliyor (kullanıcılar aynı anda birbirlerinde bağımsız değişiklikler de yapabilir). Sizden istenen herhangi bir kişinin, herhangi bir zamanda yaptığı herhangi bir işlemi geri alabilmeniz için, programda yapılan işlemlerin tutulduğu uygun bir veri yapısı tasarlamanız. Tasarımınızı çizip kullandığınız veri yapısı modelini açıklayınız. (25 puan)

typedef struct node {

char * kullanici;

char * tarih;

islem * i;

node * next;

node * prev;

};

Yukarıdaki düğüm tasarımının amacı, veri yapımızın her düğümünde yapılan işlemi (ki bu işlemin detayı bizi ilgilendirmediği için bir gösterici olarak bırakılmıştır) kimin yaptığını ve tarihi / saat bilgisini tutmaktır.

Yukarıdaki yapı, ayrıca çift bağlı liste (doubly linked list) olarak tanımlanmıştır. Tek bağlı liste olarak da tasarlanabilir di.

Yukarıdaki liste, bir yığın (stack) olarak kullanılacaktır. İşlemler hem geri, hem de ileri alınabileceği için iki yığın gerekmektedir. İşlemler sadece geri alınsa ve geri alınan işlemler bir daha kullanılmamak üzere silinseydi tek yığın yeterli olurdu.

Şekilde görüldüğü üzere, yen işlemler 1. Yığına girerken herhangi bir geri alma işlemi varsa, işlemler 1. Yığından 2. Yığına taşınmakta. İleri alma işlemi ise, 2. Yığından 1. Yığına geri işlemleri yüklemekte.

Yeni işlem geldiğinde ayrıca 2. Yığındaki bilgiler silinerek artık işlemin tekrarlanması engellenebilir (Bu kısım şart olmamakla birlikte güncel programlardaki undo /redo işlemi bu şekilde çalışır)

Yukarıdaki geri / ileri alma işlemini tasarladıktan sonra kişi ve tarih bazlı geri alma tasarımını yapmamız gerekiyor. Bunun için ilave bir indeks oluşturup yığın üzerine bağlıyoruz:

Yukarıdaki şekilde görüldüğü üzere ilave bir ağaç kodlaması ile, yığın üzerindeki bazı düğümleri (node) bağladık. Bu düğümlere kolay erişimi sağlayan bir indekstir ve bir kişinin yaptığı işleme erişilmek istendiğinde, ağaç üzerinde aranıp ardından, yığın üzerinde, bulunan bu düğüme kadar geri alam işlemi yapılabilir.

Benzer bir ağacın, tarih için oluşturulması yeterlidir.

Soru3) Aşağıda bir dizi içerisinde verilen sayıları yığın ağacı (heap) aracılığı ile sıralayınız. Sıralama işlemi sırasında dizideki değişiklikleri adım adım gösteriniz. (öğrenci numaranızın son rakamı çift ise büyükten küçüğe, tek ise küçükten büyüğe sıralayınız) (25 puan)

int a[6] =  5,12,20,18,4,3

Sor büyükten küçüğe sıralama olarak yapılacaktır. Küçükten büyüğe sıralama için aşağıdaki adımların tersten yapılması yeterlidir.

Sıralamayı büyükten küçüğe göre yaptığımıza göre, min heap yani küçükten büyüğe olacak.

Öncelikle heap inşa edilir. Mevcut durum aşağıdaki şekildedir:

Heap inşa edilişi yukarıdaki şekilde sırasıyla gösterilmiştir. Aynı sıra ile dizideki değişim aşağıda gösterilmiştir:

5,12,20,18,4,3

5,4,20,18,12,3

4,5,20,18,12,3

4,5,3,18,12,20

3,5,4,18,12,20

Yukarıdaki inşa işleminden sonra sıralamaya geçilebilir.

İlk alınan sayı 3, heap’in en sonuna yerleştirilir ve geri kalan sayılar kendi arasında yeniden heap halini alır:

5,4,18,12,20 ,3

4,5,18,12,20 ,3

İkinci sayı alınıp heap yeniden inşa edilir

5,18,12,20 ,3,4

Üçüncü sayı alınır:

18,12,20 ,3,4,5

12,18,20 ,3,4,5

Dördüncü sayı:

18,20 ,3,4,5,12

Beşinci sayı:

20, 3,4,5,12,18

Son sayı:

3,4,5,12,18,20

Görüldüğü üzere dizi sıralanmıştır. Yukarıdaki bu adımlar heap çizimi üzerinde aşağdaki şekilde gösterilmiştir.

“Programcılık %10 bilim, %20 yaratıcılık ve %70, yaratıcılığın bilimle çalışmasına çalışmaktır.”