ورقة عمل هياكل البيانات مع الإجابات

عمق العقدة في الشجرة هو:

1. Aعدد أبناء تلك العقدة
2. Bعدد العقد في شجرتها الفرعية
3. Cعدد الحواف من الجذر إلى تلك العقدة
4. Dعدد الحواف من تلك العقدة إلى أعمق ورقة

يخزّن جدول التجزئة (hash table) البيانات على شكل:

1. Aشجرة ذات مفاتيح مرتبة
2. Bقائمة مرتبة فقط
3. Cسلسلة نصية ثابتة الطول
4. Dأزواج مفتاح–قيمة يُحدَّد موقعها بدالة تجزئة

ما التصادم (collision) في جدول التجزئة؟

1. Aأن تنفد ذاكرة الجدول
2. Bأن يُخزَّن مفتاحان متساويان مرتين
3. Cأن يُربط مفتاحان مختلفان بالفهرس نفسه
4. Dألا يمكن تجزئة مفتاح إطلاقًا

لشجرة ثنائية جذرها 1، وابنه الأيسر 2 والأيمن 3، وللعقدة 2 ابنان 4 (أيسر) و5 (أيمن). ما الاجتياز القبلي؟

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D4 2 5 1 3

كيف يُدرج عنصر جديد في كومة ثنائية؟

1. Aيوضع في الجذر ويُنزل (sift down)
2. Bيُعاد بناء الكومة كلها من البداية
3. Cيوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
4. Dيُدرج في موضعه المرتب بإزاحة كل العناصر الأكبر منه موضعًا واحدًا إلى اليمين

جدول تجزئة حجمه 7 يستخدم h(k) = k mod 7 والتقصّي الخطي (linear probing). بعد إدراج 10، أين يُخزَّن 17؟

1. Aالفهرس 6
2. Bالفهرس 4
3. Cالفهرس 3
4. Dالفهرس 0

ما بنية البيانات التي تدعم ذاكرة تخزين مؤقت LRU (least recently used) بعمليتي get وput في O(1)؟

1. Aمكدس فقط
2. Bخريطة تجزئة مع قائمة مترابطة مزدوجة
3. Cشجرة بحث ثنائية فقط
4. Dمصفوفة مرتبة واحدة

لماذا تستخدم قواعد البيانات غالبًا أشجار B+ بدلًا من أشجار B العادية للفهارس؟

1. Aلأن أشجار B+ لا تحتاج إلى التوازن
2. Bلأن أشجار B+ تستخدم عقدًا داخلية ثنائية، ما يقلل عدد قراءات القرص
3. Cلأن كل السجلات في أوراق مترابطة، ما يجعل مسح المدى فعالًا
4. Dلأن أشجار B+ لا تخزّن البيانات إلا في الجذر