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)*4 +1;
}

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.