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

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

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aفرّق تسُد
2. Bالبرمجة الديناميكية
3. Cالاختيار الجشع
4. Dالقوة الغاشمة

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 100
2. Bنحو 1,000
3. Cنحو 500,000
4. Dنحو 20

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

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

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

هل 2²ⁿ تنتمي إلى O(2ⁿ)؟

1. Aنعم، لأن كلتيهما أسيتان
2. Bنعم، لأن المعاملات الثابتة في الأس تُهمَل دائمًا في O الكبير
3. Cلا، لأن 2²ⁿ = 4ⁿ و4ⁿ / 2ⁿ = 2ⁿ تنمو بلا حد
4. Dلا، لأن 2²ⁿ تنمو أبطأ من 2ⁿ

ما زمن تنفيذ خوارزمية Dijkstra مع كومة ثنائية على رسم بياني فيه V رأسًا وE حافة؟

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