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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

كيف يعمل الفرز بالاختيار (Selection sort)؟

1. Aيُدرج كل عنصر في جزء مرتب متنامٍ بالإزاحة
2. Bيبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ
3. Cيقسم المصفوفة إلى نصفين ثم يدمجهما
4. Dيجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة

كم ذاكرة إضافية يستخدمها الفرز بالدمج القياسي المعتمد على المصفوفات؟

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

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

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 3 قطع، والأمثل 3
2. Bتستخدم الجشعة 3 قطع، والأمثل 2
3. Cتستخدم الجشعة قطعتين، والأمثل 2
4. Dتستخدم الجشعة 4 قطع، والأمثل 3

ما الكلفة الزمنية والمكانية لحساب عدد فيبوناتشي رقم n بحلقة لا تحتفظ إلا بآخر قيمتين؟

1. Aزمن O(log n) ومساحة O(n)
2. Bزمن O(2ⁿ) ومساحة O(1)
3. Cزمن O(n) ومساحة O(1)
4. Dزمن O(n) ومساحة O(n)

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

1. AΘ(n^{log₂ 3})، أي نحو n^1,585
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)