Süre 90 dakika, sýnav kapalý kitaptýr.  Herkese baþarýlar J

Soru 0) Kullanýcýdan 10 tane sayý okuyup bu sayýlarýn en büyüðü ile en küçüðü arasýndaki farký bulan kodu yazýnýz. (10 puan)

Çözüm:

int sayi;

printf(�bir sayý giriniz�);

scanf(�%d�,&sayi);

int enbuyuk=sayi;

int enkucuk=sayi;

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

printf(�bir sayý giriniz�);

scanf(�%d�,&sayi);

        if(enbuyuk<sayi)

               enbuyuk=sayi;

        if(enkucuk>sayi)

               enkucuk=sayi;

}

printf(�fark:%d�,enbuyuk-enkucuk);

Soru1) Kullanýcýdan 10 tane sayý alýp bunlarý dairesel çift baðlý listeye (circular doubly linked list) koyan ve sonra bu sayýlarýn en büyüðü ile en küçüðü arasýndaki farký, bu listeyi parametre olarak alan bir fonksiyon ile bulunuz. (20 puan)

typedef struct node{

        int data;

        node * next;

        node * prev;

        };

void ekle(node *root){

    node * iter=root;
        for( int i = 0;i<10;i++){
               int sayi;
               printf(�sayi giriniz�);
               scanf(�%d�,&sayi);
             iter->data = sayi;
             iter->next = (node*)malloc(sizeof(node));
             iter->next->prev = iter;
             iter=iter->next;
         }
        iter->next = root;
        root->prev=iter;
}
 
void hesapla(node *root){
        int enbuyuk=root->data;
        int enkucuk=root->data;
        node * iter = root->next;
        while(iter!=root){
               if(iter->data > enbuyuk)
                       enbuyuk = iter->data;
               if(iter->data < enkucuk)
                       enkucuk = iter->data;
               iter=iter->next;
        }
        printf(�fark:%d�,enbuyuk-enkucuk);
}
void main(){
        node * root = (node * ) malloc(sizeof(node));
        root->prev=NULL;
 
        ekle(root);
        hesapla(root);
}

Soru2) Bir baðlý listenin bütün elemanlarýnýn baðlý liste olduðunu düþünün (listeler listesi, list of list). Bu baðlý listenin bütün elemanlarýný ve elemanlarýnýn elemanlarýný sýralayan bir yöntem geliþtiriniz. (Ýpucu, bu soru için derste görülen map, accumulate ve filter fonksiyonlarýný hazýr kabul edip kullanabilirsiniz. Ayrýca sýralama için kullanacaðýnýz fonksiyonun ismini yazarak bu fonksiyonu hazýr kabul edebilirsiniz.)  (10 puan)

Çözüm:

map(liste,sirala);

liste: List of listi gösteren pointer

sirala: Herhangi bir siralama fonksiyonu

map: derste iþlenen map fonksiyonu

Soru3) Aþaðýda bir grafik verilmiþtir:

a) Bu grafikteki kare sayýsý 5tir. Buna göre verilen bir kare grafik diziliminin boyutuna göre (n x n) kaç kare içereceðini hesaplayan fonksiyon yazýnýz. (7 puan)

b) Yukarýdaki grafikte bulunan her düðüm bir baðlý liste ile kodlansaydý. Örneðin aþaðýdaki struct kullanýlarak:

typedef struct node{

node *sol;

node *sag;

node *yukari;

node *asagi;

};

Bu durumda yukarýdaki grafikte kaç kare olduðunu bulan kodu yazýnýz. (13 puan)

c) Döngü (Cycle) : Bir düðümden baþlayarak tekrar kendisine dönen herhangi bir rota. Rotadaki elemanlar ayný olduðu sürece hangi elemandan baþlandýðýnýn veya elemanlarýn sýrasýnýn önemi yoktur örneðin (a,b,c) ile (b,c,a) ve (c,b,a) ayný döngülerdir ancak (a,b,c) ile (b,c,d) farklý döngülerdir.

Yukarýdaki tanýma göre yukarýdaki yapýda verilen bir grafikte kaç cycle olduðunu bulan kodu yazýnýz (ipucu: bu grafikte 13 adet farklý döngü (cycle) bulunmaktadýr) (20 puan)

