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

في قائمة مترابطة أحادية، ماذا يحتوي مؤشر التالي في العقدة الأخيرة؟

1. Aعنوان العقدة الأولى
2. Bعنوان العقدة السابقة
3. CNull (لا عقدة)
4. Dعدد العقد في القائمة

يتكوّن المخطط (graph) من:

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. B(i + 1) mod n
3. C2i + 1
4. Di + 1

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

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

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

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

أي ضمان تعطيه قواعد الشجرة الحمراء-السوداء بشأن ارتفاع شجرة فيها n مفتاحًا؟

1. Aالارتفاع لا يتجاوز 2 log₂(n + 1)
2. Bالارتفاع لا يتجاوز n / 2
3. Cالارتفاع لا يتجاوز log₂ n + 1
4. Dالارتفاع log₂ n بالضبط

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

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