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

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

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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

ما التعقيد الزمني للفرز بالإدراج في أسوأ الحالات؟

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

أي عبارة صحيحة عن دالة عودية ليس لها حالة أساس قابلة للبلوغ؟

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 4 قطع، والأمثل 3
2. Bتستخدم الجشعة قطعتين، والأمثل 2
3. Cتستخدم الجشعة 3 قطع، والأمثل 3
4. Dتستخدم الجشعة 3 قطع، والأمثل 2

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
2. Bلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
3. Cلا، لأن n³ أصغر من n² عندما تكون n كبيرة
4. Dنعم، لكن فقط إذا كانت n أصغر من 100

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

1. Aفرز المدخلات قبل تشغيل الفرز السريع
2. Bاختيار المحور عشوائيًا بتوزيع منتظم
3. Cاستخدام العودية على الجانب الأيسر فقط
4. Dاختيار العنصر الأول دائمًا

لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟

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