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

ما بنية البيانات الأنسب لميزة "تراجع" (undo) في محرر النصوص؟

1. Aالطابور (Queue)
2. Bمجموعة التجزئة
3. Cالمخطط (Graph)
4. Dالمكدس (Stack)

ما المخطط الموزون؟

1. Aمخطط مخزّن على القرص
2. Bمخطط بعض رؤوسه أثقل من غيرها لأن لها حوافّ أكثر
3. Cمخطط حوافه أكثر من رؤوسه
4. Dمخطط لكل حافة فيه قيمة عددية كالكلفة أو المسافة

كيف تُخزَّن عناصر المصفوفة في الذاكرة؟

1. Aفي شجرة من صفحات الذاكرة
2. Bفي كتلة واحدة متجاورة، عنصرًا بعد آخر
3. Cمتفرقة، ومربوطة بمؤشرات
4. Dفي مواقع عشوائية تختارها دالة تجزئة

يُستخدم المخزن المؤقت الدائري (ring buffer) عادةً لتنفيذ:

1. Aشجرة بحث ثنائية
2. Bطابور ثابت الحجم
3. Cدالة تجزئة
4. Dاجتياز مخطط

أُدرجت المفاتيح 50، 30، 70، 20، 40 بهذا الترتيب في شجرة بحث ثنائية فارغة. ما الابن الأيسر للعقدة 30؟

1. A20
2. B50
3. C70
4. D40

ما التعقيد الزمني للبحث عن مفتاح في شجرة بحث ثنائية متوازنة؟

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

تزيل خوارزمية Kahn للفرز الطوبولوجي مرارًا الرؤوس ذات درجة الدخول 0. أي بنية تحفظ تلك الرؤوس؟

1. Aمصفوفة تجاور تسجّل الرؤوس التي أُزيلت بالفعل
2. Bمكدس لكل الحواف المزورة
3. Cطابور (أو أي مجموعة) من الرؤوس التي درجة دخولها 0
4. Dكومة عظمى مرتبة بحسب درجة الخروج

التعقيد الزمني لعملية decrease-key في الكومة الثنائية (مع معرفة موضع العنصر) هو:

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