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

Birleştirmeli sıralama hangi tasarım stratejisini kullanır?

1. AAçgözlü seçim
2. BKaba kuvvet
3. CDinamik programlama
4. DBöl ve yönet

f(n) = Θ(g(n)) ne anlama gelir?

1. Af, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
2. Bf, g'den kesinlikle daha hızlı büyür
3. Cf her n için her zaman g'den küçüktür, yani g onu yukarıdan sınırlar ama aşağıdan asla sınırlamaz
4. Df, g'den kesinlikle daha yavaş büyür

Algoritma nedir?

1. ABir problemi çözen, iyi tanımlanmış adımlardan oluşan sonlu bir dizi
2. BMatematiksel formülleri yazmak için tasarlanmış bir programlama dili
3. CSayıları saklayan bir veri yapısı
4. DGrafik arayüzü olan herhangi bir bilgisayar programı

Karşılaştırmaya dayalı sıralama için en kötü durumdaki alt sınır nedir?

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

n elemanlı bir diziyi bir kez sıralıyor ve ardından k üyelik sorgusunu ikili aramayla yanıtlıyorsunuz. Toplam maliyet nedir?

1. AO(nk)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(n + k)

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

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

Yeni bir X probleminin NP-zor olduğunu göstermek için ne yapmalısınız?

1. ABilinen bir NP-zor problemi polinom zamanda X'e indirgemek
2. BX'in polinom zamanda doğrulanabildiğini göstermek
3. CX'i polinom zamanda bilinen bir NP-zor probleme indirgemek
4. DX'in küçük girdiler için polinom algoritması olmadığını göstermek

NP sınıfının hangi tanımı doğrudur?

1. AEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
2. BHiçbir algoritmanın çözemeyeceği problemler
3. CPolinom zamanda çözülemeyen problemler
4. DPolinom olmayan problemler