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

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

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

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

1. Aلم يكن بالإمكان حلها إلا بتجربة كل الاحتمالات
2. Bلم يكن لها حل
3. Cأمكن حلها في زمن كثير حدود
4. Dأمكن حلها في زمن ثابت

أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟

1. Aالفرز السريع (Quicksort)
2. Bالفرز بالكومة (Heap sort)
3. Cالفرز بالدمج (Merge sort)
4. Dالفرز الفقاعي (Bubble sort)

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n)
4. DΩ(n log n)

في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟

1. Aاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
2. Bاختر أقصر نشاط أولًا
3. Cاختر النشاط الذي يبدأ أبكر
4. Dاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn log n)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn)

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n log² n)
4. DΘ(n)

تُظهر مسألة التوقف أنه:

1. Aلا توجد خوارزمية تستطيع أن تقرر لكل برنامج ومدخل ما إذا كان البرنامج سيتوقف
2. Bيجب تجنب الحلقات
3. Cبعض البرامج تعمل أسرع على حواسيب أسرع، فيعتمد التوقف على العتاد
4. Dكل برنامج يتوقف في النهاية