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

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

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

n sayıdan oluşan sırasız bir dizide en büyük değeri bulmanın zaman karmaşıklığı nedir?

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

3n² + 5n + 2 ifadesinin Büyük O'su nedir?

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

Bir problemin optimal alt yapıya sahip olması ne anlama gelir?

  1. AHer alt problem aynı boyuttadır
  2. BOptimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  3. CProblem sabit zamanda çözülebilir
  4. DProblemin tam olarak bir optimal çözümü vardır ve bu çözümü her alt problem paylaşır
5.Orta

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

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

O(log n)'de olduğu gibi, Büyük O'da logaritmanın tabanı neden genellikle yazılmaz?

  1. AFarklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
  2. BTaban yalnızca küçük n için önemlidir
  3. CLogaritmalar her zaman tamsayılara yuvarlanır
  4. DBilgisayar bilimindeki tüm logaritmaların tabanı 10'dur, bu yüzden zımnen bellidir
7.Zor

Biri NP-tam bir problem için polinom zamanlı bir algoritma bulsaydı ne sonuç çıkardı?

  1. AYalnızca o problem P'ye geçerdi
  2. BTüm üstel zamanlı algoritmalar hemen doğrusal zamanda çalışırdı
  3. CDurma problemi karar verilebilir hâle gelirdi
  4. DNP'deki her problem polinom zamanda çözülebilirdi, yani P = NP
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. AHer zaman O(V + E)'de çözülebilir
  2. BAğırlıkları negatifleştirilmiş Dijkstra algoritmasıyla çözülebilir
  3. CKarar verilemezdir
  4. DNP-zordur

Cevap anahtarı

  1. 1. B · Girdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
  2. 2. C · O(n)
  3. 3. A · O(n²)
  4. 4. B · Optimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  5. 5. D · 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. A · Farklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
  7. 7. D · NP'deki her problem polinom zamanda çözülebilirdi, yani P = NP
  8. 8. D · NP-zordur

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