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 O
  3. CBüyük Teta
  4. DKüçük omega
2.Kolay

Bu çalışma sürelerinden hangisi polinomdur?

  1. AO(n³)
  2. BO(2ⁿ)
  3. CO(n!)
  4. DO(nⁿ)
3.Kolay

Böl ve yönet algoritmasının üç adımı nedir?

  1. AOku, hesapla, yaz
  2. BTahmin et, kontrol et, tekrarla
  3. CBöl, yönet (çöz), birleştir
  4. DSırala, ara, döndür
4.Orta

Dinamik programlama birleştirmeli sıralama için neden gerçek bir hızlanma sağlamaz?

  1. ADinamik programlama yalnızca graf problemlerinde çalışır, dizilerde çalışmaz
  2. BBirleştirmeli sıralamanın özyinelemeli bir yapısı yoktur
  3. CBirleştirmeli sıralama zaten O(n)'dir
  4. DAlt problemleri çakışmaz, bu yüzden yeniden kullanılacak bir şey yoktur
5.Orta

Sıralı bir dizide her iki uçtan birer işaretçiyi içeri doğru hareket ettirerek toplamı bir hedefe eşit olan iki eleman arıyorsunuz. Zaman karmaşıklığı nedir?

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

T(n) = 2T(n/2) + O(n) yineleme bağıntısının çözümü nedir?

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

Küçük o gösterimi hakkında hangi ifade doğrudur?

  1. An = o(n), çünkü her fonksiyon kendisinin küçük o'sudur
  2. Bn² = o(n)
  3. Cn = o(n²)'dir, ama n, o(n) değildir
  4. D2n = o(n), çünkü 2n yavaş büyür
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. CHiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez
  4. DDöngülerden kaçınılmalıdır

Cevap anahtarı

  1. 1. B · Büyük O
  2. 2. A · O(n³)
  3. 3. C · Böl, yönet (çöz), birleştir
  4. 4. D · Alt problemleri çakışmaz, bu yüzden yeniden kullanılacak bir şey yoktur
  5. 5. A · O(n)
  6. 6. D · O(n log n)
  7. 7. C · n = o(n²)'dir, ama n, o(n) değildir
  8. 8. C · 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.