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 dizide indeksle bir elemana erişmenin karmaşıklığı nedir?

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

Hangi sıralama algoritması yanlış sırada olan komşu elemanların yerini tekrar tekrar değiştirir?

  1. AYığın sıralaması (heap sort)
  2. BHızlı sıralama (quicksort)
  3. CKabarcık sıralaması (bubble sort)
  4. DBirleştirmeli sıralama (merge sort)
3.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)
4.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ü 2 para kullanır; optimum 2'dir
  2. BAçgözlü 4 para kullanır; optimum 3'tür
  3. CAçgözlü 3 para kullanır; optimum 2'dir
  4. DAçgözlü 3 para kullanır; optimum 3'tür
5.Orta

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

  1. AO(n)
  2. BO(n²)
  3. CO(2ⁿ)
  4. DO(n log n)
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(d(n + k))
  2. BO(n²)
  3. CO(n log n)
  4. DO(dn log k)
7.Zor

Gezgin satıcı problemi nasıl sınıflandırılır?

  1. ADijkstra algoritması her şehri bir kez ziyaret ederek onu çözdüğü için P'dedir
  2. BKarar versiyonu P'de, optimizasyon versiyonu ise NP-tamdır
  3. CKarar verilemezdir
  4. DKarar versiyonu NP-tam, optimizasyon versiyonu NP-zordur
8.Zor

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

  1. ANP'deki her problem polinom zamanda çözülebilirdi, yani P = NP
  2. BTüm üstel zamanlı algoritmalar hemen doğrusal zamanda çalışırdı
  3. CDurma problemi karar verilebilir hâle gelirdi
  4. DYalnızca o problem P'ye geçerdi

Cevap anahtarı

  1. 1. D · O(1)
  2. 2. C · Kabarcık sıralaması (bubble sort)
  3. 3. C · O(n)
  4. 4. C · Açgözlü 3 para kullanır; optimum 2'dir
  5. 5. B · O(n²)
  6. 6. A · O(d(n + k))
  7. 7. D · Karar versiyonu NP-tam, optimizasyon versiyonu NP-zordur
  8. 8. A · NP'deki her problem polinom zamanda çözülebilirdi, yani P = NP

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