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

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

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

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

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

ما الخوارزمية؟

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

ما التعقيد الزمني لحساب عدد فيبوناتشي رقم n بجدول تصاعدي (من الأسفل إلى الأعلى)؟

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

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

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

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

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

1. AΘ(n²)
2. BΘ(n^{log₂ 7})، أي نحو n^2,81
3. CΘ(n³)
4. DΘ(n² log n)

أي خوارزمية تجد شجرة ممتدة صغرى بإضافة أرخص ضلع لا يُكوّن دورة بشكل متكرر؟

1. Aخوارزمية فلويد–وارشال
2. Bخوارزمية كروسكال
3. Cخوارزمية ديكسترا
4. Dخوارزمية بريم بدءًا من عقدة واحدة