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

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

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

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز الفقاعي
2. Bالفرز بالإدراج
3. Cالفرز السريع (Quicksort)
4. Dالفرز بالدمج

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

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

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

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

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 3 قطع، والأمثل 2
2. Bتستخدم الجشعة 3 قطع، والأمثل 3
3. Cتستخدم الجشعة قطعتين، والأمثل 2
4. Dتستخدم الجشعة 4 قطع، والأمثل 3

ما التعقيد الزمني لـ: for i = 1 to n: for (j = i; j ≤ n; j = j + i) نفّذ عملًا O(1)؟

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

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتتحقق مما إذا كانت لأي حافة وزن سالب
2. Bتعدّ الدورات بالبحث بالعمق أولًا
3. Cبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة
4. Dتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات