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

Bir fonksiyon n yinelemeli bir döngü, ardından ayrı olarak n yinelemeli başka bir döngü çalıştırıyor. Zaman karmaşıklığı nedir?

  1. AO(log n)
  2. BO(n²)
  3. CO(2ⁿ)
  4. DO(n)
2.Algoritmalar ve karmaşıklıkZor

Ana teorem (master theorem) kullanılarak T(n) = 8T(n/2) + O(n²) bağıntısının çözümü nedir?

  1. AΘ(n² log n)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n³)
3.Veri yapılarıOrta

Dijkstra algoritması işlenecek bir sonraki köşeyi seçmek için hangi soyut veri türünü kullanır?

  1. AFIFO kuyruğu
  2. BSırasız bir küme
  3. CYığın
  4. DMin-öncelik kuyruğu
4.Veri yapılarıZor

Bir dizinin her elemanı için sağındaki bir sonraki büyük elemanı toplam O(n) sürede bulmak istiyorsunuz. Hangi yapı yardımcı olur?

  1. AYanıtını bekleyen elemanları tutan bir yığın
  2. BHer eleman için yeniden oluşturulan bir ikili arama ağacı
  3. CTüm elemanlardan oluşan bir karma tablosu
  4. DHer eleman çiftini tutan bir kuyruk
5.Graf kuramıOrta

Bağlantılı bir grafın 15 köşesi ve 20 kenarı vardır. Bir kapsayan ağaç kalması için kaç kenar (k) kaldırılmalıdır?

|V| = 15|E| = 20
k =
6.Graf kuramıZor
15163205811ABCDE

Ağırlıklı grafın en küçük kapsayan ağacının toplam ağırlığını (W) bulun.

|V| = 5|E| = 7
W =

3Çözeltiler

1.Algoritmalar ve karmaşıklık

Cevap: D · O(n)

Cevap neden bu

n + n = 2n'dir ve sabit çarpanlar atılır, bu yüzden fonksiyon O(n)'dir.

Cevap

D · O(n)
2.Algoritmalar ve karmaşıklık

Cevap: D · Θ(n³)

Cevap neden bu

log₂ 8 = 3'tür ve n², n³'ten daha yavaş büyür, bu yüzden yapraklar baskındır: Θ(n³).

Cevap

D · Θ(n³)
3.Veri yapıları

Cevap: D · Min-öncelik kuyruğu

Cevap neden bu

Genellikle ikili öbekle gerçekleştirilen min-öncelik kuyruğu, ziyaret edilmemiş en küçük uzaklıklı köşeyi verimli biçimde döndürür.

Cevap

D · Min-öncelik kuyruğu
4.Veri yapıları

Cevap: A · Yanıtını bekleyen elemanları tutan bir yığın

Cevap neden bu

Soldan sağa tararken yığındaki mevcut elemandan küçük her elemanı pop edin (mevcut eleman onların yanıtıdır), ardından mevcut elemanı push edin; her eleman en fazla iki kez hareket eder.

Cevap

A · Yanıtını bekleyen elemanları tutan bir yığın
5.Graf kuramı

Cevap: k = 6

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.

Kapsayan ağacın kenarları

15 − 1 = 14

Kaldırılacak kenarlar

k = 20 − 14 = 6

Cevap

k = 6
6.Graf kuramı

Cevap: W = 31

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.

Kruskal algoritması

BC (3): al
CE (5): al
DE (8): al
BE (11): atla, döngü kapatır
AB (15): al

Toplam ağırlık

W = 3 + 5 + 8 + 15 = 31

Cevap

W = 31

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