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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

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

ما العودية (Recursion)؟

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

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

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

ما التعقيد الزمني لخوارزمية Bellman–Ford على رسم بياني فيه V رأسًا وE حافة؟

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

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

أي عبارة صحيحة عن اختيار العنصر الأصغر رقم k في مصفوفة غير مرتبة؟

1. Aيعمل Quickselect في زمن متوقع O(n)، وتضمن طريقة وسيط الوسائط O(n) في أسوأ الحالات
2. Bالاختيار ممكن فقط في O(n²)
3. Cيحتاج الاختيار دائمًا إلى Ω(n log n) لأنه يتطلب الفرز
4. Dيعمل Quickselect في O(log n) في أسوأ الحالات لأنه يعود على جانب واحد فقط من المحور