1.سهلة
يتكوّن المخطط (graph) من:
- Aصفوف وأعمدة
- Bمفاتيح وقيم تجزئة فقط
- Cجذر وأوراق فقط
- Dرؤوس (عقد) تربطها حواف
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
في تمثيل المخطط بقوائم التجاور، ماذا يُخزَّن لكل رأس؟
- Aصف من V قيمة بوليانية
- Bالعدد الكلي للحواف في المخطط
- Cأقصر مسار إلى كل رأس آخر
- Dقائمة برؤوسه المجاورة
3.سهلة
في قائمة مترابطة أحادية، ماذا يحتوي مؤشر التالي في العقدة الأخيرة؟
- Aعنوان العقدة الأولى
- Bعدد العقد في القائمة
- Cعنوان العقدة السابقة
- DNull (لا عقدة)
4.متوسطة
كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟
- AO(log V)
- BO(1)
- CO(V)
- DO(E)
5.متوسطة
يزور الاجتياز الداخلي (in-order) لشجرة البحث الثنائية المفاتيح:
- Aحسب المستويات
- Bبترتيب تنازلي دائمًا
- Cبترتيب الإدراج
- Dبترتيب تصاعدي (مرتبة)
6.متوسطة
يُستخدم المخزن المؤقت الدائري (ring buffer) عادةً لتنفيذ:
- Aدالة تجزئة
- Bشجرة بحث ثنائية
- Cاجتياز مخطط
- Dطابور ثابت الحجم
7.صعبة
ما الميزة الرئيسية لقائمة التخطي (skip list) مقارنةً بقائمة مترابطة مرتبة؟
- Aبحث مضمون في O(1) لأن كل عقدة تخزّن مؤشرًا إلى كل عقدة أخرى
- Bتخزّن المفاتيح دون ترتيب
- Cبحث متوقع في O(log n) باستخدام عدة مستويات من المؤشرات الأمامية
- Dلا تستخدم ذاكرة إضافية
8.صعبة
تزيل خوارزمية Kahn للفرز الطوبولوجي مرارًا الرؤوس ذات درجة الدخول 0. أي بنية تحفظ تلك الرؤوس؟
- Aمصفوفة تجاور تسجّل الرؤوس التي أُزيلت بالفعل
- Bكومة عظمى مرتبة بحسب درجة الخروج
- Cطابور (أو أي مجموعة) من الرؤوس التي درجة دخولها 0
- Dمكدس لكل الحواف المزورة
مفتاح الإجابات
- 1. D · رؤوس (عقد) تربطها حواف
- 2. D · قائمة برؤوسه المجاورة
- 3. D · Null (لا عقدة)
- 4. B · O(1)
- 5. D · بترتيب تصاعدي (مرتبة)
- 6. D · طابور ثابت الحجم
- 7. C · بحث متوقع في O(log n) باستخدام عدة مستويات من المؤشرات الأمامية
- 8. C · طابور (أو أي مجموعة) من الرؤوس التي درجة دخولها 0
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.