ورقة عمل الخوارزميات والتعقيد مع الإجابات

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

1. Aنحو n / 2
2. Bنحو n
3. Cنحو log₂ n
4. Dنحو n²

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

ما التعقيد الزمني للفرز بالإدراج في أفضل الحالات، على مصفوفة مرتبة مسبقًا؟

1. AO(n²)
2. BO(1)
3. CO(n log n)
4. DO(n)

ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟

1. AO(n²)
2. BO(n)
3. CO(n log n)
4. DO(2ⁿ)

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر
2. Bلأن الفرز بالإدراج O(n log n) في أسوأ الحالات
3. Cلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
4. Dلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة

يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟

1. Aمصفوفة عناصرها كلها مختلفة
2. Bمصفوفة مرتبة مسبقًا
3. Cمصفوفة بترتيب عشوائي
4. Dمصفوفة طولها 2

ما التعقيد الزمني لـ: for i = 1 to n: for (j = i; j ≤ n; j = j + i) نفّذ عملًا O(1)؟

1. AO(n)
2. BO(n²)
3. CO(n √n)
4. DO(n log n)

ماذا أثبتت مبرهنة Cook–Levin؟

1. Aأن مسألة التوقف غير قابلة للحسم
2. Bأن كل مسألة NP يمكن حلها في زمن أسّي
3. Cأن P لا تساوي NP
4. Dأن مسألة الإرضاء البولياني (SAT) هي NP-تامة