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

ما خاصية الكومة العظمى (max-heap)؟

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

ما المخطط الموجّه؟

1. Aمخطط لكل حوافه أوزان
2. Bمخطط يتصل فيه كل زوج من الرؤوس المتمايزة بحافة
3. Cمخطط لا دورات فيه
4. Dمخطط لحوافه اتجاه من رأس إلى آخر

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

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

أُدرجت المفاتيح 50، 30، 70، 20، 40 بهذا الترتيب في شجرة بحث ثنائية فارغة. ما الابن الأيسر للعقدة 30؟

1. A20
2. B40
3. C50
4. D70

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

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

تضمن أشجار AVL والأشجار الحمراء-السوداء:

1. Aارتفاعًا قدره O(log n) عبر إعادة التوازن
2. Bبحثًا في زمن ثابت في جميع الحالات
3. Cألا يكون لأي عقدة ابنان
4. Dتخزين المفاتيح بترتيب الإدراج

أي بنية تتيح حساب الأكبر في كل نافذة حجمها k في مصفوفة بزمن كلي O(n)؟

1. Aكومة صغرى يُعاد بناؤها لكل نافذة
2. Bمصفوفة مرتبة تُحدَّث بالإزاحة
3. Cdeque يحفظ الفهارس بترتيب تنازلي للقيمة
4. Dقائمة مترابطة أحادية لعناصر النافذة

يجب أن تحتفظ بأصغر k قيمة من تدفق من n عددًا باستخدام ذاكرة O(k). أي طريقة تعمل في زمن O(n log k)؟

1. Aمصفوفة مرتبة لكل القيم n
2. Bطابور FIFO لآخر k قيمة
3. Cكومة صغرى تحمل القيم n كلها، تُستخرج منها أصغر k قيمة في النهاية
4. Dكومة عظمى حجمها k، يُستبدل جذرها حين تصل قيمة أصغر