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

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

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

كيف يعمل الفرز بالاختيار (Selection sort)؟

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالبرمجة الديناميكية
2. Bفرّق تسُد
3. Cالاختيار الجشع
4. Dالقوة الغاشمة

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

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

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

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

ما التعقيد الزمني لـ: for i = 1 to n: for j = 1 to i: نفّذ عملًا O(1)؟

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

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

1. Aاستخدام العودية على الجانب الأيسر فقط
2. Bفرز المدخلات قبل تشغيل الفرز السريع
3. Cاختيار العنصر الأول دائمًا
4. Dاختيار المحور عشوائيًا بتوزيع منتظم

يعمل الفرز بالإدراج في O(n) على المدخلات المرتبة. هل يناقض هذا الحد الأدنى Ω(n log n) للفرز بالمقارنة؟

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