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

يقيس التعقيد المكاني:

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

ما التعقيد الزمني للفرز بالدمج في أسوأ الحالات؟

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

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

1. Aأوميغا الصغير (Little omega)
2. Bأوميغا الكبير (Big Omega)
3. Cثيتا الكبير (Big Theta)
4. DO الكبير (Big O)

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

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

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
2. Bتحذف أغلى حافة حتى لا تبقى دورات
3. Cترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة
4. Dتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS

أي خوارزمية فرز مستقرة؟

1. Aالفرز بالدمج
2. Bالفرز السريع (النسخة الموضعية المعتادة)
3. Cالفرز بالكومة
4. Dالفرز بالاختيار (النسخة المعتادة)

أي حد صحيح لـ log(n!)؟

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(2^n²)
2. BO(n³)
3. CO(n² 2ⁿ)
4. DO(n!)