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

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

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

ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟

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

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

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

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

1. Aخطي
2. Bأسّي
3. Cلوغاريتمي
4. Dثابت

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. ASAT العامة على صيغ في الصيغة العادية العطفية
2. B3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
3. C2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
4. Dإرضاء الدارات

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأنها تعمل فقط عندما W = 0
2. Bلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
3. Cلأن n صغيرة دائمًا
4. Dلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل