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

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

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

أي ترميز يصف حدًا أدنى للنمو؟

1. Ao (o الصغير)
2. BΘ (ثيتا الكبير)
3. CΩ (أوميغا الكبير)
4. DO (O الكبير)

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(V²)
2. BO(E log V)
3. CO(V × E)
4. DO(V + E)

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

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

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

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

أي عبارة صحيحة عن دالة عودية ليس لها حالة أساس قابلة للبلوغ؟

1. Aيحولها المترجم دائمًا إلى حلقة تنتهي بأمان
2. Bتواصل استدعاء نفسها حتى يفيض مكدّس الاستدعاءات
3. Cتُرجع 0 تلقائيًا
4. Dتعمل في زمن O(1)

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

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²)
4. DΘ(n log² n)