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

Ücretsiz yazdırılabilir Veri yapıları çalışma kâğıdı: kolaydan sınav düzeyine 8 soru ve cevap anahtarı. Yazdırın ya da PDF olarak kaydedin.

Yeni çalışma kâğıdıİpuçlarıyla çevrimiçi çalışın

Öğretmenler için: sınıfta ücretsiz yazdırılabilir, çoğaltılabilir ve kullanılabilir. Her yeni çalışma kâğıdında yeni değerler ve kendi cevap anahtarı vardır. Ders sayfanızda ExamProblems bağlantısı vermeniz bizi memnun eder.

Ad: ____________________   Tarih: ____________

1.Kolay

Bir graf şunlardan oluşur:

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

Karma tablosunda çakışma (collision) nedir?

  1. Aİki farklı anahtarın aynı indekse eşlenmesi
  2. BTablonun belleğinin tükenmesi
  3. Cİki eşit anahtarın iki kez saklanması
  4. DBir anahtarın hiç karma değerinin hesaplanamaması
3.Kolay

Karma fonksiyonu bir karma tablosunda ne yapar?

  1. AKaç anahtar saklandığını sayar
  2. BBir anahtarı tablodaki bir indekse eşler
  3. CTablodaki değerleri şifreler
  4. DTablodaki anahtarları sıralar
4.Orta

Hangi çakışma çözümleme yöntemi çakışan anahtarları aynı kovadaki bir listede saklar?

  1. AAyrı zincirleme (separate chaining)
  2. BKaresel sondalama
  3. CDoğrusal sondalama
  4. DÇift karma
5.Orta

Bir kuyruk iki yığınla gerçekleştiriliyor: "in" yığınına push edilir, "out" yığınından pop edilir ve "out" boşaldığında "in"den doldurulur. İşlem başına amortize maliyet nedir?

  1. AO(log n)
  2. BO(1)
  3. CO(n)
  4. DO(n²)
6.Orta

İkili arama ağacında en küçük anahtarı nasıl bulursunuz?

  1. ASağ çocuk kalmayana kadar kökten itibaren sağ çocukları izleyerek
  2. BSol çocuk kalmayana kadar kökten itibaren sol çocukları izleyerek
  3. CHer yaprağı ziyaret edip karşılaştırarak
  4. DYalnızca köke bakarak
7.Zor

Öbek sıralaması (heapsort) hakkında hangi ifade doğrudur?

  1. AKararlıdır ve O(n) ek bellek gerektirir
  2. BYerinde, en kötü durumda O(n log n) sürede sıralar, ancak kararlı değildir
  3. CHer girdide O(n) sürede çalışır
  4. DEk depolama olarak bir ikili arama ağacına ihtiyaç duyar, bu yüzden O(n) ek bellek kullanır
8.Zor

Rütbeye göre birleştirme ve yol sıkıştırma kullanan union-find (ayrık küme) yapısının işlem başına amortize maliyeti nedir?

  1. AO(n²)
  2. BO(n)
  3. CO(α(n)), ters Ackermann fonksiyonu; pratikte sabittir
  4. DTam olarak O(log n)

Cevap anahtarı

  1. 1. D · Kenarlarla birbirine bağlı köşeler (düğümler)
  2. 2. A · İki farklı anahtarın aynı indekse eşlenmesi
  3. 3. B · Bir anahtarı tablodaki bir indekse eşler
  4. 4. A · Ayrı zincirleme (separate chaining)
  5. 5. B · O(1)
  6. 6. B · Sol çocuk kalmayana kadar kökten itibaren sol çocukları izleyerek
  7. 7. B · Yerinde, en kötü durumda O(n log n) sürede sıralar, ancak kararlı değildir
  8. 8. C · O(α(n)), ters Ackermann fonksiyonu; pratikte sabittir

Tam adım adım çözümler: bu konuyu examproblems.com’da çalışın.