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

في شجرة البحث الثنائية، تكون القيم في الشجرة الفرعية اليسرى لعقدة ما:

1. Aأكبر من قيمة العقدة
2. Bمساوية لقيمة العقدة
3. Cبترتيب عشوائي
4. Dأصغر من قيمة العقدة

في قائمة مترابطة أحادية، ماذا يحتوي مؤشر التالي في العقدة الأخيرة؟

1. Aعنوان العقدة السابقة
2. Bعنوان العقدة الأولى
3. Cعدد العقد في القائمة
4. DNull (لا عقدة)

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

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

في كومة صغرى ثنائية (min-heap) مخزّنة في مصفوفة (يبدأ الفهرس من 0)، يقع ابنا العقدة ذات الفهرس i في:

1. Ai/2 و i/2 + 1
2. B2i و 2i + 1
3. C2i + 1 و 2i + 2
4. Di + 1 و i + 2

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

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

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

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

ما بنية البيانات التي تدعم ذاكرة تخزين مؤقت LRU (least recently used) بعمليتي get وput في O(1)؟

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

أي مشكلة من مشكلات التقصّي الخطي تقللها التجزئة المزدوجة أساسًا؟

1. Aالتكتل الأولي، حيث تتكوّن سلاسل طويلة من الخانات المشغولة
2. Bكلفة O(n) لقراءة قيمة مفتاح
3. Cالحاجة إلى دالة تجزئة
4. Dالحاجة إلى تخزين المفاتيح في الجدول