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

ورقة عمل مجانية قابلة للطباعة في الخوارزميات والتعقيد: 8 مسألة من السهل إلى مستوى الامتحان، مع مفتاح الإجابات. اطبعها أو احفظها بصيغة PDF.

ورقة عمل جديدةتدرّب عبر الإنترنت مع التلميحات

للمعلمين: يمكن طباعتها ونسخها واستخدامها في الصف مجانًا. كل ورقة عمل جديدة لها قيم جديدة ومفتاح إجابات خاص بها. نقدّر إضافة رابط إلى ExamProblems في صفحة مقررك.

الاسم: ____________________   التاريخ: ____________

1.سهلة

ما قيمة log₂ 1024؟

  1. A10
  2. B32
  3. C12
  4. D512
2.سهلة

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

  1. AΘ (ثيتا الكبير)
  2. BO (O الكبير)
  3. CΩ (أوميغا الكبير)
  4. Do (o الصغير)
3.سهلة

ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟

  1. AO(n log n)
  2. BO(n)
  3. CO(log n)
  4. DO(1)
4.متوسطة

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

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n²)
5.متوسطة

ماذا يقيس التحليل المستهلَك (amortised)؟

  1. Aكلفة الخوارزمية على أفضل مدخل
  2. Bمتوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
  3. Cالكلفة المتوقعة على مدخلات عشوائية
  4. Dكلفة أغلى عملية منفردة في أي موضع من السلسلة
6.متوسطة

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

  1. AO(n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(log n)
7.صعبة

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(n)
  4. DO(log n)
8.صعبة

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

  1. Aتصبح كل الخوارزميات ذات الزمن الأسّي خطية فورًا
  2. Bتصبح مسألة التوقف قابلة للحسم
  3. Cيمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
  4. Dتنتقل تلك المسألة وحدها إلى P

مفتاح الإجابات

  1. 1. A · 10
  2. 2. C · Ω (أوميغا الكبير)
  3. 3. B · O(n)
  4. 4. A · Ω(n log n)
  5. 5. B · متوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
  6. 6. B · O(n²)
  7. 7. C · O(n)
  8. 8. C · يمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP

حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.