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

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(V²)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

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

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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

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

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

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

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

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

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

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

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

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

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