14.01.

2021
Süre: 50dk
2020 -2021 Güz Dönemi Veri Yapıları Dersi Final Sınavı

1- Öğrenci numaranızın son rakamına göre soruda kullanılacak diziyi seçiniz. Öğrenci numaranızın
sondan bir önceki rakamına göre çiftse soldan sağa, tek ise sağdan sola doğru ağaca yerleştiriniz. (Sıfır
rakamı çifttir.)
Örnek: Öğrenci numarası B121210037 ise 7 numaralı veri dizisini seçilecektir. Öğrenci numarasındaki
sondan bir önceki rakama da 3 yani tek olduğu için sağdan sola doğru {51, 4, 10, 34, 81, 77, 64 }
olacak şekilde ağaca yerleştirilir.
Verilen dizinin elemanları sırasıyla başlangıçta boş bir ikili arama ağacına (AVL olmayan binary search
tree) eklenirse oluşacak ağacı çizip üzerinde postorder, Preorder ve Levelorder traversal
(dolaşma) uygulayıp işlem yapılan düğümleri sırasıyla belirtiniz. Not: Kullanılan elemanlar öğrenci
numarasına aitse puan verilecektir.

Numaranızın Veri dizisi

son rakamı
0 77 66 74 75 34 72 65
1 20 48 53 12 51 21 72
2 39 28 23 81 32 21 61
3 62 88 25 68 94 37 63
4 87 38 67 41 61 67 26
5 54 61 89 88 11 99 1
6 47 77 73 93 38 30 54
7 64 77 81 34 10 4 51
8 73 24 73 93 12 61 44
9 11 61 10 99 83 90 81
2- Öğrenci numaranızın son rakamına göre soruda kullanılacak diziyi seçiniz. Öğrenci numaranızın
sondan bir önceki rakamına göre çiftse soldan sağa, tek ise sağdan sola doğru ağaca yerleştiriniz.
Öğrenci numaranızın sondan iki önceki rakamına göre çiftse Min-Heap, tek ise Max-Heap ağacına
eklenecektir. (Sıfır rakamı çifttir.)
Örnek: Öğrenci numarası B121210037 ise 7 numaralı veri dizisini seçiyorsunuz. Öğrenci numarasındaki
sondan bir önceki rakama da 3 yani tek olduğu için sağdan sola doğru {60, 73, 56, 16, 91, 79 } olacak
şekilde ağaca yerleştirilir. Sondan iki önceki rakam 0 ve çift olduğu için Min-Heap seçilecektir.
Verilen dizinin elemanları sırasıyla başlangıçta boş bir heap ağacına eklenirse,
a) oluşacak ağacı ara işlem adımlarını belirterek çiziniz.
b) ağacın durumunu dizi üzerinde gösteriniz.
c) kökün silinmesi sonucunda, yeni ağacın şeklini ara işlem adımlarını belirterek çiziniz.
Not: Kullanılan elemanlar öğrenci numarasına aitse puan verilecektir.
Numaranızın Veri dizisi
son rakamı
0 54 78 18 63 79 4
1 50 62 22 16 78 76
2 91 56 94 55 39 32
3 85 80 26 64 21 68
4 45 91 75 70 73 6
5 77 86 56 36 97 43
6 57 56 97 30 44 2
7 79 91 16 56 73 60
8 25 19 51 87 5 10
9 29 85 50 23 38 11
 14.01.2021
Süre: 50dk
2020 -2021 Güz Dönemi Veri Yapıları Dersi Final Sınavı

3- Aşağıda verilen tablodaki öğrenci numaranızın son rakamını kullanarak seçtiğiniz string ifadeyi
Lempelziv kodlama ile (LZ78) kodlayınız. Öğrenci numaranızın sondan bir önceki rakamına göre eğer
çift ise soldan sağa, tek ise sağdan sola kodlayınız. Kodlamada sözlük oluşturularak, elde edilecek
string ifadenin nasıl oluşturulduğu adım adım aşağıdaki tablo kullanılarak gösterilmelidir. String
sıkıştırılmadan önce kaç bit yer kaplamaktaydı. Sıkıştırıldıktan sonra kaç bit yer kaplamaktadır
hesaplayınız.

