Veri Yapıları ve Algoritmalar: hızlı tekrar paketi

Formül kâğıtları, her konunun temel yöntem adımları ve 6 alıştırma sorusu; tam çözümler en sonda.

Yeni sorularDerse dön

Yazdırma penceresinde, bir kopyayı cihazınızda saklamak için “PDF olarak kaydet” seçeneğini seçin.

1Formüller ve yöntemler

Graf kuramı

El sıkışma lemması
Σ deg(v) = 2|E|
Tam graflar
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Düzgün (regüler) graf
|E| = n·k/2
Ağaç ve orman
|E| = n − 1, |E| = n − c
Ağacın yaprakları
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
devre: tüm derecelerin çift olması; yol: tam olarak 2 tek derece
Kn içindeki Hamilton devreleri
(n − 1)!/2
Dijkstra güncellemesi
d(v) = min(d(v), d(u) + w(u, v))
L uzunluğundaki gezintiler
(Mᴸ)ij

Yöntem

  1. Her köşenin derecesini yazın; dereceler toplamı kenar sayısının iki katıdır.
  2. Euler sorularında grafın bağlantılı olduğunu denetleyin ve derecesi tek olan köşeleri sayın.
  3. Ağaçlarda n − 1 kenarı ve el sıkışma lemmasını kullanın.
  4. Dijkstra için geçici uzaklıkların bir tablosunu tutun ve her turda henüz kesinleşmemiş köşelerden en küçük uzaklığa sahip olanı kesinleştirin.
  5. En küçük kapsayan ağaç için kenarları ağırlığa göre sıralayın ve bir döngü kapatan her kenarı atlayın (Kruskal) ya da bir başlangıç köşesinden tek bir ağaç büyütün (Prim).

2Alıştırma soruları

1.Algoritmalar ve karmaşıklıkOrta

Amortize analiz neyi ölçer?

  1. ARastgele girdiler üzerinden beklenen maliyeti
  2. BEn kötü durumdaki bir işlem dizisi üzerinden işlem başına ortalama maliyeti
  3. CDizideki herhangi bir yerde bulunan en pahalı tek işlemin maliyetini
  4. DBir algoritmanın en iyi girdideki maliyetini
2.Algoritmalar ve karmaşıklıkZor

Bellman–Ford algoritması kaynaktan ulaşılabilen negatif ağırlıklı bir döngüyü nasıl tespit eder?

  1. ADijkstra algoritmasını iki kez çalıştırır ve iki uzaklık sonucunu karşılaştırır
  2. BHerhangi bir kenarın negatif ağırlığa sahip olup olmadığını kontrol eder
  3. CDerinlik öncelikli aramayla döngüleri sayar
  4. DV − 1 turdan sonra herhangi bir kenarın hâlâ gevşetilebilip gevşetilemediğini kontrol eder
3.Veri yapılarıOrta

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

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

Hangi dolaşım çifti, anahtarları birbirinden farklı bir ikili ağacı her zaman benzersiz olarak belirler?

  1. AYalnızca preorder
  2. BPreorder ve inorder
  3. CYalnızca seviye sıralı dolaşım
  4. DPreorder ve postorder
5.Graf kuramıOrta

K7 tam grafının kaç farklı Hamilton devresi (H) vardır? Yalnızca başlangıç köşesi ya da yönü farklı olan devreler aynı sayılır.

K7
H =
6.Graf kuramıZor
102108310142ABCDEF

Dijkstra algoritması A’dan başlar. 5. turda kesinleşen (kalıcı yapılan) köşeye tıklayın; A’nın kendisi 1. turdur.

başlangıç: Atur 5
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

3Çözeltiler

1.Algoritmalar ve karmaşıklık

Cevap: B · En kötü durumdaki bir işlem dizisi üzerinden işlem başına ortalama maliyeti

Cevap neden bu

Amortize analiz nadir pahalı işlemlerin maliyetini birçok ucuz işleme yayar ve herhangi bir dizi için garanti edilen bir ortalama verir.

Cevap

B · En kötü durumdaki bir işlem dizisi üzerinden işlem başına ortalama maliyeti
2.Algoritmalar ve karmaşıklık

Cevap: D · V − 1 turdan sonra herhangi bir kenarın hâlâ gevşetilebilip gevşetilemediğini kontrol eder

Cevap neden bu

Tüm gerçek en kısa uzaklıklar V − 1 tur içinde bulunur; bir kenar hâlâ iyileştirilebiliyorsa negatif bir döngü olmalıdır.

Cevap

D · V − 1 turdan sonra herhangi bir kenarın hâlâ gevşetilebilip gevşetilemediğini kontrol eder
3.Veri yapıları

Cevap: B · O(n), çünkü sonraki elemanlar kaydırılmalıdır

Cevap neden bu

Ekleme noktasından sonraki tüm elemanlar bir konum sağa kayar; bu n ile orantılı zaman alır.

Cevap

B · O(n), çünkü sonraki elemanlar kaydırılmalıdır
4.Veri yapıları

Cevap: B · Preorder ve inorder

Cevap neden bu

Preorder kökü verir ve kökün inorder dizisindeki konumu sol ve sağ alt ağaçları ayırır; preorder ile postorder ise bir düğümün tek çocuğu olduğunda belirsizdir.

Cevap

B · Preorder ve inorder
5.Graf kuramı

Cevap: H = 360

Euler, Hamilton ve ağaçlar: bağlantılı bir grafın tüm köşelerinin derecesi çiftse bir Euler devresi (her kenar bir kez, başlangıca dönüş), tam olarak iki köşenin derecesi tekse devre olmayan bir Euler yolu vardır; yol bir tek dereceli köşeden ötekine gider. Bir Hamilton devresi her köşeyi bir kez ziyaret eder; Kn grafında bunlardan (n − 1)!/2 tane vardır. n köşeli bir ağacın n − 1 kenarı vardır ve m kenarlı bağlantılı bir graf m − n + 1 kenar kaldırıldıktan sonra bir kapsayan ağaç bırakır.

Sayın

H = (7 − 1)!/2 = 720/2 = 360

Cevap

H = 360
6.Graf kuramı

Cevap: D

En kısa yollar ve kapsayan ağaçlar: Dijkstra algoritması her turda bir köşeyi kesinleştirir: geçici uzaklığı en küçük olan, henüz kesinleşmemiş köşeyi. Uzaklığı artık kesindir ve her komşu v için d(v) = min(d(v), d(u) + w(u, v)) alınır. Kruskal algoritması en küçük kapsayan ağacı, kenarları hafiften ağıra alıp bir döngü kapatacak kenarları atlayarak kurar; Prim algoritması bir başlangıç köşesinden tek bir ağaç büyütür ve her seferinde ağaçtan çıkan en hafif kenarı ekler. n köşeli bir kapsayan ağacın n − 1 kenarı vardır.

Dijkstra tur tur

1. A (0): C: 10
2. C (10): B: 12, E: 18
3. B (12): D: 22, E: 14
4. E (14): D: 17, F: 28
5. D (17): F: 27
6. F (27)

tur 5

D

Cevap

D

ExamProblems · examproblems.com/courses/data-structures-and-algorithms