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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

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

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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

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

تكون البرمجة الديناميكية مفيدة عندما تحتوي المسألة على:

1. Aمدخلات عشوائية فقط
2. Bمسائل فرعية متداخلة وبنية فرعية مثلى
3. Cلا مسائل فرعية على الإطلاق، فيمكن حلها في خطوة واحدة
4. Dحلقة واحدة

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

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

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

1. Aثابت
2. Bخطي
3. Cأسّي
4. Dلوغاريتمي

ما الكلفة الزمنية والمكانية لحساب عدد فيبوناتشي رقم n بحلقة لا تحتفظ إلا بآخر قيمتين؟

1. Aزمن O(2ⁿ) ومساحة O(1)
2. Bزمن O(n) ومساحة O(n)
3. Cزمن O(log n) ومساحة O(n)
4. Dزمن O(n) ومساحة O(1)

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

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