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