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

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

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

ما معامل التحميل (load factor) لجدول التجزئة؟

1. Aعدد الدلاء مقسومًا على متوسط طول المفاتيح المخزّنة
2. Bعدد العناصر المخزّنة مقسومًا على عدد الدلاء
3. Cعدد التصادمات حتى الآن
4. Dالوقت اللازم لتحميل الجدول من القرص

أي عملية تكون O(1) للمصفوفة لكن O(n) للقائمة المترابطة الأحادية؟

1. Aالوصول إلى العنصر ذي الفهرس i
2. Bالإدراج في الرأس
3. Cإزالة عنصر الرأس
4. Dقراءة العنصر الأول

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

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

تكون شجرة البادئات (trie) فعّالة بشكل خاص في:

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

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

1. A11
2. B10
3. C24
4. D14

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

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

أُدرجت المفاتيح 5، 3، 8، 1 بهذا الترتيب في كومة ثنائية صغرى فارغة قائمة على مصفوفة. ما المصفوفة النهائية؟

1. A[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]