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

ما التذكير (Memoisation)؟

1. Aتخزين نتائج استدعاءات الدوال ليُجاب عن الاستدعاءات المكررة من الذاكرة
2. Bتحويل العودية إلى حلقة مكافئة تلقائيًا فلا حاجة إلى مكدّس استدعاءات
3. Cتحرير الذاكرة بعد عودة الدالة
4. Dكتابة تعليقات بجانب كل سطر من الشيفرة

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

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

ما خوارزمية القوة الغاشمة؟

1. Aخوارزمية تجرّب كل الحلول المرشحة الممكنة
2. Bخوارزمية تستخدم العودية دائمًا
3. Cخوارزمية تخمّن إجابة عشوائيًا
4. Dخوارزمية تعمل على معالجات كثيرة

في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟

1. Aاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
2. Bاختر أقصر نشاط أولًا
3. Cاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة
4. Dاختر النشاط الذي يبدأ أبكر

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
2. Bتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
3. Cترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة
4. Dتحذف أغلى حافة حتى لا تبقى دورات

لأي نوع من مسألة الحقيبة تعطي القاعدة الجشعة "خذ العناصر بترتيب القيمة لكل وحدة وزن" إجابة مثلى دائمًا؟

1. Aالنوعان كلاهما
2. Bلا هذا ولا ذاك
3. Cالحقيبة الكسرية، حيث يجوز تقسيم العناصر
4. Dحقيبة 0/1، حيث يجب دائمًا أخذ العناصر كاملة

لماذا يكون متوسط البحث في جدول التجزئة O(1) بينما أسوأ الحالات O(n)؟

1. Aدوال التجزئة بطيئة
2. Bالوصول إلى المصفوفات يستغرق O(n)
3. Cقد تتصادم مفاتيح كثيرة في الدلو نفسه
4. Dيجب فرز المفاتيح أولًا