1.سهلة
ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟
- AO(n)
- BO(log n)
- CO(1)
- DO(n²)
ورقة عمل الخوارزميات والتعقيد مع الإجابات
2.سهلة
أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟
- AO(n log n)
- BO(n²)
- CO(log n)
- DO(n)
3.سهلة
أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟
- Aالفرز بالدمج (Merge sort)
- Bالفرز الفقاعي (Bubble sort)
- Cالفرز بالكومة (Heap sort)
- Dالفرز السريع (Quicksort)
4.متوسطة
يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟
- Aمصفوفة بترتيب عشوائي
- Bمصفوفة عناصرها كلها مختلفة
- Cمصفوفة طولها 2
- Dمصفوفة مرتبة مسبقًا
5.متوسطة
أي خوارزمية فرز مستقرة؟
- Aالفرز السريع (النسخة الموضعية المعتادة)
- Bالفرز بالكومة
- Cالفرز بالدمج
- Dالفرز بالاختيار (النسخة المعتادة)
6.متوسطة
ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟
- AO(2ⁿ)
- BO(n)
- CO(n²)
- DO(n log n)
7.صعبة
ماذا أثبتت مبرهنة Cook–Levin؟
- Aأن مسألة الإرضاء البولياني (SAT) هي NP-تامة
- Bأن مسألة التوقف غير قابلة للحسم
- Cأن P لا تساوي NP
- Dأن كل مسألة NP يمكن حلها في زمن أسّي
8.صعبة
يمكن إيجاد أقصر المسارات البسيطة في زمن كثير حدود. ما المعروف عن إيجاد أطول مسار بسيط بين رأسين في رسم بياني عام؟
- Aأنه يمكن حله بخوارزمية Dijkstra مع أوزان معكوسة الإشارة
- Bأنه قابل للحل دائمًا في O(V + E)
- Cأنه غير قابل للحسم
- Dأنه NP-صعب
مفتاح الإجابات
- 1. A · O(n)
- 2. C · O(log n)
- 3. B · الفرز الفقاعي (Bubble sort)
- 4. D · مصفوفة مرتبة مسبقًا
- 5. C · الفرز بالدمج
- 6. A · O(2ⁿ)
- 7. A · أن مسألة الإرضاء البولياني (SAT) هي NP-تامة
- 8. D · أنه NP-صعب
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.