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

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

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

عمق العقدة في الشجرة هو:

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

في مخطط غير موجّه، ما درجة الرأس؟

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

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

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

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

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

كيف تجد المفتاح الأصغر في شجرة بحث ثنائية؟

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

تتضاعف مصفوفة ديناميكية حين تمتلئ. لماذا لا تقلصها تطبيقات كثيرة إلا حين تكون ممتلئة بمقدار الربع، لا النصف؟

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

بافتراض التجزئة المنتظمة البسيطة، ما الزمن المتوقع للبحث في جدول تجزئة بالتسلسل فيه n مفتاحًا وm دلوًا؟

1. AO(log n)
2. BO(1 + α)، حيث α = n / m
3. CO(n)
4. DO(m)