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

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

الوصول إلى عنصر في مصفوفة عبر فهرسه يستغرق:

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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

يجد البحث بالعرض أولًا في رسم بياني غير موزون:

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

أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟

1. Aالبحث بالعمق أولًا (DFS)
2. Bخوارزمية كروسكال (Kruskal)
3. Cخوارزمية ديكسترا (Dijkstra)
4. Dخوارزمية بيلمان–فورد مطلوبة في جميع الحالات

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

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

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

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. An = o(n)، لأن كل دالة هي o صغير لنفسها
2. B2n = o(n)، لأن 2n تنمو ببطء
3. Cn = o(n²)، لكن n ليست o(n)
4. Dn² = o(n)