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

ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟

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

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز الفقاعي
2. Bالفرز بالدمج
3. Cالفرز بالإدراج
4. Dالفرز السريع (Quicksort)

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

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

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

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

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

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

ماذا يعني أن لمسألة بنية فرعية مثلى؟

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

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

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

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتعدّ الدورات بالبحث بالعمق أولًا
2. Bتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات
3. Cتتحقق مما إذا كانت لأي حافة وزن سالب
4. Dبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة