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

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

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

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

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

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

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

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

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

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aنعم، لكن فقط إذا كانت n أصغر من 100
2. Bلا، لأن n³ أصغر من n² عندما تكون n كبيرة
3. Cلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
4. Dنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(m + n)

أي عبارة عن ترميز o الصغير صحيحة؟

1. An² = o(n)
2. Bn = o(n²)، لكن n ليست o(n)
3. Cn = o(n)، لأن كل دالة هي o صغير لنفسها
4. D2n = o(n)، لأن 2n تنمو ببطء

لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟

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