1.سهلة
ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟
- AO(k log n)
- BO(n log n)
- CO(n²)
- DO(n + k)
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
أي ترميز يصف حدًا أدنى للنمو؟
- Ao (o الصغير)
- BΘ (ثيتا الكبير)
- CΩ (أوميغا الكبير)
- DO (O الكبير)
3.سهلة
ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟
- AO(n log n)
- BO(log n)
- CO(n)
- DO(1)
4.متوسطة
يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟
- Aمصفوفة طولها 2
- Bمصفوفة بترتيب عشوائي
- Cمصفوفة مرتبة مسبقًا
- Dمصفوفة عناصرها كلها مختلفة
5.متوسطة
لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟
- Aلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
- Bلأن الفرز بالإدراج O(n log n) في أسوأ الحالات
- Cلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
- Dلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر
6.متوسطة
أي خوارزمية فرز مستقرة؟
- Aالفرز بالاختيار (النسخة المعتادة)
- Bالفرز السريع (النسخة الموضعية المعتادة)
- Cالفرز بالدمج
- Dالفرز بالكومة
7.صعبة
كيف تُصنَّف مسألة البائع المتجول؟
- Aتنتمي إلى P لأن خوارزمية Dijkstra تحلها بزيارة كل مدينة مرة واحدة
- Bنسخة القرار في P لكن نسخة التحسين NP-تامة
- Cغير قابلة للحسم
- Dنسخة القرار NP-تامة ونسخة التحسين NP-صعبة
8.صعبة
ما الكلفة المستهلَكة لزيادة عدّاد ثنائي بمقدار واحد، علمًا بأن زيادة واحدة قد تقلب بتات كثيرة؟
- AO(n) لكل زيادة
- BO(1) لكل زيادة
- CO(log n) لكل زيادة
- DO(n log n) لكل زيادة
مفتاح الإجابات
- 1. D · O(n + k)
- 2. C · Ω (أوميغا الكبير)
- 3. C · O(n)
- 4. C · مصفوفة مرتبة مسبقًا
- 5. C · لأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
- 6. C · الفرز بالدمج
- 7. D · نسخة القرار NP-تامة ونسخة التحسين NP-صعبة
- 8. B · O(1) لكل زيادة
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.