1.سهلة
ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟
- AO(log n)
- BO(n²)
- CO(n)
- DO(1)
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
كيف يعمل الفرز بالاختيار (Selection sort)؟
- Aيقسم المصفوفة إلى نصفين ثم يدمجهما
- Bيُدرج كل عنصر في جزء مرتب متنامٍ بالإزاحة
- Cيبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ
- Dيجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة
3.سهلة
أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟
- Aالفرز بالدمج
- Bالفرز بالإدراج
- Cالفرز السريع (Quicksort)
- Dالفرز الفقاعي
4.متوسطة
ماذا يعني أن لمسألة بنية فرعية مثلى؟
- Aأنه يمكن حل المسألة في زمن ثابت
- Bأن للمسألة حلًا أمثل واحدًا بالضبط تشترك فيه كل مسألة فرعية
- Cأن لكل المسائل الفرعية الحجم نفسه
- Dأنه يمكن بناء حل أمثل من الحلول المثلى لمسائلها الفرعية
5.متوسطة
ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟
- AO(n)
- BO(2ⁿ)
- CO(n log n)
- DO(n²)
6.متوسطة
الخوارزمية الجشعة (Greedy):
- Aتجرّب كل حل ممكن
- Bتتخذ الخيار الأفضل محليًا في كل خطوة
- Cتعطي الحل الأمثل دائمًا
- Dتستخدم العودية فقط
7.صعبة
لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟
- Aلأن القوائم المترابطة لا يمكن فرزها
- Bلأن المقارنات على عقد القائمة المترابطة أبطأ
- Cلأن الوصول إلى العنصر الأوسط يستغرق O(n) خطوة، إذ لا وصول مباشر بالفهرس
- Dلأن البحث الثنائي يحتاج إلى ضعف الذاكرة على الأقل
8.صعبة
ما التعقيد الزمني لبناء كومة ثنائية من n عنصر غير مرتب بالطريقة التصاعدية (bottom-up)؟
- AO(log n)
- BO(n)
- CO(n²)
- DO(n log n)
مفتاح الإجابات
- 1. C · O(n)
- 2. D · يجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة
- 3. C · الفرز السريع (Quicksort)
- 4. D · أنه يمكن بناء حل أمثل من الحلول المثلى لمسائلها الفرعية
- 5. B · O(2ⁿ)
- 6. B · تتخذ الخيار الأفضل محليًا في كل خطوة
- 7. C · لأن الوصول إلى العنصر الأوسط يستغرق O(n) خطوة، إذ لا وصول مباشر بالفهرس
- 8. B · O(n)
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.