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

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

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

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

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

ما التصادم (collision) في جدول التجزئة؟

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

في جدول تجزئة يستخدم العنونة المفتوحة، ما أقصى معامل تحميل ممكن؟

1. Aلا يوجد حد أقصى
2. B0,5
3. C2
4. D1

شبكة طرق فيها 100,000 تقاطع، يتصل كل منها بنحو 4 تقاطعات أخرى. أي تمثيل هو الأنسب؟

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

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

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

ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟

1. AO(log n) بالضبط
2. BO(n)
3. CO(n²)
4. DO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا

أي زوج من الاجتيازات يحدد دائمًا شجرة ثنائية فريدة ذات مفاتيح متمايزة؟

1. Aالقبلي والوسطي
2. Bالقبلي وحده
3. Cالقبلي والبعدي
4. Dمستوى بعد مستوى وحده