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

ما اسم عملية المكدس التي تضيف عنصرًا إلى القمة؟

1. APeek
2. BPush
3. CPop
4. DEnqueue

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

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

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

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

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

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

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

1. Ai/2 و i/2 + 1
2. B2i + 1 و 2i + 2
3. C2i و 2i + 1
4. Di + 1 و i + 2

كم يستغرق البحث عن كلمة طولها L في trie بأبجدية ثابتة؟

1. AO(log n)، حيث n عدد الكلمات
2. BO(L × n)
3. CO(n)، حيث n عدد الكلمات
4. DO(L)، بصرف النظر عن عدد الكلمات المخزّنة

أي مشكلة من مشكلات التقصّي الخطي تقللها التجزئة المزدوجة أساسًا؟

1. Aالحاجة إلى تخزين المفاتيح في الجدول
2. Bكلفة O(n) لقراءة قيمة مفتاح
3. Cالتكتل الأولي، حيث تتكوّن سلاسل طويلة من الخانات المشغولة
4. Dالحاجة إلى دالة تجزئة

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

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