1.سهلة
ماذا تخزّن الخريطة (map أو القاموس)؟
- Aأزواج مفتاح–قيمة بمفاتيح فريدة
- Bأزواجًا من المفاتيح المتساوية
- Cقيمًا مرتبة بحسب الحجم
- Dقيمًا فقط بترتيب الإدراج
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
في شجرة البحث الثنائية، تكون القيم في الشجرة الفرعية اليسرى لعقدة ما:
- Aأكبر من قيمة العقدة
- Bمساوية لقيمة العقدة
- Cبترتيب عشوائي
- Dأصغر من قيمة العقدة
3.سهلة
بأي ترتيب يزور الاجتياز القبلي (preorder) لشجرة ثنائية العقد؟
- Aمستوى بعد مستوى من الأعلى
- Bالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
- Cالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- Dالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
4.متوسطة
كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟
- AO(V)
- BO(E)
- CO(log V)
- DO(1)
5.متوسطة
ما كلفة إدراج عنصر في منتصف مصفوفة من n عنصر؟
- AO(n)، لأن العناصر اللاحقة يجب أن تُزاح
- BO(log n)، بسبب البحث الثنائي
- CO(n²)، لأن كل عنصر يتحرك n مرة
- DO(1)، لأن الفهرس معروف
6.متوسطة
كيف يُدرج عنصر جديد في كومة ثنائية؟
- Aيُدرج في موضعه المرتب بإزاحة كل العناصر الأكبر منه موضعًا واحدًا إلى اليمين
- Bيوضع في الجذر ويُنزل (sift down)
- Cيوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
- Dيُعاد بناء الكومة كلها من البداية
7.صعبة
التعقيد الزمني لعملية decrease-key في الكومة الثنائية (مع معرفة موضع العنصر) هو:
- AO(n)
- BO(log n)
- CO(1)
- DO(n log n)
8.صعبة
كيف تتفوق شجرة radix (الـ trie المضغوط) على الـ trie العادي؟
- Aتخزّن كل كلمة في جدول تجزئة عند الجذر بدل العقد المنفصلة
- Bترتب أبناء كل عقدة بحسب التكرار
- Cلا تحتفظ إلا بالحرف الأول من كل كلمة
- Dتدمج سلاسل العقد ذات الابن الواحد في حافة واحدة موسومة بسلسلة نصية
مفتاح الإجابات
- 1. A · أزواج مفتاح–قيمة بمفاتيح فريدة
- 2. D · أصغر من قيمة العقدة
- 3. C · العقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- 4. D · O(1)
- 5. A · O(n)، لأن العناصر اللاحقة يجب أن تُزاح
- 6. C · يوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
- 7. B · O(log n)
- 8. D · تدمج سلاسل العقد ذات الابن الواحد في حافة واحدة موسومة بسلسلة نصية
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.