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

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

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

كم حافة لشجرة فيها n عقدة؟

1. An + 1
2. Bn − 1
3. Cn
4. D2n

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

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

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

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

طابور منفّذ بمكدسين: push إلى مكدس "in"، وpop من مكدس "out" مع إعادة ملئه من "in" حين يفرغ. ما الكلفة المستهلَكة لكل عملية؟

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

في جدول تجزئة يستخدم العنونة المفتوحة، ما أقصى معامل تحميل ممكن؟

1. A0,5
2. Bلا يوجد حد أقصى
3. C1
4. D2

إدراج مفتاح في شجرة AVL جعل الشجرة الفرعية اليسرى لعقدة أطول من اللازم، وذهب المفتاح الجديد إلى الشجرة الفرعية اليسرى لابنها الأيسر (حالة يسار-يسار). أي إصلاح يُطبَّق؟

1. Aدوران واحد إلى اليمين عند العقدة غير المتوازنة
2. Bدوران واحد إلى اليسار عند العقدة غير المتوازنة
3. Cإعادة تلوين العقدة وابنها
4. Dدوران إلى اليسار عند الابن، ثم دوران إلى اليمين عند العقدة

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

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