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

İkili arama girdisinden ne gerektirir?

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

Kaba kuvvet algoritması nedir?

1. ARastgele bir yanıt tahmin eden bir algoritma
2. BTüm olası aday çözümleri deneyen bir algoritma
3. CBirçok işlemci üzerinde çalışan bir algoritma
4. DHer zaman özyineleme kullanan bir algoritma

Hangi sıralama algoritması yanlış sırada olan komşu elemanların yerini tekrar tekrar değiştirir?

1. ABirleştirmeli sıralama (merge sort)
2. BHızlı sıralama (quicksort)
3. CYığın sıralaması (heap sort)
4. DKabarcık sıralaması (bubble sort)

k tabanında d basamaklı n tamsayı üzerinde LSD taban sıralamasının (radix sort) çalışma süresi nedir?

1. AO(n log n)
2. BO(dn log k)
3. CO(n²)
4. DO(d(n + k))

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(n + k)
2. BO(n log n + k log n)
3. CO(k n log n)
4. DO(nk)

Etkinlik seçimi probleminde hangi açgözlü kural her zaman çakışmayan en fazla sayıda etkinliği verir?

1. AEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
2. BEn erken başlayan etkinliği seç
3. CÖnce en az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
4. DÖnce en kısa etkinliği seç

Gezgin satıcı problemi nasıl sınıflandırılır?

1. AKarar versiyonu P'de, optimizasyon versiyonu ise NP-tamdır
2. BKarar verilemezdir
3. CDijkstra algoritması her şehri bir kez ziyaret ederek onu çözdüğü için P'dedir
4. DKarar versiyonu NP-tam, optimizasyon versiyonu NP-zordur

Bir problem hangi durumda NP-tamdır?

1. ANP'dedir ve her NP problemi ona polinom zamanda indirgenebilir
2. BPolinom zamanda çözülebilir
3. CÇözülmesi imkânsızdır
4. DNP'nin dışındadır ama durma problemi gibi tüm NP problemlerinden daha zordur