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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

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

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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

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

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

أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟

1. Aخوارزمية بيلمان–فورد مطلوبة في جميع الحالات
2. Bخوارزمية كروسكال (Kruskal)
3. Cالبحث بالعمق أولًا (DFS)
4. Dخوارزمية ديكسترا (Dijkstra)

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

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

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

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

باستخدام المبرهنة الرئيسية (master theorem)، حل T(n) = 8T(n/2) + O(n²) هو:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)