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

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

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالقوة الغاشمة
2. Bالبرمجة الديناميكية
3. Cفرّق تسُد
4. Dالاختيار الجشع

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

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

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

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

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

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

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3})، أي نحو n^1,585
4. DΘ(n²)

لماذا يكون متوسط البحث في جدول التجزئة O(1) بينما أسوأ الحالات O(n)؟

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