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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

1. Aالقراءة، والحساب، والكتابة
2. Bالتخمين، والتحقق، والتكرار
3. Cالفرز، والبحث، والإرجاع
4. Dالتقسيم، والحل، والدمج

ما العودية (Recursion)؟

1. Aنوع من بنى البيانات
2. Bطريقة فرز
3. Cحلقة لا تنتهي أبدًا
4. Dدالة تستدعي نفسها على مدخلات أصغر

ماذا يُسمى النمو O(2ⁿ)؟

1. Aكثير حدود
2. Bلوغاريتمي
3. Cأسّي
4. Dخطي

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

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

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

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

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

لماذا يحتاج أي بحث قائم على المقارنة في مصفوفة مرتبة إلى Ω(log n) مقارنة في أسوأ الحالات؟

1. Aلأن البحث الثنائي هو الخوارزمية الوحيدة الممكنة، وهو يحتاج إلى log₂ n مقارنة
2. Bلأن كل عنصر يجب أن يُقارَن مرة واحدة على الأقل
3. Cلأن كل مقارنة تستغرق زمنًا لوغاريتميًا
4. Dلأن شجرة قرار لها n نتيجة ممكنة يجب أن يكون عمقها log₂ n على الأقل

ما التعقيد الزمني لبناء كومة ثنائية من n عنصر غير مرتب بالطريقة التصاعدية (bottom-up)؟

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