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

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

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

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

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

ماذا تحتوي كل عقدة في القائمة المترابطة الثنائية؟

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

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

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

في كومة صغرى ثنائية (min-heap) مخزّنة في مصفوفة (يبدأ الفهرس من 0)، يقع ابنا العقدة ذات الفهرس i في:

1. A2i و 2i + 1
2. B2i + 1 و 2i + 2
3. Ci/2 و i/2 + 1
4. Di + 1 و i + 2

كيف تعمل عملية استخراج الأصغر (extract-min) في كومة ثنائية صغرى؟

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

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

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

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

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