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

في تمثيل المخطط بقوائم التجاور، ماذا يُخزَّن لكل رأس؟

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

في المخطط، ما الدورة؟

1. Aرأس ليست له حواف
2. Bمسار يزور كل رأس
3. Cحافة وزنها صفر
4. Dمسار يبدأ وينتهي عند الرأس نفسه

كم حافة لشجرة فيها n عقدة؟

1. An + 1
2. Bn
3. C2n
4. Dn − 1

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

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

ما كلفة إدراج عنصر في منتصف مصفوفة من n عنصر؟

1. AO(log n)، بسبب البحث الثنائي
2. BO(n)، لأن العناصر اللاحقة يجب أن تُزاح
3. CO(n²)، لأن كل عنصر يتحرك n مرة
4. DO(1)، لأن الفهرس معروف

طابور منفّذ بمكدسين: push إلى مكدس "in"، وpop من مكدس "out" مع إعادة ملئه من "in" حين يفرغ. ما الكلفة المستهلَكة لكل عملية؟

1. AO(n)
2. BO(1)
3. CO(n²)
4. DO(log n)

خُزّن كائن مفتاحًا في خريطة تجزئة، ثم غُيّر حقل تستخدمه دالة تجزئته. ما النتيجة المرجحة؟

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

في جدول تجزئة يستخدم العنونة المفتوحة، لماذا يُنفَّذ الحذف غالبًا باستخدام علامة "شاهد القبر" (tombstone)؟

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