1.سهلة
في المخطط، ما الدورة؟
- Aمسار يزور كل رأس
- Bحافة وزنها صفر
- Cرأس ليست له حواف
- Dمسار يبدأ وينتهي عند الرأس نفسه
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
أي عملية تكون O(1) للمصفوفة لكن O(n) للقائمة المترابطة الأحادية؟
- Aقراءة العنصر الأول
- Bإزالة عنصر الرأس
- Cالوصول إلى العنصر ذي الفهرس i
- Dالإدراج في الرأس
3.سهلة
ما الورقة في الشجرة؟
- Aعقدة لها ابن واحد بالضبط
- Bعقدة ليس لها أبناء
- Cالعقدة ذات القيمة الأكبر
- Dعقدة ليس لها أب
4.متوسطة
كيف يُدرج عنصر جديد في كومة ثنائية؟
- Aيُدرج في موضعه المرتب بإزاحة كل العناصر الأكبر منه موضعًا واحدًا إلى اليمين
- Bيُعاد بناء الكومة كلها من البداية
- Cيوضع في الجذر ويُنزل (sift down)
- Dيوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
5.متوسطة
تضمن أشجار AVL والأشجار الحمراء-السوداء:
- Aألا يكون لأي عقدة ابنان
- Bارتفاعًا قدره O(log n) عبر إعادة التوازن
- Cتخزين المفاتيح بترتيب الإدراج
- Dبحثًا في زمن ثابت في جميع الحالات
6.متوسطة
أي طريقة لحل التصادمات تخزّن المفاتيح المتصادمة في قائمة داخل الدلو نفسه؟
- Aالسبر التربيعي
- Bالتجزئة المزدوجة
- Cالتسلسل المنفصل (separate chaining)
- Dالسبر الخطي
7.صعبة
يمكن لمرشّح بلوم (Bloom filter) الإجابة عن سؤال "هل هذا العنصر في المجموعة؟":
- Aللأعداد فقط
- Bمع احتمال سلبيات كاذبة دون إيجابيات كاذبة
- Cمع احتمال إيجابيات كاذبة دون سلبيات كاذبة
- Dبإجابات دقيقة دائمًا
8.صعبة
يُحذف عادةً عقدة لها ابنان من شجرة بحث ثنائية عن طريق:
- Aإزالة الشجرة الفرعية بأكملها
- Bمبادلتها مع الجذر
- Cإعادة بناء الشجرة الفرعية تحتها من الصفر وإعادة إدراج كل مفتاح كانت تحتويه
- Dاستبدالها بخلفها في الترتيب الداخلي (أو سلفها) ثم حذف تلك العقدة
مفتاح الإجابات
- 1. D · مسار يبدأ وينتهي عند الرأس نفسه
- 2. C · الوصول إلى العنصر ذي الفهرس i
- 3. B · عقدة ليس لها أبناء
- 4. D · يوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
- 5. B · ارتفاعًا قدره O(log n) عبر إعادة التوازن
- 6. C · التسلسل المنفصل (separate chaining)
- 7. C · مع احتمال إيجابيات كاذبة دون سلبيات كاذبة
- 8. D · استبدالها بخلفها في الترتيب الداخلي (أو سلفها) ثم حذف تلك العقدة
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.