1.سهلة
أي من أزمنة التنفيذ هذه كثير حدود؟
- AO(n!)
- BO(2ⁿ)
- CO(n³)
- DO(nⁿ)
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
ما التعقيد الزمني للفرز بالإدراج في أسوأ الحالات؟
- AO(n)
- BO(n²)
- CO(n log n)
- DO(log n)
3.سهلة
ما التذكير (Memoisation)؟
- Aتخزين نتائج استدعاءات الدوال ليُجاب عن الاستدعاءات المكررة من الذاكرة
- Bتحرير الذاكرة بعد عودة الدالة
- Cكتابة تعليقات بجانب كل سطر من الشيفرة
- Dتحويل العودية إلى حلقة مكافئة تلقائيًا فلا حاجة إلى مكدّس استدعاءات
4.متوسطة
ما حل علاقة التكرار T(n) = T(n − 1) + O(1)؟
- AO(log n)
- BO(n²)
- CO(n)
- DO(2ⁿ)
5.متوسطة
كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟
- AO(1)
- BO(n)
- CO(n²)
- DO(log n)
6.متوسطة
لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟
- Aكل اللوغاريتمات في علوم الحاسوب أساسها 10، فهو مفهوم ضمنًا
- Bلأن الأساس لا يهم إلا عندما تكون n صغيرة
- Cلأن اللوغاريتمات ذات الأسس المختلفة لا تختلف إلا بمعامل ثابت
- Dلأن اللوغاريتمات تُقرَّب دائمًا إلى أعداد صحيحة
7.صعبة
أي تعريف للفئة NP صحيح؟
- Aالمسائل التي لا يمكن حلها في زمن كثير حدود
- Bمسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة
- Cالمسائل التي لا تستطيع أي خوارزمية حلها
- Dالمسائل غير كثيرة الحدود
8.صعبة
ماذا أثبتت مبرهنة Cook–Levin؟
- Aأن مسألة التوقف غير قابلة للحسم
- Bأن مسألة الإرضاء البولياني (SAT) هي NP-تامة
- Cأن P لا تساوي NP
- Dأن كل مسألة NP يمكن حلها في زمن أسّي
مفتاح الإجابات
- 1. C · O(n³)
- 2. B · O(n²)
- 3. A · تخزين نتائج استدعاءات الدوال ليُجاب عن الاستدعاءات المكررة من الذاكرة
- 4. C · O(n)
- 5. B · O(n)
- 6. C · لأن اللوغاريتمات ذات الأسس المختلفة لا تختلف إلا بمعامل ثابت
- 7. B · مسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة
- 8. B · أن مسألة الإرضاء البولياني (SAT) هي NP-تامة
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.