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 büyüdükçe bunlardan hangisi en yavaş büyür?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
2.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'den kesinlikle daha yavaş büyür
  3. Cf, g'den kesinlikle daha hızlı büyür
  4. Df, 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.Kolay

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

  1. AHızlı sıralama (quicksort)
  2. BBirleştirmeli sıralama
  3. CKabarcık sıralaması
  4. DEklemeli sıralama
4.Orta

Hızlı sıralama pivot olarak her zaman ilk elemanı kullanıyor. Hangi girdide en kötü durum davranışını gösterir?

  1. ARastgele sıralı bir dizide
  2. BZaten sıralı bir dizide
  3. CUzunluğu 2 olan bir dizide
  4. DTüm elemanları farklı olan bir dizide
5.Orta

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

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

Dolduğunda kapasitesini iki katına çıkaran dinamik bir dizinin sonuna eleman eklemenin amortize zaman karmaşıklığı nedir?

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

Yeni bir X probleminin NP-zor olduğunu göstermek için ne yapmalısınız?

  1. AX'in polinom zamanda doğrulanabildiğini göstermek
  2. BBilinen bir NP-zor problemi polinom zamanda X'e indirgemek
  3. CX'i polinom zamanda bilinen bir NP-zor probleme indirgemek
  4. DX'in küçük girdiler için polinom algoritması olmadığını göstermek
8.Zor

Bazı kenar ağırlıkları negatif olduğunda Dijkstra algoritması neden yanlış sonuçlar verebilir?

  1. ANegatif sayılar bir öncelik kuyruğunda saklanamaz
  2. BHer negatif kenarda sonsuz döngüye girer
  3. CYalnızca yönsüz çizgelerde çalışır
  4. DBir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir

Cevap anahtarı

  1. 1. D · O(log n)
  2. 2. D · 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
  3. 3. A · Hızlı sıralama (quicksort)
  4. 4. B · Zaten sıralı bir dizide
  5. 5. D · O(log n)
  6. 6. B · O(1)
  7. 7. B · Bilinen bir NP-zor problemi polinom zamanda X'e indirgemek
  8. 8. D · Bir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir

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