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

أي عملية تكون O(1) للمصفوفة لكن O(n) للقائمة المترابطة الأحادية؟

1. Aالوصول إلى العنصر ذي الفهرس i
2. Bقراءة العنصر الأول
3. Cإزالة عنصر الرأس
4. Dالإدراج في الرأس

ما جذر الشجرة؟

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

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

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

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

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

في طابور دائري مخزّن في مصفوفة سعتها n، كيف يُحسب الموضع التالي بعد الفهرس i؟

1. A(i − 1) mod n
2. Bi + 1
3. C2i + 1
4. D(i + 1) mod n

لعقدة في شجرة بحث ثنائية شجرة فرعية يمنى. أين يقع تاليها في الترتيب الوسطي (in-order successor)؟

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

يمكن لمرشّح بلوم (Bloom filter) الإجابة عن سؤال "هل هذا العنصر في المجموعة؟":

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

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

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