1.سهلة
ما الخطوات الثلاث لخوارزمية فرّق تسُد؟
- Aالتقسيم، والحل، والدمج
- Bالقراءة، والحساب، والكتابة
- Cالفرز، والبحث، والإرجاع
- Dالتخمين، والتحقق، والتكرار
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟
- Aثابت
- Bخطي
- Cتربيعي
- Dلوغاريتمي
3.سهلة
ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟
- Aأن زمن تنفيذها لا ينمو مع حجم المدخلات
- Bأنها لا يمكن تنفيذها إلا مرة واحدة
- Cأنها تعالج عنصرًا واحدًا بالضبط في كل ثانية من زمن التشغيل
- Dأنها تستغرق ثانية واحدة بالضبط دائمًا
4.متوسطة
ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟
- AO(log n)
- BO(n log n)
- CO(n)
- DO(n²)
5.متوسطة
بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟
- Aتستخدم الجشعة 4 قطع، والأمثل 3
- Bتستخدم الجشعة 3 قطع، والأمثل 2
- Cتستخدم الجشعة قطعتين، والأمثل 2
- Dتستخدم الجشعة 3 قطع، والأمثل 3
6.متوسطة
ماذا يقيس التحليل المستهلَك (amortised)؟
- Aكلفة الخوارزمية على أفضل مدخل
- Bمتوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
- Cكلفة أغلى عملية منفردة في أي موضع من السلسلة
- Dالكلفة المتوقعة على مدخلات عشوائية
7.صعبة
لأي نوع من مسألة الحقيبة تعطي القاعدة الجشعة "خذ العناصر بترتيب القيمة لكل وحدة وزن" إجابة مثلى دائمًا؟
- Aلا هذا ولا ذاك
- Bالنوعان كلاهما
- Cالحقيبة الكسرية، حيث يجوز تقسيم العناصر
- Dحقيبة 0/1، حيث يجب دائمًا أخذ العناصر كاملة
8.صعبة
تكون المسألة NP-كاملة (NP-complete) إذا كانت:
- Aمستحيلة الحل
- Bتنتمي إلى NP وكل مسألة في NP قابلة للاختزال إليها في زمن كثير الحدود
- Cخارج NP لكنها أصعب من جميع مسائل NP، مثل مسألة التوقف
- Dقابلة للحل في زمن كثير الحدود
مفتاح الإجابات
- 1. A · التقسيم، والحل، والدمج
- 2. B · خطي
- 3. A · أن زمن تنفيذها لا ينمو مع حجم المدخلات
- 4. B · O(n log n)
- 5. B · تستخدم الجشعة 3 قطع، والأمثل 2
- 6. B · متوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
- 7. C · الحقيبة الكسرية، حيث يجوز تقسيم العناصر
- 8. B · تنتمي إلى NP وكل مسألة في NP قابلة للاختزال إليها في زمن كثير الحدود
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.