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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

1. Aالزمن الذي تستغرقه على أصغر مدخل
2. Bالزمن الذي تستغرقه على حاسوب بطيء
3. Cالزمن المتوقع الذي تستغرقه على مدخل عشوائي بحجم n
4. Dأقصى زمن تستغرقه على كل المدخلات ذات الحجم n

ماذا يتطلب البحث الثنائي في مدخلاته؟

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

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

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

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

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

الخوارزمية الجشعة (Greedy):

1. Aتعطي الحل الأمثل دائمًا
2. Bتتخذ الخيار الأفضل محليًا في كل خطوة
3. Cتستخدم العودية فقط
4. Dتجرّب كل حل ممكن

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

تُظهر مسألة التوقف أنه:

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

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

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