1.سهلة
ماذا يُسمى النمو O(2ⁿ)؟
- Aلوغاريتمي
- Bخطي
- Cأسّي
- Dكثير حدود
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
تستغرق خوارزمية O(n) ثلاث ثوانٍ عند n = مليون. كم تستغرق تقريبًا عند n = مليونين؟
- A12 ثانية
- B3 ثوانٍ
- C9 ثوانٍ
- D6 ثوانٍ
3.سهلة
ماذا يتطلب البحث الثنائي في مدخلاته؟
- Aأن يكون طول المصفوفة قوة للعدد اثنين
- Bأن تكون المصفوفة مرتبة
- Cألا تحتوي المصفوفة إلا أعدادًا موجبة
- Dألا تتجاوز المصفوفة 1000 عنصر
4.متوسطة
الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:
- AΩ(n log n)
- BΩ(log n)
- CΩ(n²)
- DΩ(n)
5.متوسطة
يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟
- Aمصفوفة بترتيب عشوائي
- Bمصفوفة مرتبة مسبقًا
- Cمصفوفة عناصرها كلها مختلفة
- Dمصفوفة طولها 2
6.متوسطة
ما التعقيد الزمني لخوارزمية Bellman–Ford على رسم بياني فيه V رأسًا وE حافة؟
- AO(V × E)
- BO(V³ × E)
- CO(E log V)
- DO(V + E)
7.صعبة
لماذا قد تعطي خوارزمية Dijkstra نتائج خاطئة حين تكون بعض أوزان الحواف سالبة؟
- Aلأنها تدخل في حلقة لا نهائية عند كل حافة سالبة
- Bلأن الأعداد السالبة لا يمكن تخزينها في طابور أولويات
- Cلأنها لا تعمل إلا على الرسوم البيانية غير الموجهة
- Dلأن الرأس يُثبَّت نهائيًا عند استخراجه، لكن حافة سالبة لاحقة قد تعطيه مسارًا أقصر
8.صعبة
تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟
- Aلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
- Bلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
- Cلأنها تعمل فقط عندما W = 0
- Dلأن n صغيرة دائمًا
مفتاح الإجابات
- 1. C · أسّي
- 2. D · 6 ثوانٍ
- 3. B · أن تكون المصفوفة مرتبة
- 4. A · Ω(n log n)
- 5. B · مصفوفة مرتبة مسبقًا
- 6. A · O(V × E)
- 7. D · لأن الرأس يُثبَّت نهائيًا عند استخراجه، لكن حافة سالبة لاحقة قد تعطيه مسارًا أقصر
- 8. B · لأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.