1.سهلة
بأي ترتيب يزور الاجتياز البعدي (postorder) لشجرة ثنائية العقد؟
- Aالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- Bالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
- Cالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
- Dالشجرة الفرعية اليمنى، ثم العقدة، ثم اليسرى
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
ما بنية البيانات الأنسب لميزة "تراجع" (undo) في محرر النصوص؟
- Aمجموعة التجزئة
- Bالطابور (Queue)
- Cالمخطط (Graph)
- Dالمكدس (Stack)
3.سهلة
ما الورقة في الشجرة؟
- Aالعقدة ذات القيمة الأكبر
- Bعقدة ليس لها أب
- Cعقدة ليس لها أبناء
- Dعقدة لها ابن واحد بالضبط
4.متوسطة
كم ذاكرة تستخدم قائمة التجاور لمخطط فيه V رأسًا وE حافة؟
- AO(V × E)
- BO(V²)
- CO(V + E)
- DO(E²)
5.متوسطة
ما ارتفاع شجرة البحث الثنائية ذات n عقدة في أسوأ الحالات إذا أُدرجت المفاتيح بترتيب تصاعدي؟
- A√n
- B1
- Cn (تصبح الشجرة قائمة مترابطة)
- Dlog₂ n
6.متوسطة
لماذا يكون اجتياز مصفوفة عمليًا أسرع غالبًا بكثير من اجتياز قائمة مترابطة بالطول نفسه؟
- Aلأن عناصر المصفوفة متجاورة، فتستفيد جيدًا من ذاكرة التخزين المؤقت (cache) للمعالج
- Bلأن اجتياز المصفوفة O(1) في المجموع، بينما اجتياز القائمة المترابطة O(n)
- Cلأن القوائم المترابطة تخزّن العناصر على القرص دائمًا
- Dلأن المصفوفات تستخدم تعليمات أقل لمقارنة القيم
7.صعبة
بافتراض التجزئة المنتظمة البسيطة، ما الزمن المتوقع للبحث في جدول تجزئة بالتسلسل فيه n مفتاحًا وm دلوًا؟
- AO(m)
- BO(1 + α)، حيث α = n / m
- CO(n)
- DO(log n)
8.صعبة
دون الاتحاد بالرتبة أو ضغط المسار، ما كلفة عملية find واحدة في أسوأ الحالات في بنية union-find فيها n عنصر؟
- AO(n)
- BO(1)
- CO(α(n))
- DO(log n)
مفتاح الإجابات
- 1. B · الشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
- 2. D · المكدس (Stack)
- 3. C · عقدة ليس لها أبناء
- 4. C · O(V + E)
- 5. C · n (تصبح الشجرة قائمة مترابطة)
- 6. A · لأن عناصر المصفوفة متجاورة، فتستفيد جيدًا من ذاكرة التخزين المؤقت (cache) للمعالج
- 7. B · O(1 + α)، حيث α = n / m
- 8. A · O(n)
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.