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

Ücretsiz yazdırılabilir Algoritmalar ve karmaşıklık çalışma kâğıdı: kolaydan sınav düzeyine 8 soru ve cevap anahtarı. Yazdırın ya da PDF olarak kaydedin.

Yeni çalışma kâğıdıİpuçlarıyla çevrimiçi çalışın

Öğretmenler için: sınıfta ücretsiz yazdırılabilir, çoğaltılabilir ve kullanılabilir. Her yeni çalışma kâğıdında yeni değerler ve kendi cevap anahtarı vardır. Ders sayfanızda ExamProblems bağlantısı vermeniz bizi memnun eder.

Ad: ____________________   Tarih: ____________

1.Kolay

Her biri n kez çalışan iç içe iki döngüye sahip bir algoritma genellikle hangi karmaşıklığa sahiptir?

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

Alan karmaşıklığı neyi ölçer?

  1. AKod satırı sayısını
  2. BProgramın derlendikten sonraki dosyasının disk alanını
  3. CBilgisayarın fiziksel boyutunu
  4. DGirdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
3.Kolay

O(n²) bir algoritma n = 1000 için 1 saniye sürüyor. n = 2000 için yaklaşık ne kadar sürer?

  1. A2 saniye
  2. B1 saniye
  3. C4 saniye
  4. D8 saniye
4.Orta

İki n × n matrisi standart üçlü döngüyle çarpmanın zaman karmaşıklığı nedir?

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

Prim algoritması minimum kapsayan ağacı nasıl oluşturur?

  1. AGenişlik öncelikli arama çalıştırır ve BFS ağacını tutar
  2. BDöngü kalmayana kadar en pahalı kenarı çıkarır
  3. CBir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  4. DTüm kenarları ağırlığa göre sıralar ve ormanda döngü oluşturmayacaksa her birini ekler
6.Orta

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

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

V düğümlü ve E kenarlı bir çizgede ikili yığınla Dijkstra algoritmasının çalışma süresi nedir?

  1. AO(V³)
  2. BO(V + E)
  3. CO((V + E) log V)
  4. DO(V × E)
8.Zor

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. AKarar verilemezdir
  2. BAğırlıkları negatifleştirilmiş Dijkstra algoritmasıyla çözülebilir
  3. CNP-zordur
  4. DHer zaman O(V + E)'de çözülebilir

Cevap anahtarı

  1. 1. A · O(n²)
  2. 2. D · Girdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
  3. 3. C · 4 saniye
  4. 4. D · O(n³)
  5. 5. C · Bir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  6. 6. D · O(log n)
  7. 7. C · O((V + E) log V)
  8. 8. C · NP-zordur

Tam adım adım çözümler: bu konuyu examproblems.com’da çalışın.