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

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

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

أي بنية بيانات تُستخدم لإجراء اجتياز شجرة مستوى بعد مستوى (level-order)؟

1. Aالمكدس
2. Bطابور الأولويات
3. Cالطابور
4. Dجدول التجزئة

ما الذي يعرّف الشجرة الثنائية؟

1. Aللشجرة مستويان بالضبط
2. Bتخزّن كل عقدة عددًا ثنائيًا
3. Cلكل عقدة ابنان بالضبط
4. Dلكل عقدة ابنان على الأكثر

أُدرجت المفاتيح 50، 30، 70، 20، 40 بهذا الترتيب في شجرة بحث ثنائية فارغة. ما الابن الأيسر للعقدة 30؟

1. A70
2. B50
3. C40
4. D20

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

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

ما ارتفاع شجرة البحث الثنائية ذات n عقدة في أسوأ الحالات إذا أُدرجت المفاتيح بترتيب تصاعدي؟

1. A1
2. B√n
3. Clog₂ n
4. Dn (تصبح الشجرة قائمة مترابطة)

في المخزن المؤقت الدائري (circular buffer)، قد يعني front == rear الفراغ أو الامتلاء. ما الطريقة الشائعة للتمييز بينهما؟

1. Aالاحتفاظ بعدّاد منفصل للعناصر، أو ترك خانة واحدة غير مستخدمة دائمًا
2. Bتخزين front وrear في المتغير نفسه
3. Cمسح المخزن دائمًا حين يتساوى front وrear، فتكون الحالة فارغة
4. Dجعل حجم المخزن قوة للعدد اثنين

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

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