1.سهلة
بأي ترتيب يزور الاجتياز القبلي (preorder) لشجرة ثنائية العقد؟
- Aمستوى بعد مستوى من الأعلى
- Bالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
- Cالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- Dالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
يتكوّن المخطط (graph) من:
- Aصفوف وأعمدة
- Bجذر وأوراق فقط
- Cمفاتيح وقيم تجزئة فقط
- Dرؤوس (عقد) تربطها حواف
3.سهلة
ما اسم عملية الطابور التي تزيل العنصر الموجود في المقدمة؟
- AEnqueue
- BDequeue
- CInsert
- DPush
4.متوسطة
كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟
- AO(E)
- BO(log V)
- CO(V)
- DO(1)
5.متوسطة
لشجرة ثنائية جذرها 1، وابنه الأيسر 2 والأيمن 3، وللعقدة 2 ابنان 4 (أيسر) و5 (أيمن). ما الاجتياز البعدي؟
- A4 5 2 3 1
- B5 4 3 2 1
- C1 2 4 5 3
- D4 2 5 1 3
6.متوسطة
يُستخدم المخزن المؤقت الدائري (ring buffer) عادةً لتنفيذ:
- Aدالة تجزئة
- Bشجرة بحث ثنائية
- Cاجتياز مخطط
- Dطابور ثابت الحجم
7.صعبة
في جدول تجزئة يستخدم العنونة المفتوحة، لماذا يُنفَّذ الحذف غالبًا باستخدام علامة "شاهد القبر" (tombstone)؟
- Aتجعل الجدول مرتبًا
- Bيجب الاحتفاظ بالمفاتيح المحذوفة إلى الأبد لأسباب أمنية، فلا يعاد استخدام الخانات أبدًا
- Cشواهد القبور تسرّع التجزئة
- Dإفراغ الخانة قد يقطع تسلسل السبر لمفاتيح أخرى
8.صعبة
ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟
- AO(n)
- BO(n²)
- CO(log n) بالضبط
- DO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
مفتاح الإجابات
- 1. C · العقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- 2. D · رؤوس (عقد) تربطها حواف
- 3. B · Dequeue
- 4. D · O(1)
- 5. A · 4 5 2 3 1
- 6. D · طابور ثابت الحجم
- 7. D · إفراغ الخانة قد يقطع تسلسل السبر لمفاتيح أخرى
- 8. D · O(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.