Çözüm:

a) recursive bir problemdir. Buna göre örneðin 3x3lük bir ýzgarada 4 adet 2x2lik ýzgaradaki kadar kare ve ilave olarak 1 kare daha bulunacaktýr.

int kare_sayisi(int n){
        if(n==1)
               return 1;
        return kare_sayisi(n-1)+n*n;
}

b) yapý kullanarak arama yapýlacaktýr, basitçe bir karenin boyutu öðrenilerek yukarýdaki fonksiyondan faydalanabilirsiniz. O halde bu yapýdaki bir ýzgaranýn boyutunu bulan fonksiyonu yazalým. Fonksiyona ýzgaranýn sol üst köþesini gösteren bir pointer verildiði düþünülürse

int boyut_bul(node *root){
        int boyut=0;
        while(root->sol!=null){
               boyut++;
               root=root->sol;
        }
        return boyut;
}

þimdi ilave olarak bu fonksiyonu kullanarak a, þýkkýnda yazýlan fonksiyonu kullanalým:

        kare_sayisi(boyut_bul(root));

c) yapýnýn özelliðinden faydalanarak arama yapýlacaktýr. Öncelikle grafik üzerinde bütün yönlere arama yapan ve bu aramalar sonucunda her gezdiði düðümü bir stacke atan ve her düðümdeki 4 farklý yön için içinde tuttuðu listeye bu stackleri elkeyen recursive bir kod yazalým:

liste * arama ( node *dugum , node *baslangic, liste *dolasilan){
        if(baslangic == dugum) // sayet baslangica donduysek stacki dondur
               return dolasilan;
        liste *iter= dolasilan;
        while(iter->next!=NULL)
               push(iter->stack,dugum);
        insert(liste,arama(liste->sol,baslangic,dolasilan));
insert(liste,arama(liste->sag,baslangic,dolasilan));
insert(liste,arama(liste->yukari,baslangic,dolasilan));
insert(liste,arama(liste->asagi,baslangic,dolasilan));       
}

Yukarýdaki kod dikkatlice okunursa, sonuçta bir linked list tutar. Bu koddaki linked listin her elemaný stacktir. Þayet baþlangýç düðümüne ulaþtýysa listeyi döndürür, þayet ulaþamadýysa Stacklerin içerisine ise kendisini yazar ve 4 farklý yön için iþlem yapar. Her yönden gelen sonucu ise kendisindeki listede birleþtirir.

Bu kodda kullanýlan yapý aþaðýdaki þekilde olabilir:

typedef struct stack{
        node * bilgi;
        stack * next;
};
 
typedef struct dolas_liste{
        stack * dolasilan;
        dolas_liste*next;
};

Stack içeriklerini karþýlaþtýran kodu yazalým:

int stack_karsilastir (stack *a, stack *b){
        while(pop(a)==pop(b)); // stacklerden biri bitine veya içeriði eþit olmayana kadar dön
        return( top(a) == NULL) && (top(b) == NULL) ; // iki stack de boþ mu bak sonucu döndür
}

Yukarýdaki kod verilen iki stackin içeriðini karþýlaþtýrýr.

Sonuç olarak her yönde farklý bütün alternatifleri dolaþan bir kodumuz ve bu kodun sonucunu stack listesinde tutan fonksiyonumuz yukarýda yazýldý. Ayrýca stack içeriklerini de karþýlaþtýran kod yukarýda bulunuyor. Dolayýsýyla þayet stack içeriði farklý dolaþma ihtimalleri varsa bunlar birbirinden farklý döngülerdir (lütfen baþlangýçta bittiðini hatýrlayalým).

