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

ما حالة الأساس في دالة عودية؟

1. Aحالة يُجاب عنها مباشرة دون استدعاء عودي آخر
2. Bالسطر الأول من الدالة
3. Cالحالة ذات المدخلات الأكبر، وتُعالَج قبل أي استدعاءات عودية
4. Dالاستدعاء الذي يستهلك أكبر قدر من الذاكرة

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

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

ما الخوارزمية؟

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

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

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

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

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

كيف تُقارَن n! و2ⁿ عندما تكون n كبيرة؟

1. A2ⁿ تنمو أسرع من n!
2. Bتنموان بالمعدل نفسه
3. Cn! هي O(n²)
4. Dn! تنمو أسرع من 2ⁿ

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. A3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
2. BSAT العامة على صيغ في الصيغة العادية العطفية
3. C2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
4. Dإرضاء الدارات