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

ما الورقة في الشجرة؟

1. Aالعقدة ذات القيمة الأكبر
2. Bعقدة لها ابن واحد بالضبط
3. Cعقدة ليس لها أب
4. Dعقدة ليس لها أبناء

ما الطابور مزدوج الطرفين (deque)؟

1. Aطابور مرتب بحسب الأولوية
2. Bطابور لا يسمح بالإزالة إلا من المؤخرة
3. Cطابوران منفصلان يتشاركان مصفوفة واحدة
4. Dبنية تسمح بالإدراج والإزالة في الطرفين كليهما

بأي ترتيب يزور الاجتياز البعدي (postorder) لشجرة ثنائية العقد؟

1. Aالشجرة الفرعية اليمنى، ثم العقدة، ثم اليسرى
2. Bالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
3. Cالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
4. Dالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة

طابور منفّذ بمكدسين: push إلى مكدس "in"، وpop من مكدس "out" مع إعادة ملئه من "in" حين يفرغ. ما الكلفة المستهلَكة لكل عملية؟

1. AO(1)
2. BO(n²)
3. CO(n)
4. DO(log n)

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

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

ما بنية البيانات التي يستخدمها البحث بالعمق أولًا (DFS، النسخة التكرارية)؟

1. Aطابور
2. Bجدول تجزئة فقط
3. Cكومة
4. Dمكدس

تريد لكل عنصر في مصفوفة العنصر الأكبر التالي على يمينه، في زمن كلي O(n). أي بنية تساعد؟

1. Aجدول تجزئة لكل العناصر
2. Bمكدس يحفظ العناصر التي تنتظر إجابتها
3. Cطابور يحفظ كل زوج من العناصر
4. Dشجرة بحث ثنائية يُعاد بناؤها لكل عنصر

لماذا تُستخدم أشجار B في قواعد البيانات وأنظمة الملفات؟

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