int yolsay(node * dugum){
        dolas_liste gecici = arama(root,root,null); // baþlangýçta, baþlangýþ ve liste ayný ve stack boþ
        dolas_liste *temp = gecici;    
while(temp->next!=null){ //listedeki her eleman diðer bütün elemanlar ile karþýlaþtýrýlacak n2lik iþlem demek
        dolas_liste *temp2=gecici;
        while (temp2->next!=null){
               if(stack_karsilastir(temp,temp2){// þayet ayný iki liste bulursan
                       delete(gecici,temp2); //bulunan stack listesindne eþi bulunan stack siliniyor
               }
        }
}
}

Sonuçta yukarýdaki fonksiyon ile ayný stackten sadece 1 tane kalmasý saðlanýyor (baþlangýç ve bitiþi ayný olan (bitiþi baþlangýç olan) döngülerden).

Dolayýsýyla sayý bu listedeki eleman sayýsýdýr. Bunu bulan kod:

int liste_eleman_sayisi(dolas_liste *node){
        int sonuc=0;
        while(node->next!null) sonuc++;
        return sonuc;
}

geriye bir baþlangýç noktasýndan baþlanarak ve kendisine geri dönerek dolaþýlabilecek bütün döngü sayýsýný diðer noktalardan da saydýrmak kalýyor bunu yapan kod (yine recursive olarak):

int graf_dolas(node * graf){
        int dongu_sayisi=0;
 
        dongu_sayisi += graf_dolas(graf->sag);
        dongu_sayisi += graf_dolas(graf->sol);
        dongu_sayisi += graf_dolas(graf->yukari);
        dongu_sayisi += graf_dolas(graf->asagi);
        return dongu_sayisi;
}

Yukarýdaki kodlarda unutulmuþ bir nokta recursive kodlarýn dolaþýlan düðümlere tekrar gitmesidir. Bunu engellemek için ilk baþta verilen node struct�ýna dolasýldý gibi bir int eklemek ve dolaþýlanlarýn bir daha dolaþýlmamasýný saðlamaktýr.

Soru 4) Bir firmada programcý olarak çalýþan Ali�ye verilere daha hýzlý eriþilmesi için ikili aðaç kullanmasý söyleniyor. Ali, göstericileri (pointers) bilmediði için bu aðacý dizi kullanarak tutmaya çalýþýyor ve bir dizi üzerinde ikili aðacýn anahtarlarýný tutarak bu aðacýn ilgili elemanýna eriþmeyi baþarýyor.

a) Siz bir ikili aðacý bir dizi üzerinde nasýl tutardýnýz? Þekiller, örnekler ve formüller yardýmý ile açýklayabilirsiniz. (5 puan)

b) Ali�ye, siz göstericileri öðrettikten sonra, Ali�nin eskiden tutmuþ olduðu diziyi bir ikili aðaca nasýl dönüþtürürdünüz? (10 puan)

c) Göstericileri öðrenen Ali aþaðýdaki þekilde bir aðaç üzerinde her seviyeye daha hýzlý eriþim yapmayý hedefleyen bir baðlý liste kullanmak istiyor bu baðlý listeyi kullanarak sýð arama (breadth first search) yapacak olursanýz klasik dolaþma (traverse) algoritmalarý dýþýnda nasýl bir algoritma önerirdiniz?  (bu baðlý liste için, dairesel liste, çift baðlý liste gibi alternatifleri önerebilirsiniz)(5 puan)

Çözüm:

a) Çözüm olarak ikili aðacý bir diziye dönüþtürmenin yolunu bulmak gerekiyor. Dolayýsýyla ikili aðaçta bir elemana eriþildiðinde aslýnda dizinin bir elemanýna eriþilecek. Hepimizinbildiði üzere dizilerde gösterici kullanamýyoruz bunun yerine dizilerin sayaçlarý (indexer) bulunuyor ve bir diziye ilgili sayacý ile (indis) ulaþýlabiliyor. Bu durumda ikili aðacýn sayaç numarsýna dönüþmesi gerekir. Aþaðýda bir aðaþ ve aðacýn dizi karþýlýðý verilmiþtir:

1

2

3

4

5

6

7

�

Dikkat edilirse dengeli (Balanced) bir aðaç için 2d � 1  (d : derinlik) elemanlý bir dizi gerekmektedir. Dolayýsýyla Ali�nin ilk problemi olan dizi boyutu bu þekilde hesaplanýr. Ardýndan her eriþme iþleminde sola eriþim 2n, saða eriþim 2n +1 formülü ile hesaplanýr (n: düðüm numarasý). Bu hesap da eriþilen elemanýn dizideki yerini verir.

