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

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

1. An − 1
2. B2n
3. Cn + 1
4. Dn

في الشجرة، ما العقد الأشقاء؟

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

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

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

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

1. A10
2. B11
3. C24
4. D14

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

1. A2i + 1 و 2i + 2
2. B2i و 2i + 1
3. Ci/2 و i/2 + 1
4. Di + 1 و i + 2

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

1. A40
2. B70
3. C20
4. D50

شجرة Fenwick (الشجرة المفهرسة ثنائيًا) على مصفوفة من n عددًا تدعم أي عمليات في O(log n)؟

1. Aإيجاد الوسيط في O(1)
2. Bإدراج العناصر في أي موضع
3. Cفرز المصفوفة والبحث الثنائي
4. Dاستعلامات مجموع البادئة وتحديثات العنصر الواحد

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

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