1.سهلة
زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟
- Aلوغاريتمي
- Bثابت
- Cتربيعي
- Dخطي
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
أي ترميز يصف حدًا أعلى للنمو؟
- Aأوميغا الصغير (Little omega)
- Bأوميغا الكبير (Big Omega)
- CO الكبير (Big O)
- Dثيتا الكبير (Big Theta)
3.سهلة
ماذا يُسمى النمو O(2ⁿ)؟
- Aأسّي
- Bلوغاريتمي
- Cخطي
- Dكثير حدود
4.متوسطة
كيف تبني خوارزمية Prim شجرة امتداد صغرى؟
- Aتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
- Bتحذف أغلى حافة حتى لا تبقى دورات
- Cتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
- Dترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة
5.متوسطة
ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟
- AO(1)
- BO(n)
- CO(log n)
- DO(n²)
6.متوسطة
ما حل علاقة التكرار T(n) = T(n/2) + O(1)؟
- AO(log n)
- BO(n)
- CO(1)
- DO(n log n)
7.صعبة
تُظهر مسألة التوقف أنه:
- Aبعض البرامج تعمل أسرع على حواسيب أسرع، فيعتمد التوقف على العتاد
- Bلا توجد خوارزمية تستطيع أن تقرر لكل برنامج ومدخل ما إذا كان البرنامج سيتوقف
- Cكل برنامج يتوقف في النهاية
- Dيجب تجنب الحلقات
8.صعبة
أي حد صحيح لـ log(n!)؟
- AΘ(log n)
- BΘ(n)
- CΘ(n log n)
- DΘ(n²)
مفتاح الإجابات
- 1. D · خطي
- 2. C · O الكبير (Big O)
- 3. A · أسّي
- 4. A · تُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
- 5. A · O(1)
- 6. A · O(log n)
- 7. B · لا توجد خوارزمية تستطيع أن تقرر لكل برنامج ومدخل ما إذا كان البرنامج سيتوقف
- 8. C · Θ(n log n)
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.