1.سهلة
كيف يعمل الفرز بالاختيار (Selection sort)؟
- Aيُدرج كل عنصر في جزء مرتب متنامٍ بالإزاحة
- Bيبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ
- Cيقسم المصفوفة إلى نصفين ثم يدمجهما
- Dيجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة
2.سهلة
أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟
- Aالفرز السريع (Quicksort)
- Bالفرز الفقاعي
- Cالفرز بالإدراج
- Dالفرز بالدمج
3.سهلة
ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟
- AO(log n)
- BO(n)
- CO(n²)
- DO(2n)
4.متوسطة
في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟
- Aاختر النشاط الذي يبدأ أبكر
- Bاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة
- Cاختر أقصر نشاط أولًا
- Dاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
5.متوسطة
يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟
- Aمصفوفة بترتيب عشوائي
- Bمصفوفة مرتبة مسبقًا
- Cمصفوفة طولها 2
- Dمصفوفة عناصرها كلها مختلفة
6.متوسطة
كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟
- Aنحو 500,000
- Bنحو 20
- Cنحو 1,000
- Dنحو 100
7.صعبة
لماذا يحتاج أي بحث قائم على المقارنة في مصفوفة مرتبة إلى Ω(log n) مقارنة في أسوأ الحالات؟
- Aلأن شجرة قرار لها n نتيجة ممكنة يجب أن يكون عمقها log₂ n على الأقل
- Bلأن كل مقارنة تستغرق زمنًا لوغاريتميًا
- Cلأن كل عنصر يجب أن يُقارَن مرة واحدة على الأقل
- Dلأن البحث الثنائي هو الخوارزمية الوحيدة الممكنة، وهو يحتاج إلى log₂ n مقارنة
8.صعبة
ما التعقيد الزمني لـ: for i = 1 to n: for (j = i; j ≤ n; j = j + i) نفّذ عملًا O(1)؟
- AO(n)
- BO(n²)
- CO(n √n)
- DO(n log n)
مفتاح الإجابات
- 1. D · يجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة
- 2. A · الفرز السريع (Quicksort)
- 3. C · O(n²)
- 4. D · اختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
- 5. B · مصفوفة مرتبة مسبقًا
- 6. B · نحو 20
- 7. A · لأن شجرة قرار لها n نتيجة ممكنة يجب أن يكون عمقها log₂ n على الأقل
- 8. D · O(n log n)
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.