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

بأي ترتيب يزور الاجتياز القبلي (preorder) لشجرة ثنائية العقد؟

1. Aالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
2. Bالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
3. Cمستوى بعد مستوى من الأعلى
4. Dالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى

ماذا تفعل دالة التجزئة في جدول التجزئة؟

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

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

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

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

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

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

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

لديك مرجع إلى عقدة في منتصف قائمة. في أي قائمة يمكنك إزالتها في O(1)؟

1. Aالقائمة المترابطة الأحادية
2. Bالمصفوفة المرتبة
3. Cالقائمة المترابطة الثنائية
4. Dالمصفوفة الديناميكية

تريد لكل عنصر في مصفوفة العنصر الأكبر التالي على يمينه، في زمن كلي O(n). أي بنية تساعد؟

1. Aمكدس يحفظ العناصر التي تنتظر إجابتها
2. Bطابور يحفظ كل زوج من العناصر
3. Cشجرة بحث ثنائية يُعاد بناؤها لكل عنصر
4. Dجدول تجزئة لكل العناصر

يُحذف عادةً عقدة لها ابنان من شجرة بحث ثنائية عن طريق:

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