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