1.سهلة
ماذا يُسمى النمو O(2ⁿ)؟
- Aكثير حدود
- Bلوغاريتمي
- Cأسّي
- Dخطي
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
ما قيمة log₂ 1024؟
- A10
- B512
- C32
- D12
3.سهلة
أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟
- AO(n log n)
- BO(2ⁿ)
- CO(n²)
- DO(n³)
4.متوسطة
لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟
- Aلأن الفرز بالدمج O(n) أصلًا
- Bلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
- Cلأن الفرز بالدمج ليس له بنية عودية
- Dلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
5.متوسطة
كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟
- Aنحو 500,000
- Bنحو 100
- Cنحو 20
- Dنحو 1,000
6.متوسطة
أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟
- Aالبحث بالعمق أولًا (DFS)
- Bخوارزمية بيلمان–فورد مطلوبة في جميع الحالات
- Cخوارزمية كروسكال (Kruskal)
- Dخوارزمية ديكسترا (Dijkstra)
7.صعبة
يعمل الفرز بالإدراج في O(n) على المدخلات المرتبة. هل يناقض هذا الحد الأدنى Ω(n log n) للفرز بالمقارنة؟
- Aنعم، لكن فقط للمصفوفات الأقصر من 100
- Bلا، فالحد الأدنى ينطبق على أسوأ الحالات عبر كل المدخلات، لا على كل مدخل
- Cنعم، فالحد الأدنى خاطئ إذن
- Dلا، لأن الفرز بالإدراج ليس فرزًا بالمقارنة
8.صعبة
كيف تُصنَّف مسألة البائع المتجول؟
- Aتنتمي إلى P لأن خوارزمية Dijkstra تحلها بزيارة كل مدينة مرة واحدة
- Bنسخة القرار NP-تامة ونسخة التحسين NP-صعبة
- Cنسخة القرار في P لكن نسخة التحسين NP-تامة
- Dغير قابلة للحسم
مفتاح الإجابات
- 1. C · أسّي
- 2. A · 10
- 3. B · O(2ⁿ)
- 4. D · لأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
- 5. C · نحو 20
- 6. D · خوارزمية ديكسترا (Dijkstra)
- 7. B · لا، فالحد الأدنى ينطبق على أسوأ الحالات عبر كل المدخلات، لا على كل مدخل
- 8. B · نسخة القرار NP-تامة ونسخة التحسين NP-صعبة
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.