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

n elemanlı sırasız bir dizide doğrusal aramanın zaman karmaşıklığı (en kötü durumda) nedir?

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

İkili arama girdisinden ne gerektirir?

1. ADizinin yalnızca pozitif sayılar içermesini
2. BDizi uzunluğunun ikinin kuvveti olmasını
3. CDizinin 1000'den fazla eleman içermemesini
4. DDizinin sıralı olmasını

n büyüdükçe bunlardan hangisi en yavaş büyür?

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

T(n) = T(n − 1) + O(n) yinelemesinin çözümü nedir?

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

Negatif olmayan kenar ağırlıklarına sahip bir grafta tek bir kaynaktan en kısa yolları hangi algoritma bulur?

1. AHer durumda Bellman–Ford gereklidir
2. BKruskal algoritması
3. CDerinlik öncelikli arama (DFS)
4. DDijkstra algoritması

Ağırlıksız bir grafta genişlik öncelikli arama neyi bulur?

1. AMinimum kapsayan ağacı
2. BTüm graflarda bir topolojik sırayı
3. CNegatif kenar ağırlıkları içeren graflardaki en kısa yolları
4. DBaşlangıç düğümünden kenar sayısı cinsinden en kısa yolları

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

1. AEvet, ama yalnızca 100'den kısa diziler için
2. BHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
3. CEvet, dolayısıyla alt sınır yanlıştır
4. DHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir

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

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)