Cevaplı Veri yapıları çalışma kâğıdı

Tek yönlü bağlı listede her düğüm şunları içerir:

1. AVeri ve bir sonraki düğüme referans
2. BVeri ve diğer tüm düğümlere referanslar
3. CVeri ve bir indeks
4. DYalnızca veri

n düğümlü bir ağacın kaç kenarı vardır?

1. A2n
2. Bn + 1
3. Cn − 1
4. Dn

Bir graf şunlardan oluşur:

1. AYalnızca bir kök ve yapraklar
2. BYalnızca anahtarlar ve karma değerleri
3. CKenarlarla birbirine bağlı köşeler (düğümler)
4. DSatırlar ve sütunlar

7 boyutlu bir karma tablosu h(k) = k mod 7 ve doğrusal yoklama (linear probing) kullanıyor. 10 eklendikten sonra 17 nerede saklanır?

1. Aİndeks 6
2. Bİndeks 0
3. Cİndeks 4
4. Dİndeks 3

Bir dizide saklanan ikili min-öbekte (indeks 0'dan başlar) i indeksindeki düğümün çocukları hangi konumlardadır?

1. A2i ve 2i + 1
2. Bi/2 ve i/2 + 1
3. Ci + 1 ve i + 2
4. D2i + 1 ve 2i + 2

n elemanlı bir dizinin ortasına bir eleman eklemenin maliyeti nedir?

1. AO(n), çünkü sonraki elemanlar kaydırılmalıdır
2. BO(n²), çünkü her eleman n kez taşınır
3. CO(log n), ikili arama nedeniyle
4. DO(1), çünkü indeks bilinmektedir

Bir nesne bir karma haritasında (hash map) anahtar olarak saklanıyor ve ardından karma fonksiyonunda kullanılan bir alanı değiştiriliyor. Olası sonuç nedir?

1. ANesne eski karma değerinin kovasında durduğu için onu arama başarısız olabilir
2. BAlan değiştiği anda harita bir hata fırlatır
3. CHiçbir şey değişmez, çünkü bir anahtarın karma değeri yalnızca program başlarken bir kez hesaplanır
4. DHarita anahtarı otomatik olarak yeni kovasına taşır

n sayılık bir dizi üzerindeki bir Fenwick ağacı (binary indexed tree) hangi işlemleri O(log n)'de destekler?

1. AÖnek toplamı sorgularını ve tek eleman güncellemelerini
2. BMedyanı O(1)'de bulmayı
3. CHerhangi bir konuma eleman eklemeyi
4. DDiziyi sıralamayı ve ikili aramayı