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

ما السمة المميِّزة للمجموعة (set) بوصفها نوع بيانات مجردًا؟

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

ما الذي يعرّف الشجرة الثنائية؟

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

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

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

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

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

ماذا يحدث حين يُعيد جدول تجزئة التجزئة (rehash) بعد تجاوز معامل تحميله حدًا معينًا؟

1. Aتُحذف أقدم المفاتيح لإفساح المجال
2. Bلا تُنقل إلا المفاتيح المتصادمة إلى قائمة فائض جديدة في نهاية الجدول
3. Cيُحجز جدول أكبر ويُدرج كل مفتاح من جديد
4. Dتُرتَّب المفاتيح الموجودة في مكانها

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

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

كيف تكشف ما إذا كانت قائمة مترابطة أحادية تحتوي دورة باستخدام ذاكرة إضافية O(1)؟

1. Aخزّن كل عقدة مزورة في مجموعة تجزئة
2. Bعُدّ العقد حتى يتجاوز العدد حقل طول القائمة
3. Cحرّك مؤشرًا خطوة واحدة ومؤشرًا آخر خطوتين وتحقق مما إذا التقيا
4. Dرتب القائمة وابحث عن التكرارات

دون الاتحاد بالرتبة أو ضغط المسار، ما كلفة عملية find واحدة في أسوأ الحالات في بنية union-find فيها n عنصر؟

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