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

ماذا يتطلب البحث الثنائي في مدخلاته؟

1. Aأن يكون طول المصفوفة قوة للعدد اثنين
2. Bألا تحتوي المصفوفة إلا أعدادًا موجبة
3. Cألا تتجاوز المصفوفة 1000 عنصر
4. Dأن تكون المصفوفة مرتبة

ما التذكير (Memoisation)؟

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

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

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn log n)
4. DO(mn)

هل 2²ⁿ تنتمي إلى O(2ⁿ)؟

1. Aنعم، لأن كلتيهما أسيتان
2. Bنعم، لأن المعاملات الثابتة في الأس تُهمَل دائمًا في O الكبير
3. Cلا، لأن 2²ⁿ = 4ⁿ و4ⁿ / 2ⁿ = 2ⁿ تنمو بلا حد
4. Dلا، لأن 2²ⁿ تنمو أبطأ من 2ⁿ

أي عبارة صحيحة عن اختيار العنصر الأصغر رقم k في مصفوفة غير مرتبة؟

1. Aالاختيار ممكن فقط في O(n²)
2. Bيعمل Quickselect في زمن متوقع O(n)، وتضمن طريقة وسيط الوسائط O(n) في أسوأ الحالات
3. Cيعمل Quickselect في O(log n) في أسوأ الحالات لأنه يعود على جانب واحد فقط من المحور
4. Dيحتاج الاختيار دائمًا إلى Ω(n log n) لأنه يتطلب الفرز