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

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

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

ما قيمة log₂ 1024؟

1. A32
2. B512
3. C10
4. D12

ما التعقيد الزمني للفرز بالدمج في أسوأ الحالات؟

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 4 قطع، والأمثل 3
2. Bتستخدم الجشعة 3 قطع، والأمثل 3
3. Cتستخدم الجشعة قطعتين، والأمثل 2
4. Dتستخدم الجشعة 3 قطع، والأمثل 2

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

يجد البحث بالعرض أولًا في رسم بياني غير موزون:

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

1. AΘ(n^{log₂ 7})، أي نحو n^2,81
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n²)

أي عبارة صحيحة عن اختيار العنصر الأصغر رقم k في مصفوفة غير مرتبة؟

1. Aيحتاج الاختيار دائمًا إلى Ω(n log n) لأنه يتطلب الفرز
2. Bيعمل Quickselect في زمن متوقع O(n)، وتضمن طريقة وسيط الوسائط O(n) في أسوأ الحالات
3. Cالاختيار ممكن فقط في O(n²)
4. Dيعمل Quickselect في O(log n) في أسوأ الحالات لأنه يعود على جانب واحد فقط من المحور