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

Bir algoritmanın çalışma süresi O(n)'dir. Bu büyümeye ne ad verilir?

  1. ADoğrusal
  2. BKaresel
  3. CLogaritmik
  4. DSabit
2.Kolay

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

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

Standart dizi tabanlı birleştirmeli sıralama ne kadar ek bellek kullanır?

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

Hangi sıralama algoritması kararlıdır?

  1. ASeçmeli sıralama (tipik sürüm)
  2. BYığın sıralaması
  3. CBirleştirmeli sıralama
  4. DHızlı sıralama (tipik yerinde sürüm)
5.Orta

1, 3 ve 4 değerinde madeni paralarla 6 tutarı için açgözlü "önce en büyük para" yöntemi optimuma kıyasla kaç para kullanır?

  1. AAçgözlü 3 para kullanır; optimum 3'tür
  2. BAçgözlü 2 para kullanır; optimum 2'dir
  3. CAçgözlü 3 para kullanır; optimum 2'dir
  4. DAçgözlü 4 para kullanır; optimum 3'tür
6.Orta

k tabanında d basamaklı n tamsayı üzerinde LSD taban sıralamasının (radix sort) çalışma süresi nedir?

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

Hangi sırt çantası varyantı için "öğeleri ağırlık başına değer sırasına göre al" açgözlü kuralı her zaman optimal bir yanıt verir?

  1. AÖğelerin her zaman bütün olarak alınması gereken 0/1 sırt çantası
  2. BHiçbir varyant
  3. CÖğelerin bölünebildiği kesirli sırt çantası
  4. DHer iki varyant
8.Zor

Bu sağlanabilirlik problemlerinden hangisinin polinom zamanda çözülebildiği bilinmektedir?

  1. AHer yan tümcenin en fazla iki literal içerdiği 2-SAT
  2. BBirleşimli normal biçimdeki formüller üzerinde genel SAT
  3. CDevre sağlanabilirliği
  4. DHer yan tümcenin tam olarak üç literal içerdiği 3-SAT

Cevap anahtarı

  1. 1. A · Doğrusal
  2. 2. C · Büyük O
  3. 3. A · O(n)
  4. 4. C · Birleştirmeli sıralama
  5. 5. C · Açgözlü 3 para kullanır; optimum 2'dir
  6. 6. C · O(d(n + k))
  7. 7. C · Öğelerin bölünebildiği kesirli sırt çantası
  8. 8. A · Her yan tümcenin en fazla iki literal içerdiği 2-SAT

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