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

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

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

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

1. Aلم يكن لها حل
2. Bأمكن حلها في زمن ثابت
3. Cلم يكن بالإمكان حلها إلا بتجربة كل الاحتمالات
4. Dأمكن حلها في زمن كثير حدود

ماذا يتطلب البحث الثنائي في مدخلاته؟

1. Aألا تتجاوز المصفوفة 1000 عنصر
2. Bأن تكون المصفوفة مرتبة
3. Cأن يكون طول المصفوفة قوة للعدد اثنين
4. Dألا تحتوي المصفوفة إلا أعدادًا موجبة

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

1. Aنحو n
2. Bنحو n / 2
3. Cنحو log₂ n
4. Dنحو √n

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

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

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

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

أي عبارة عن P و NP صحيحة؟

1. ANP تعني «ليست كثيرة الحدود» (not polynomial)
2. Bلا يمكن التحقق من حلول مسائل NP بسرعة
3. Cثبت أن P ≠ NP
4. Dكل مسألة في P تنتمي أيضًا إلى NP

الفرز الطوبولوجي ممكن فقط في:

1. Aالرسوم البيانية التامة
2. Bالرسوم البيانية الموجهة غير الدورية
3. Cالرسوم البيانية ذات الأوزان السالبة
4. Dالرسوم البيانية غير الموجهة