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

أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟

1. Aالفرز السريع (Quicksort)
2. Bالفرز بالكومة (Heap sort)
3. Cالفرز الفقاعي (Bubble sort)
4. Dالفرز بالدمج (Merge sort)

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو أسرع من g تمامًا
2. Bأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا
3. Cأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
4. Dأن f تنمو أبطأ من g تمامًا

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

1. Aنحو n
2. Bنحو log₂ n
3. Cنحو n²
4. Dنحو n / 2

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

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

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

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

1. Aنحو √n
2. Bنحو n
3. Cنحو log₂ n
4. Dنحو n / 2

لأي نوع من مسألة الحقيبة تعطي القاعدة الجشعة "خذ العناصر بترتيب القيمة لكل وحدة وزن" إجابة مثلى دائمًا؟

1. Aحقيبة 0/1، حيث يجب دائمًا أخذ العناصر كاملة
2. Bلا هذا ولا ذاك
3. Cالنوعان كلاهما
4. Dالحقيبة الكسرية، حيث يجوز تقسيم العناصر

ما التعقيد الزمني لبناء كومة ثنائية من n عنصر غير مرتب بالطريقة التصاعدية (bottom-up)؟

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