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

ماذا تخزّن الخريطة (map أو القاموس)؟

1. Aقيمًا مرتبة بحسب الحجم
2. Bقيمًا فقط بترتيب الإدراج
3. Cأزواج مفتاح–قيمة بمفاتيح فريدة
4. Dأزواجًا من المفاتيح المتساوية

أي بنية بيانات تُستخدم لإجراء اجتياز شجرة مستوى بعد مستوى (level-order)؟

1. Aجدول التجزئة
2. Bالطابور
3. Cالمكدس
4. Dطابور الأولويات

يتكوّن المخطط (graph) من:

1. Aرؤوس (عقد) تربطها حواف
2. Bجذر وأوراق فقط
3. Cصفوف وأعمدة
4. Dمفاتيح وقيم تجزئة فقط

كيف تعمل عملية استخراج الأصغر (extract-min) في كومة ثنائية صغرى؟

1. Aيُبحث في كل الأوراق عن الأصغر الجديد
2. Bيُزال الجذر وتُزاح كل العناصر موضعًا واحدًا إلى اليسار
3. Cيُنقل العنصر الأخير إلى الجذر ويُنزل
4. Dيُزال العنصر الأخير من المصفوفة

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

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 5 2 3 1

أي شرط توازن تحافظ عليه شجرة AVL عند كل عقدة؟

1. Aأن تكون كل الأوراق على العمق نفسه بالضبط
2. Bأن تُلوَّن كل عقدة بالأحمر أو الأسود
3. Cألا يختلف ارتفاعا الشجرتين الفرعيتين اليسرى واليمنى بأكثر من 1
4. Dأن تحتوي الشجرتان الفرعيتان لكل عقدة العدد نفسه تمامًا من العقد

أي ضمان تعطيه قواعد الشجرة الحمراء-السوداء بشأن ارتفاع شجرة فيها n مفتاحًا؟

1. Aالارتفاع log₂ n بالضبط
2. Bالارتفاع لا يتجاوز n / 2
3. Cالارتفاع لا يتجاوز 2 log₂(n + 1)
4. Dالارتفاع لا يتجاوز log₂ n + 1

ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟

1. AO(n²)
2. BO(log n) بالضبط
3. CO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
4. DO(n)