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

كم ذاكرة إضافية يستخدمها الفرز بالدمج القياسي المعتمد على المصفوفات؟

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

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

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

ما O الكبير للتعبير 3n² + 5n + 2؟

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

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

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

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

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

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

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

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

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

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

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