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

ماذا تحتوي كل عقدة في القائمة المترابطة الثنائية؟

1. Aنسختين من البيانات ومؤشرًا واحدًا
2. Bبيانات ومؤشرين، أحدهما إلى العقدة التالية والآخر إلى العقدة التي تليها
3. Cبيانات ومؤشرًا إلى العقدة التالية فقط
4. Dبيانات، ومؤشرًا إلى العقدة التالية، ومؤشرًا إلى العقدة السابقة

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

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

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

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

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

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

جدول تجزئة حجمه 7 يستخدم h(k) = k mod 7 والتقصّي الخطي (linear probing). بعد إدراج 10، أين يُخزَّن 17؟

1. Aالفهرس 0
2. Bالفهرس 4
3. Cالفهرس 6
4. Dالفهرس 3

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

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

دون الاتحاد بالرتبة أو ضغط المسار، ما كلفة عملية find واحدة في أسوأ الحالات في بنية union-find فيها n عنصر؟

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

أي مشكلة من مشكلات التقصّي الخطي تقللها التجزئة المزدوجة أساسًا؟

1. Aالتكتل الأولي، حيث تتكوّن سلاسل طويلة من الخانات المشغولة
2. Bالحاجة إلى دالة تجزئة
3. Cالحاجة إلى تخزين المفاتيح في الجدول
4. Dكلفة O(n) لقراءة قيمة مفتاح