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

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

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

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

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

ما معامل التحميل (load factor) لجدول التجزئة؟

1. Aعدد الدلاء مقسومًا على متوسط طول المفاتيح المخزّنة
2. Bعدد التصادمات حتى الآن
3. Cالوقت اللازم لتحميل الجدول من القرص
4. Dعدد العناصر المخزّنة مقسومًا على عدد الدلاء

في كومة ثنائية مخزّنة في مصفوفة تبدأ من الفهرس 0، أين أبو العقدة ذات الفهرس i؟

1. Aفي الفهرس 2i + 1
2. Bفي الفهرس ⌊(i − 1) / 2⌋
3. Cفي الفهرس i − 1
4. Dفي الفهرس ⌊i / 2⌋ + 1

لشجرة ثنائية جذرها 1، وابنه الأيسر 2 والأيمن 3، وللعقدة 2 ابنان 4 (أيسر) و5 (أيمن). ما الاجتياز البعدي؟

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

يزور الاجتياز الداخلي (in-order) لشجرة البحث الثنائية المفاتيح:

1. Aبترتيب تنازلي دائمًا
2. Bبترتيب الإدراج
3. Cحسب المستويات
4. Dبترتيب تصاعدي (مرتبة)

ما الميزة الرئيسية لقائمة التخطي (skip list) مقارنةً بقائمة مترابطة مرتبة؟

1. Aبحث متوقع في O(log n) باستخدام عدة مستويات من المؤشرات الأمامية
2. Bتخزّن المفاتيح دون ترتيب
3. Cبحث مضمون في O(1) لأن كل عقدة تخزّن مؤشرًا إلى كل عقدة أخرى
4. Dلا تستخدم ذاكرة إضافية

كيف تتفوق شجرة radix (الـ trie المضغوط) على الـ trie العادي؟

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