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

n elemanlı sırasız bir dizide doğrusal aramanın zaman karmaşıklığı (en kötü durumda) nedir?

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

Hangi sıralama algoritması bir pivot seçer ve diziyi daha küçük ve daha büyük elemanlara ayırır?

  1. AKabarcık sıralaması
  2. BBirleştirmeli sıralama
  3. CEklemeli sıralama
  4. DHızlı sıralama (quicksort)
3.Kolay

f(n) = Θ(g(n)) ne anlama gelir?

  1. Af 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
  2. Bf, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  3. Cf, g'den kesinlikle daha yavaş büyür
  4. Df, g'den kesinlikle daha hızlı büyür
4.Orta

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

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

V düğümlü ve E kenarlı bir çizgede Bellman–Ford algoritmasının zaman karmaşıklığı nedir?

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

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

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

Ana teorem (master theorem) kullanılarak T(n) = 8T(n/2) + O(n²) bağıntısının çözümü nedir?

  1. AΘ(n² log n)
  2. BΘ(n²)
  3. CΘ(n³)
  4. DΘ(n log n)
8.Zor

Dinamik programlama ile çözülen 0/1 sırt çantası problemi O(nW) zaman alır. Buna neden sözde polinom (pseudo-polynomial) denir?

  1. AW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  2. BÇünkü yalnızca W = 0 için çalışır
  3. CÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
  4. DÇünkü n her zaman küçüktür

Cevap anahtarı

  1. 1. B · O(n)
  2. 2. D · Hızlı sıralama (quicksort)
  3. 3. B · 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. D · O(n³)
  5. 5. D · O(V × E)
  6. 6. A · O(n)
  7. 7. C · Θ(n³)
  8. 8. A · W bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir

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