1.سهلة
ماذا تفعل دالة التجزئة في جدول التجزئة؟
- Aترتب المفاتيح في الجدول
- Bتربط المفتاح بفهرس في الجدول
- Cتشفّر القيم في الجدول
- Dتعدّ المفاتيح المخزّنة
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
ما اسم عملية المكدس التي تضيف عنصرًا إلى القمة؟
- APush
- BEnqueue
- CPop
- DPeek
3.سهلة
يتكوّن المخطط (graph) من:
- Aصفوف وأعمدة
- Bمفاتيح وقيم تجزئة فقط
- Cجذر وأوراق فقط
- Dرؤوس (عقد) تربطها حواف
4.متوسطة
كم يستغرق البحث عن كلمة طولها L في trie بأبجدية ثابتة؟
- AO(log n)، حيث n عدد الكلمات
- BO(L)، بصرف النظر عن عدد الكلمات المخزّنة
- CO(L × n)
- DO(n)، حيث n عدد الكلمات
5.متوسطة
كيف يُدرج عنصر جديد في كومة ثنائية؟
- Aيُدرج في موضعه المرتب بإزاحة كل العناصر الأكبر منه موضعًا واحدًا إلى اليمين
- Bيوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
- Cيوضع في الجذر ويُنزل (sift down)
- Dيُعاد بناء الكومة كلها من البداية
6.متوسطة
أي نوع بيانات مجرد تستخدمه خوارزمية Dijkstra لاختيار الرأس التالي للمعالجة؟
- Aطابور أولويات صغرى
- Bمجموعة بلا ترتيب
- Cمكدس
- Dطابور FIFO
7.صعبة
يمكن لمرشّح بلوم (Bloom filter) الإجابة عن سؤال "هل هذا العنصر في المجموعة؟":
- Aمع احتمال سلبيات كاذبة دون إيجابيات كاذبة
- Bمع احتمال إيجابيات كاذبة دون سلبيات كاذبة
- Cللأعداد فقط
- Dبإجابات دقيقة دائمًا
8.صعبة
ما التكلفة المستهلكة (amortised) لكل عملية في بنية union-find (المجموعات المنفصلة) مع الدمج حسب الرتبة وضغط المسار؟
- AO(n²)
- BO(n)
- CO(log n) بالضبط
- DO(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
مفتاح الإجابات
- 1. B · تربط المفتاح بفهرس في الجدول
- 2. A · Push
- 3. D · رؤوس (عقد) تربطها حواف
- 4. B · O(L)، بصرف النظر عن عدد الكلمات المخزّنة
- 5. B · يوضع في نهاية المصفوفة ويُرفع (sift up) ما دام يخالف خاصية الكومة
- 6. A · طابور أولويات صغرى
- 7. B · مع احتمال إيجابيات كاذبة دون سلبيات كاذبة
- 8. D · O(α(n))، أي دالة أكرمان العكسية، وهي ثابتة عمليًا
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.