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

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

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

تستغرق خوارزمية O(n) ثلاث ثوانٍ عند n = مليون. كم تستغرق تقريبًا عند n = مليونين؟

1. A3 ثوانٍ
2. B9 ثوانٍ
3. C12 ثانية
4. D6 ثوانٍ

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

1. Aنحو n
2. Bنحو n²
3. Cنحو n / 2
4. Dنحو log₂ n

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
2. Bلأن الفرز بالدمج ليس له بنية عودية
3. Cلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
4. Dلأن الفرز بالدمج O(n) أصلًا

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
2. Bترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة
3. Cتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
4. Dتحذف أغلى حافة حتى لا تبقى دورات

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

1. AO(d(n + k))
2. BO(dn log k)
3. CO(n log n)
4. DO(n²)

أي تعريف للفئة P صحيح؟

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

تكون المسألة NP-كاملة (NP-complete) إذا كانت:

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