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

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

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

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

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

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

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

الخوارزمية الجشعة (Greedy):

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

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aأقصر المسارات بين كل أزواج الرؤوس في O(V³)
2. Bأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
3. Cترتيبًا طوبولوجيًا في O(V²)
4. Dشجرة امتداد صغرى في O(E log V)

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

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

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

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

أي أمرين يجب إثباتهما لإثبات أن مسألة القرار X هي NP-تامة؟

1. Aأن X تنتمي إلى NP، وأن مسألة NP-تامة معروفة تُختزل إلى X في زمن كثير حدود
2. Bأن X تُختزل إلى مسألة في P، وأن X تنتمي إلى NP
3. Cأن X ليس لها خوارزمية كثيرة حدود، وأن X قابلة للحسم
4. Dأن X تنتمي إلى P، وأن X تُختزل إلى SAT