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

ما خاصية الكومة العظمى (max-heap)؟

1. Aمفتاح كل أب أكبر من مفاتيح أبنائه أو يساويها
2. Bالمفاتيح مرتبة من اليسار إلى اليمين
3. Cمفتاح كل ابن أيسر أكبر من مفتاح شقيقه الأيمن أو يساويه
4. Dكل الأوراق تحتوي المفتاح الأكبر

ما المخطط الموجّه؟

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

أي بنية بيانات تعمل وفق مبدأ "الداخل أخيرًا يخرج أولًا" (LIFO)؟

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

لشجرة ثنائية جذرها 1، وابنه الأيسر 2 والأيمن 3، وللعقدة 2 ابنان 4 (أيسر) و5 (أيمن). ما الاجتياز البعدي؟

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

لماذا يمكن تخزين كومة ثنائية في مصفوفة دون أي مؤشرات؟

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

في جدول تجزئة يستخدم العنونة المفتوحة، ما أقصى معامل تحميل ممكن؟

1. Aلا يوجد حد أقصى
2. B2
3. C0,5
4. D1

ما الميزة الرئيسية لقائمة التخطي (skip list) مقارنةً بقائمة مترابطة مرتبة؟

1. Aبحث متوقع في O(log n) باستخدام عدة مستويات من المؤشرات الأمامية
2. Bتخزّن المفاتيح دون ترتيب
3. Cبحث مضمون في O(1) لأن كل عقدة تخزّن مؤشرًا إلى كل عقدة أخرى
4. Dلا تستخدم ذاكرة إضافية

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

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