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

Hangi gösterim büyüme için bir üst sınırı tanımlar?

  1. ABüyük Omega
  2. BBüyük Teta
  3. CBüyük O
  4. DKüçük omega
2.Kolay

O(2ⁿ) büyümeye ne ad verilir?

  1. ADoğrusal
  2. BLogaritmik
  3. CPolinom
  4. DÜstel
3.Kolay

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 yavaş 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 hızlı büyür
4.Orta

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

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

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 + k)
  4. DO(n log n + k log n)
6.Orta

Basit özyinelemeli faktöriyel fonksiyonu fact(n) = n × fact(n − 1) ne kadar yığın (stack) alanı kullanır?

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

22n, O(2ⁿ) içinde midir?

  1. AHayır, çünkü 22n = 4ⁿ ve 4ⁿ / 2ⁿ = 2ⁿ sınırsız büyür
  2. BEvet, çünkü ikisi de üsteldir
  3. CHayır, çünkü 22n, 2ⁿ'den daha yavaş büyür
  4. DEvet, çünkü üsteki sabit çarpanlar Büyük O'da her zaman göz ardı edilir
8.Zor

Durma problemi neyi gösterir?

  1. ABazı programlar daha hızlı bilgisayarlarda daha hızlı çalışır, bu yüzden durma donanıma bağlıdır
  2. BHer program eninde sonunda durur
  3. CDöngülerden kaçınılmalıdır
  4. DHiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez

Cevap anahtarı

  1. 1. C · Büyük O
  2. 2. D · Üstel
  3. 3. A · f, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  4. 4. C · Ω(n log n)
  5. 5. D · O(n log n + k log n)
  6. 6. A · O(n)
  7. 7. A · Hayır, çünkü 22n = 4ⁿ ve 4ⁿ / 2ⁿ = 2ⁿ sınırsız büyür
  8. 8. D · Hiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez

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