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

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

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

ماذا تفعل دالة التجزئة في جدول التجزئة؟

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

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

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

ما الصحيح بشأن مصفوفة التجاور لمخطط غير موجّه؟

1. Aأنها مثلثية علوية دائمًا
2. Bأن قطرها الرئيسي يحتوي دائمًا آحادًا
3. Cأن كل صف فيه 1 واحد بالضبط
4. Dأنها متناظرة حول القطر الرئيسي

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

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

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

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

ما الخاصية التي يجب أن تحققها الشجرة الحمراء-السوداء؟

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

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

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