Süre 60 dakika, sınav açık kitaptır. Sınavda hiçbir şekilde fotokopi ve dersin sitesi dışında bilgisayar çıktısı kabul edilmeyecektir. Başarılar 

Soru 1) Aşağıda verilen kod için şıkları cevaplandırınız. (35 puan)

int topla(node *yapi,int boyut){

int sonuc=0;

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

sonuc += yapi.eleman(i);

}

return sonuc;

}

Yukarıdaki kodda yapi.eleman(int) fonksiyonu verilen parametredeki elemanın değerini döndürmektedir.

1. Yapı bir bağlı listeyse (linked list) N elemanlı bir liste için kaç kere listeye erişim olur?

n(n+1)/2

2. Yapı bir dizi (array) ise N elemanlı bir dizi için kaç kere diziye erişim olur?

n

3. Yukarıdaki fonksiyonda 10,000 eleman için hafızaya erişimin 3 saniye vakit aldığını düşünürsek, bağlı listede ve dizide 100,000 eleman için ne kadar vakit gerekir?

Dizi = 30sn, liste: 500000 sn

4. Yukarıdaki toplama fonksiyonunun bağlı liste ve diziden daha hızlı çalışması için nasıl bir veri yapısı önerirdiniz?

Listeye erişirken kaldığı yerden devam eden bir iteratör

Soru 2) Bir adet ağaç ve birde iki parametreli fonksiyon alan bir fonksiyon yazınız. Buna göre ağaçta bulunan bütün elemanlar bu fonksiyon ile accumulate edilerek (toplanarak) sonuçta tek bir sayı döndürülecektir.

Yukarıdaki örnek için topla fonksiyonu aşağıdaki şekilde olabilir:

int topla(int a, int b){

return a + b;

}

int acc(node * root){

if(root==NULL)

return 0;

return acc(root->left)+acc(root->right)+root->data;

}

Soru 2) iki adet yığın (stack) kullanarak bir çift yönlü sıra (double ended queue) kodlamanız isteniyor. Buna göre sıranın hem başından ekleme ve çıkarma hem de sonundan ekleme ve çıkarma işlemleri yapılabilecektir. Yığın için bir ADT (Abstract Data Type, Soyut Veri Tipi) yazıldığını ve pop ve push fonksiyonlarının hazır olduğunu kabul ediniz. Bu fonksiyonları kullanarak çift yönlü sıranın iki ucundan da ekleme ve çıkarma işlemi yapan 4 fonksiyonu kodlayınız. (30 puan)

soldaki yığına 1, sağdakine 2 dersek;

void pushSol(int data){

push1(data);

}

void pushSag(int data){

push2(data);

}

int popSol(){

if(!isEmptySol()) {

return pop1();

}

if(!isEmptySag()){

while(!isEmptySag())

push1(pop2());

return pop1();

}

int popSag(){

if(!isEmptySag()) {

return pop2();

}

if(!isEmptySol()){

while(!isEmptySol())

push1(pop1());

return pop2();

}

Soru 3) Bir bağlı yönlü dairesel olmayan graftaki düğümler için (connected directed acyclic graph) azami giriş derecesi (max inorder) 1 ve azami çıkış derecesi (max outorder) 2 olarak tanımlanıyor. Bu graf’ın içindeki elemanları seviye seviye ekrana basan bir kod yazınız. Yani örneğin üst seviyeden alta doğru gidiyorsanız üst seviyelerden birisi bitmeden bir alttaki elemanları basmayacak. Şayet alt seviyeden üste doğru gidiyorsanız alt seviyelerden birisi bitmeden üste gitmeyecek. (35 puan)

void agacbas(node *root){

for(int i =0;i<derinlik(root);i++)

seviyeBas(root,i,0);

}

void seviyeBas(node * root,int seviyeIstenen,int seviye){

if(root!=NULL&&seviyeIstenen>seviye){

seviyeBas(root->left,seviyeIstenen,seviye+1);

seviyeBas(root->right,seviyeIstenen,seviye+1);

}

else if(root!=NULL)

printf(“%d”,root->data);

}

“Bilgisayarların, bilgisayar mühendisliğindeki önemi, teleskopların astronomi biliminde kapladığı önemden daha fazla değildir. “
(E. W. Dijkstra)