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

أي عملية بطيئة في المصفوفة لكنها سريعة في بداية القائمة المترابطة؟

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

ماذا تفعل دالة التجزئة في جدول التجزئة؟

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

ما جذر الشجرة؟

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

في طابور دائري مخزّن في مصفوفة سعتها n، كيف يُحسب الموضع التالي بعد الفهرس i؟

1. A(i + 1) mod n
2. B2i + 1
3. C(i − 1) mod n
4. Di + 1

لماذا يكون اجتياز مصفوفة عمليًا أسرع غالبًا بكثير من اجتياز قائمة مترابطة بالطول نفسه؟

1. Aلأن المصفوفات تستخدم تعليمات أقل لمقارنة القيم
2. Bلأن القوائم المترابطة تخزّن العناصر على القرص دائمًا
3. Cلأن عناصر المصفوفة متجاورة، فتستفيد جيدًا من ذاكرة التخزين المؤقت (cache) للمعالج
4. Dلأن اجتياز المصفوفة O(1) في المجموع، بينما اجتياز القائمة المترابطة O(n)

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

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

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

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

لكي يعمل جدول التجزئة بشكل صحيح، أي قاعدة يجب أن تتبعها التجزئة والمساواة؟

1. Aيجب أن تكون قيم التجزئة أعدادًا أولية
2. Bتساوي قيم التجزئة يستلزم تساوي المفاتيح
3. Cيجب أن تكون للمفاتيح المختلفة قيم تجزئة مختلفة
4. Dيجب أن تكون للمفاتيح المتساوية قيم تجزئة متساوية