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

في القائمة المترابطة الأحادية، تحتوي كل عقدة على:

1. Aبيانات وفهرس
2. Bبيانات ومراجع إلى جميع العقد الأخرى
3. Cبيانات فقط
4. Dبيانات ومرجع إلى العقدة التالية

في تمثيل المخطط بقوائم التجاور، ماذا يُخزَّن لكل رأس؟

1. Aقائمة برؤوسه المجاورة
2. Bصف من V قيمة بوليانية
3. Cأقصر مسار إلى كل رأس آخر
4. Dالعدد الكلي للحواف في المخطط

كم حافة لشجرة فيها n عقدة؟

1. An − 1
2. B2n
3. Cn + 1
4. Dn

أي نوع بيانات مجرد تستخدمه خوارزمية Dijkstra لاختيار الرأس التالي للمعالجة؟

1. Aطابور FIFO
2. Bمجموعة بلا ترتيب
3. Cطابور أولويات صغرى
4. Dمكدس

جدول تجزئة حجمه 7 يستخدم h(k) = k mod 7 والتقصّي الخطي (linear probing). بعد إدراج 10، أين يُخزَّن 17؟

1. Aالفهرس 6
2. Bالفهرس 0
3. Cالفهرس 3
4. Dالفهرس 4

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

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

ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟

1. AO(n²)
2. BO(n)
3. CO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
4. DO(log n) بالضبط

تتضاعف مصفوفة ديناميكية حين تمتلئ. لماذا لا تقلصها تطبيقات كثيرة إلا حين تكون ممتلئة بمقدار الربع، لا النصف؟

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