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

ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟

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

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز بالإدراج
2. Bالفرز السريع (Quicksort)
3. Cالفرز بالدمج
4. Dالفرز الفقاعي

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

1. AO(dn log k)
2. BO(d(n + k))
3. CO(n²)
4. DO(n log n)

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

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

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
2. Bلأن الفرز بالدمج O(n) أصلًا
3. Cلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
4. Dلأن الفرز بالدمج ليس له بنية عودية

لأي نوع من مسألة الحقيبة تعطي القاعدة الجشعة "خذ العناصر بترتيب القيمة لكل وحدة وزن" إجابة مثلى دائمًا؟

1. Aالنوعان كلاهما
2. Bحقيبة 0/1، حيث يجب دائمًا أخذ العناصر كاملة
3. Cالحقيبة الكسرية، حيث يجوز تقسيم العناصر
4. Dلا هذا ولا ذاك

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

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