1.سهلة
كم حافة لشجرة فيها n عقدة؟
- A2n
- Bn − 1
- Cn + 1
- Dn
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
يتكوّن المخطط (graph) من:
- Aرؤوس (عقد) تربطها حواف
- Bمفاتيح وقيم تجزئة فقط
- Cصفوف وأعمدة
- Dجذر وأوراق فقط
3.سهلة
ما خاصية الكومة العظمى (max-heap)؟
- Aمفتاح كل أب أكبر من مفاتيح أبنائه أو يساويها
- Bمفتاح كل ابن أيسر أكبر من مفتاح شقيقه الأيمن أو يساويه
- Cالمفاتيح مرتبة من اليسار إلى اليمين
- Dكل الأوراق تحتوي المفتاح الأكبر
4.متوسطة
تضمن أشجار AVL والأشجار الحمراء-السوداء:
- Aبحثًا في زمن ثابت في جميع الحالات
- Bارتفاعًا قدره O(log n) عبر إعادة التوازن
- Cتخزين المفاتيح بترتيب الإدراج
- Dألا يكون لأي عقدة ابنان
5.متوسطة
ما بنية البيانات التي يستخدمها البحث بالعمق أولًا (DFS، النسخة التكرارية)؟
- Aطابور
- Bمكدس
- Cكومة
- Dجدول تجزئة فقط
6.متوسطة
أي شرط توازن تحافظ عليه شجرة AVL عند كل عقدة؟
- Aأن تكون كل الأوراق على العمق نفسه بالضبط
- Bأن تُلوَّن كل عقدة بالأحمر أو الأسود
- Cأن تحتوي الشجرتان الفرعيتان لكل عقدة العدد نفسه تمامًا من العقد
- Dألا يختلف ارتفاعا الشجرتين الفرعيتين اليسرى واليمنى بأكثر من 1
7.صعبة
في المخزن المؤقت الدائري (circular buffer)، قد يعني front == rear الفراغ أو الامتلاء. ما الطريقة الشائعة للتمييز بينهما؟
- Aجعل حجم المخزن قوة للعدد اثنين
- Bمسح المخزن دائمًا حين يتساوى front وrear، فتكون الحالة فارغة
- Cتخزين front وrear في المتغير نفسه
- Dالاحتفاظ بعدّاد منفصل للعناصر، أو ترك خانة واحدة غير مستخدمة دائمًا
8.صعبة
ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟
- AO(log n) بالضبط
- BO(n)
- CO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
- DO(n²)
مفتاح الإجابات
- 1. B · n − 1
- 2. A · رؤوس (عقد) تربطها حواف
- 3. A · مفتاح كل أب أكبر من مفاتيح أبنائه أو يساويها
- 4. B · ارتفاعًا قدره O(log n) عبر إعادة التوازن
- 5. B · مكدس
- 6. D · ألا يختلف ارتفاعا الشجرتين الفرعيتين اليسرى واليمنى بأكثر من 1
- 7. D · الاحتفاظ بعدّاد منفصل للعناصر، أو ترك خانة واحدة غير مستخدمة دائمًا
- 8. C · O(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.