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

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

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

ما بنية البيانات الأنسب لميزة "تراجع" (undo) في محرر النصوص؟

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

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

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

كم يستغرق التحقق من وجود الحافة (u, v) باستخدام مصفوفة التجاور؟

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

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

1. Ai + 1 و i + 2
2. B2i + 1 و 2i + 2
3. C2i و 2i + 1
4. Di/2 و i/2 + 1

ما كلفة إدراج عنصر في منتصف مصفوفة من n عنصر؟

1. AO(n²)، لأن كل عنصر يتحرك n مرة
2. BO(log n)، بسبب البحث الثنائي
3. CO(n)، لأن العناصر اللاحقة يجب أن تُزاح
4. DO(1)، لأن الفهرس معروف

كيف تكشف ما إذا كانت قائمة مترابطة أحادية تحتوي دورة باستخدام ذاكرة إضافية O(1)؟

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

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

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