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

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

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

أي بنية بيانات تعمل وفق مبدأ "الداخل أخيرًا يخرج أولًا" (LIFO)؟

1. Aالقائمة المترابطة
2. Bالمكدس (Stack)
3. Cجدول التجزئة
4. Dالطابور (Queue)

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

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

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

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

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

1. A0,5
2. B2
3. Cلا يوجد حد أقصى
4. D1

ما التعقيد الزمني للبحث عن مفتاح في شجرة بحث ثنائية متوازنة؟

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

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

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

يجب أن تحتفظ بأصغر k قيمة من تدفق من n عددًا باستخدام ذاكرة O(k). أي طريقة تعمل في زمن O(n log k)؟

1. Aطابور FIFO لآخر k قيمة
2. Bمصفوفة مرتبة لكل القيم n
3. Cكومة صغرى تحمل القيم n كلها، تُستخرج منها أصغر k قيمة في النهاية
4. Dكومة عظمى حجمها k، يُستبدل جذرها حين تصل قيمة أصغر