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

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

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

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

أي تعريف للفئة NP صحيح؟

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

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

1. Alog n ضعف الأصغر على الأكثر
2. Bضعف حجم الغطاء الرأسي الأصغر على الأكثر
3. Cغطاء رأسي أصغر دائمًا
4. Dجودته مجهولة مقارنةً بالأمثل