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

بأي ترتيب يزور الاجتياز البعدي (postorder) لشجرة ثنائية العقد؟

1. Aالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
2. Bالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
3. Cالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
4. Dالشجرة الفرعية اليمنى، ثم العقدة، ثم اليسرى

ما المخطط الموجّه؟

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

عمق العقدة في الشجرة هو:

1. Aعدد الحواف من تلك العقدة إلى أعمق ورقة
2. Bعدد أبناء تلك العقدة
3. Cعدد الحواف من الجذر إلى تلك العقدة
4. Dعدد العقد في شجرتها الفرعية

ما قيمة التعبير اللاحق (postfix) 3 4 + 2 *؟

1. A14
2. B11
3. C24
4. D10

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

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D1 2 3 4 5

ما الغرض من العقدة الحارسة (sentinel أو dummy) في قائمة مترابطة؟

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

بافتراض التجزئة المنتظمة البسيطة، ما الزمن المتوقع للبحث في جدول تجزئة بالتسلسل فيه n مفتاحًا وm دلوًا؟

1. AO(log n)
2. BO(1 + α)، حيث α = n / m
3. CO(m)
4. DO(n)

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

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