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

ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو أبطأ من g تمامًا
2. Bأن f تنمو أسرع من g تمامًا
3. Cأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا
4. Dأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g

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

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

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

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

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

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

أي خوارزمية فرز مستقرة؟

1. Aالفرز السريع (النسخة الموضعية المعتادة)
2. Bالفرز بالكومة
3. Cالفرز بالدمج
4. Dالفرز بالاختيار (النسخة المعتادة)

لماذا قد تعطي خوارزمية Dijkstra نتائج خاطئة حين تكون بعض أوزان الحواف سالبة؟

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

أي حد صحيح لـ log(n!)؟

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