Örneðin, sorunun c þýkkýnda verilen aðacý düþünelim. Bu aðaçta 7 sayýsý aransýn. Önce aðacýmýzýn diziye dönüþmüþ halini yazalým:

1	2	3	4	5	6	7
10	5	15	2	7	13	17

Önce roota bakýlacak. bu durum dizinin ilk elemaný demek oluyor. Ýlk eleman 10 ve 7, 10�dan küçük o halde sola gidilecek ve sol hesaplamasýnda 2.1 formülü kullanýlýyor (1, düðüm no) ve 2 sayýsýna ulaþýlýyor. Sayý 2. eleman olan 5 ile karþýlaþtýrýlýyor. 7 sayýsý, 5�ten büyük o halde aðacýn saðýna gidilecek. Saðýný bulmak için 2n+1 formülü kullanýlýyor, düðüm sayýmýz 2 olduðu için 2.2+1 = 5 sayýsýna ulaþýlýyor. dizinin 5. elemaný 7dir ve sayýya ulaþýlmýþtýr.

Bu iþlemde dengeli bir aðaç örnek alýndýðý için boþ deðer bulunmamýþtýr, boþ deðer olarak null konulmasý sorunu çözer ve þayet null deðerine ulaþýlýyorsa veya aðacýn boyutu dýþýnda bir elemana ulaþýlýyorsa bu sayý yoktur demek yeterlidir.

C dilinde bu durum aþaðýdaki þekilde yazýlabilir.

ara (int * dizi,int boyut,int sayi){
        int indis=0; // C dilinde diziler 0dan baþlar
        while(indis < boyut || dizi[indis]!=null){
        if(dizi[indis]==sayi){
               printf(�bulundu�);
               break;
        }
        else if(sayi < dizi[indis])
               indis=(indis+1) * 2 -1; // Cdilinde diziler 0�dan baþladýðý için önce normal indise çevrilmeli
        else
               indis = (indis+1) *2 ;
        }
}

Ýnsert ve delte fonksiyonlarý içinde benzer eriþim yöntemleri kullanýlabilir. Ayrýca silinen eleman yerine null konulacaktýr.

b) bu þýk için bir önceki þýkta yapýlan iþlem tersine çevrilerek:

node * agacyap ( int * dizi , int boyut,int indis){
        node * sonuc = (node * ) malloc(sizeof(node));
        sonuc->data = dizi [0];
 
        sonuc->sol = agacyap(dizi,boyut,(indis+1)*2-1);
        sonuc->sag=agacyap(dizi,boyut,(indis+1)*2);
        return sonuc;
}

c) Bu þýk için yeni bir breadth first search yöntemi istenmiþtir. Buna göre baðlý listelerden faydalanarak her seviyedeki düðümler bastýrýlýp daha sonra bir alt seviyeye geçmek mümkündür. Baðlý listeler olmasaydý bu yapýnýn çalýþmasý imkansýzdýr. Bu yapýnýn daha saðlýklý çalýþmasý için dairesel (circular) baðlý liste kullanýlmasý daha kolay olur (bu sayede bulunulan seviyedeki her düðümün basýldýðýndan emin olunmuþ olunur. Ayrýca bir problem olan eksik eleman durumu anlaþýlabilir. Þöyleki, örneðin baðlý liste tam dolu olmasýn bu durumda herhangi bir seviyede eksik eleman olacak ve bu eleman deðeri listede null olarak görülecek. Dolayýsýyla bu elemanýn  sonrasýndaki (next) elemana da eriþielemeyecek. Bu durumun anlaþýlmasý çok önemlidir. Dairesel baðlý liste bize bu imkaný da sunar.

Bu durumda listenin devamý için bir üstteki köke çýkýlýp bir aþaðý inilecektir (bazý durumlarda 2,3,4 gibi sayýlarda yukarý çýkýlmasý da gerekebilir) tam çözüm olarak aðacýn köküne kadar çýkýlmasý gerekebilir. Bu durumda þayet hala bir sonraki düðüm bulunamýyorsa bir sonraki düðüm yok demektir yorumu yapýlarak aðacýn daha alt seviyesine geçileiblir.