ورقة عمل الخوارزميات والتعقيد مع الإجابات

ماذا يُسمى النمو O(2ⁿ)؟

1. Aأسّي
2. Bلوغاريتمي
3. Cخطي
4. Dكثير حدود

أي ترميز يصف حدًا أعلى للنمو؟

1. Aأوميغا الصغير (Little omega)
2. BO الكبير (Big O)
3. Cثيتا الكبير (Big Theta)
4. Dأوميغا الكبير (Big Omega)

ماذا يتطلب البحث الثنائي في مدخلاته؟

1. Aألا تتجاوز المصفوفة 1000 عنصر
2. Bأن تكون المصفوفة مرتبة
3. Cأن يكون طول المصفوفة قوة للعدد اثنين
4. Dألا تحتوي المصفوفة إلا أعدادًا موجبة

ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟

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

أي عبارة صحيحة عن دالة عودية ليس لها حالة أساس قابلة للبلوغ؟

1. Aتعمل في زمن O(1)
2. Bتواصل استدعاء نفسها حتى يفيض مكدّس الاستدعاءات
3. Cيحولها المترجم دائمًا إلى حلقة تنتهي بأمان
4. Dتُرجع 0 تلقائيًا

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

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

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

1. Alog n ضعف الأصغر على الأكثر
2. Bضعف حجم الغطاء الرأسي الأصغر على الأكثر
3. Cجودته مجهولة مقارنةً بالأمثل
4. Dغطاء رأسي أصغر دائمًا