Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Hangi sıralama algoritması bir pivot seçer ve diziyi daha küçük ve daha büyük elemanlara ayırır?

1. AKabarcık sıralaması
2. BEklemeli sıralama
3. CBirleştirmeli sıralama
4. DHızlı sıralama (quicksort)

Bir algoritmanın çalışma süresi O(n)'dir. Bu büyümeye ne ad verilir?

1. ASabit
2. BDoğrusal
3. CLogaritmik
4. DKaresel

Hangi gösterim büyüme için bir alt sınırı tanımlar?

1. AΩ (Büyük Omega)
2. BO (Büyük O)
3. Co (küçük o)
4. DΘ (Büyük Teta)

Ulaşılabilir bir temel durumu olmayan özyinelemeli bir fonksiyon hakkında hangi ifade doğrudur?

1. ADerleyici onu her zaman güvenli biçimde sonlanan bir döngüye dönüştürür
2. BOtomatik olarak 0 döndürür
3. CO(1) zamanda çalışır
4. DÇağrı yığını taşana kadar kendini çağırmaya devam eder

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(n²)
2. BO(n)
3. CO(log n)
4. DO(2ⁿ)

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

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

Bir hash tablosunda arama neden ortalamada O(1), en kötü durumda ise O(n)'dir?

1. AHash fonksiyonları yavaştır
2. BBirçok anahtar çakışarak aynı kovaya düşebilir
3. CDizilere erişim O(n)'dir
4. DAnahtarların önce sıralanması gerekir

En kısa basit yollar polinom zamanda bulunabilir. Genel bir çizgede iki düğüm arasındaki en uzun basit yolu bulmak hakkında ne bilinmektedir?

1. ANP-zordur
2. BAğırlıkları negatifleştirilmiş Dijkstra algoritmasıyla çözülebilir
3. CKarar verilemezdir
4. DHer zaman O(V + E)'de çözülebilir