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

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

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
2. Bأن f تنمو أسرع من g تمامًا
3. Cأن f تنمو أبطأ من g تمامًا
4. Dأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا

كم ذاكرة إضافية يستخدمها الفرز بالدمج القياسي المعتمد على المصفوفات؟

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

ترتب مصفوفة من n عنصر مرة واحدة ثم تجيب عن k استعلام عضوية بالبحث الثنائي. ما الكلفة الكلية؟

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

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

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

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

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

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

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

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

1. AΘ(n²)
2. BΘ(n log² n)
3. CΘ(n log n)
4. DΘ(n)