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

يُعرَّف ارتفاع الشجرة عادةً بأنه:

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

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

1. An
2. Bn − 1
3. C2n
4. Dn + 1

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

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

في كومة ثنائية مخزّنة في مصفوفة تبدأ من الفهرس 0، أين أبو العقدة ذات الفهرس i؟

1. Aفي الفهرس ⌊(i − 1) / 2⌋
2. Bفي الفهرس 2i + 1
3. Cفي الفهرس ⌊i / 2⌋ + 1
4. Dفي الفهرس i − 1

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

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D1 2 3 4 5

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

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

ما كلفة الزمن والمساحة الإضافية لعكس قائمة مترابطة أحادية في مكانها؟

1. Aزمن O(1) ومساحة إضافية O(1)
2. Bزمن O(n) ومساحة إضافية O(1)
3. Cزمن O(n) ومساحة إضافية O(n)
4. Dزمن O(n log n) ومساحة إضافية O(1)

كم يستغرق البحث عن مفتاح اعتباطي في كومة ثنائية صغرى فيها n عنصر؟

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