1.سهلة
ما جذر الشجرة؟
- Aالعقدة ذات القيمة الأكبر
- Bأي عقدة في المنتصف
- Cعقدة ليس لها أبناء
- Dالعقدة العليا التي ليس لها أب
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
في شجرة البحث الثنائية، تكون القيم في الشجرة الفرعية اليسرى لعقدة ما:
- Aأكبر من قيمة العقدة
- Bأصغر من قيمة العقدة
- Cمساوية لقيمة العقدة
- Dبترتيب عشوائي
3.سهلة
أي بنية بيانات تُستخدم لإجراء اجتياز شجرة مستوى بعد مستوى (level-order)؟
- Aطابور الأولويات
- Bالمكدس
- Cالطابور
- Dجدول التجزئة
4.متوسطة
كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟
- AO(log V)
- BO(1)
- CO(E)
- DO(V)
5.متوسطة
أي بنية بيانات تُستخدم للتحقق من توازن الأقواس في "{[()]}"؟
- Aشجرة البحث الثنائية
- Bالمكدس
- Cالطابور
- Dجدول التجزئة
6.متوسطة
لماذا يكون اجتياز مصفوفة عمليًا أسرع غالبًا بكثير من اجتياز قائمة مترابطة بالطول نفسه؟
- Aلأن القوائم المترابطة تخزّن العناصر على القرص دائمًا
- Bلأن عناصر المصفوفة متجاورة، فتستفيد جيدًا من ذاكرة التخزين المؤقت (cache) للمعالج
- Cلأن المصفوفات تستخدم تعليمات أقل لمقارنة القيم
- Dلأن اجتياز المصفوفة O(1) في المجموع، بينما اجتياز القائمة المترابطة O(n)
7.صعبة
عقدة في شجرة AVL غير متوازنة لأن الشجرة الفرعية اليمنى لابنها الأيسر صارت أطول من اللازم (حالة يسار-يمين). أي إصلاح يُطبَّق؟
- Aدوران إلى اليمين عند الابن الأيسر، ثم دوران إلى اليسار عند العقدة
- Bدوران إلى اليسار عند الابن الأيسر، ثم دوران إلى اليمين عند العقدة
- Cدوران واحد إلى اليسار عند العقدة
- Dدوران واحد إلى اليمين عند العقدة
8.صعبة
دون الاتحاد بالرتبة أو ضغط المسار، ما كلفة عملية find واحدة في أسوأ الحالات في بنية union-find فيها n عنصر؟
- AO(1)
- BO(log n)
- CO(α(n))
- DO(n)
مفتاح الإجابات
- 1. D · العقدة العليا التي ليس لها أب
- 2. B · أصغر من قيمة العقدة
- 3. C · الطابور
- 4. B · O(1)
- 5. B · المكدس
- 6. B · لأن عناصر المصفوفة متجاورة، فتستفيد جيدًا من ذاكرة التخزين المؤقت (cache) للمعالج
- 7. B · دوران إلى اليسار عند الابن الأيسر، ثم دوران إلى اليمين عند العقدة
- 8. D · O(n)
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.