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

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

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

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aخطي
2. Bثابت
3. Cلوغاريتمي
4. Dتربيعي

تستغرق خوارزمية O(n) ثلاث ثوانٍ عند n = مليون. كم تستغرق تقريبًا عند n = مليونين؟

1. A12 ثانية
2. B9 ثوانٍ
3. C3 ثوانٍ
4. D6 ثوانٍ

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

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

تكون المسألة NP-كاملة (NP-complete) إذا كانت:

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

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

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