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

يخزّن جدول التجزئة (hash table) البيانات على شكل:

1. Aشجرة ذات مفاتيح مرتبة
2. Bسلسلة نصية ثابتة الطول
3. Cأزواج مفتاح–قيمة يُحدَّد موقعها بدالة تجزئة
4. Dقائمة مرتبة فقط

ما الطابور مزدوج الطرفين (deque)؟

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

ماذا تخزّن الخريطة (map أو القاموس)؟

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

كيف يُدرج عنصر جديد في كومة ثنائية؟

1. Aيُدرج في موضعه المرتب بإزاحة كل العناصر الأكبر منه موضعًا واحدًا إلى اليمين
2. Bيوضع في الجذر ويُنزل (sift down)
3. Cيُعاد بناء الكومة كلها من البداية
4. Dيوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة

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

1. A40
2. B20
3. C70
4. D50

كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟

1. AO(log V)
2. BO(E)
3. CO(1)
4. DO(V)

لكي يعمل جدول التجزئة بشكل صحيح، أي قاعدة يجب أن تتبعها التجزئة والمساواة؟

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

التعقيد الزمني لعملية decrease-key في الكومة الثنائية (مع معرفة موضع العنصر) هو:

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