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

ماذا يُسمى النمو O(2ⁿ)؟

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

ماذا يتطلب البحث الثنائي في مدخلاته؟

1. Aألا تحتوي المصفوفة إلا أعدادًا موجبة
2. Bأن تكون المصفوفة مرتبة
3. Cأن يكون طول المصفوفة قوة للعدد اثنين
4. Dألا تتجاوز المصفوفة 1000 عنصر

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

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

ماذا يعني أن لمسألة بنية فرعية مثلى؟

1. Aأنه يمكن حل المسألة في زمن ثابت
2. Bأن للمسألة حلًا أمثل واحدًا بالضبط تشترك فيه كل مسألة فرعية
3. Cأن لكل المسائل الفرعية الحجم نفسه
4. Dأنه يمكن بناء حل أمثل من الحلول المثلى لمسائلها الفرعية

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

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

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

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

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

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

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

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