(sıra no= öğrenci_no % 10)

4- Şekilde verilen ikili arama ağacı (AVL olmayan) üzerinde, öğrenci numaranızın son rakamına göre
istenen işlemi gerçekleştirecek kodu C++ dilinde yazınız. Sadece verilenler kullanılarak işlem
gerçekleştirilecektir, hazır fonksiyon kullanılmayacaktır. Gerekli kod satırları yazılacaktır.
Sıra Gerçekleştirilecek İşlem
No
0 K verisinin ağaçtan silinme işlemi
1 E verisinin ağaçtan silinme işlemi
2 O verisinin ağaçtan silinme işlemi
3 Ağaca yeni veri eklenme işlemi, Veri Kullanıcıdan
alınacaktır.
4 Ağaçta veri arama işlemi, Veri Kullanıcıdan
alınacaktır.
5 Aranan verinin ebeveyn düğümünün bulunması, Veri
Kullanıcıdan alınacaktır.
6 Aranan veriden küçük ve aranan veriye en yakın olan
verinin ağaçtan silinme işlemi
7 Aranan veriden büyük ve aranan veriye en yakın olan
verinin ağaçtan silinme işlemi
8 Aranan verinin yaprak olma kontrolü, Veri
Kullanıcıdan alınacaktır.
9 Aranan verinin ağaçtaki en küçük veya en büyük veri
değilse ekrana false yazılması aksi halde true
yazılması, veri kullanıcıdan alınacaktır.
 14.01.2021
Süre: 50dk
2020 -2021 Güz Dönemi Veri Yapıları Dersi Final Sınavı

5- Aşağıdaki problemler için çözüm önerinizi yazınız? Problemi öğrenci numaranızın son rakamına göre
seçiniz.

Sıra Problem
No
0 Öğrencilerin yaşına göre tutulan bir ikili arama ağacında aynı isimde bir öğrenci var mı kontrolü
1 Dinamik olarak düğüm verisinin değiştirildiği ikili arama ağacında BST olma durumunun yitirilmesi
2 100 kişilik öğrenci verisinde hızlı bir arama yapılmak istenmektedir. Detaylı çözüm
3 Heap ağacı bağıl olarak gerçekleştirilmek istenmektedir. En optimum tasarım nasıl olmalıdır.
4 Huffman ağacı dizi üzerinde gerçekleştirilirse karşılaşılacak problemler ve çözümler.
5 İkili ağaçta tek çocuğa sahip düğüm sayısını bulmak için çözüm yöntemi
6 İkili ağaçta iki çocuğa sahip düğüm sayısını bulmak için çözüm yöntemi
7 Bir ağaç veri yapısının, ikili arama ağacı olup olmadığını kontrol etmek için çözüm yöntemi
8 Bir ikili ağaç veri yapısının, AVL ağacı olup olmadığını kontrol etmek için çözüm yöntemi
9 Kuyruk veri yapısı, yığıt kullanılarak gerçekleştirilmek isteniyor. Çözüm yöntemi

Açıklamalar:

- Cevap kağıdınızda, Adınız, Soyadınız, Numaranız, Şubeniz ve İmzanız mutlaka olmalıdır.

- Cevaplar kurşun kalem ile A4 kağıdına el yazısı ile yazılıp daha sonra taranıp SABİS’e
yüklenmelidir.
- Herhangi bir soru cevabının kopya olması durumunda her iki tarafta final sınav notundan sıfır
alacaktır.
- Mail üzerinden kesinlikle gönderim kabul edilmemektedir.
- Hangi sorunun cevabının yazıldığı cevap kağıdında açıkça belirtilmelidir.
- Her soru 20 puandır.