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

ما O الكبير للتعبير 3n² + 5n + 2؟

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

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

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

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

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

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aترتيبًا طوبولوجيًا في O(V²)
2. Bشجرة امتداد صغرى في O(E log V)
3. Cأقصر المسارات بين كل أزواج الرؤوس في O(V³)
4. Dأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

1. Aلأن اللوغاريتمات ذات الأسس المختلفة لا تختلف إلا بمعامل ثابت
2. Bكل اللوغاريتمات في علوم الحاسوب أساسها 10، فهو مفهوم ضمنًا
3. Cلأن الأساس لا يهم إلا عندما تكون n صغيرة
4. Dلأن اللوغاريتمات تُقرَّب دائمًا إلى أعداد صحيحة

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

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

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

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

لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟

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