1.سهلة
ما بنية البيانات الأنسب لميزة "تراجع" (undo) في محرر النصوص؟
- Aالمكدس (Stack)
- Bالطابور (Queue)
- Cمجموعة التجزئة
- Dالمخطط (Graph)
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
بأي ترتيب يزور الاجتياز القبلي (preorder) لشجرة ثنائية العقد؟
- Aالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة
- Bالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
- Cالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- Dمستوى بعد مستوى من الأعلى
3.سهلة
يتكوّن المخطط (graph) من:
- Aصفوف وأعمدة
- Bمفاتيح وقيم تجزئة فقط
- Cجذر وأوراق فقط
- Dرؤوس (عقد) تربطها حواف
4.متوسطة
كم يستغرق البحث عن كلمة طولها L في trie بأبجدية ثابتة؟
- AO(L)، بصرف النظر عن عدد الكلمات المخزّنة
- BO(n)، حيث n عدد الكلمات
- CO(log n)، حيث n عدد الكلمات
- DO(L × n)
5.متوسطة
يحتاج تطبيق إلى بحث سريع، وإلى سرد المفاتيح مرتبة والإجابة عن استعلامات المدى. أي بنية هي الأنسب؟
- Aمكدس
- Bشجرة بحث ثنائية متوازنة
- Cقائمة مترابطة غير مرتبة
- Dجدول تجزئة
6.متوسطة
في كومة صغرى ثنائية (min-heap) مخزّنة في مصفوفة (يبدأ الفهرس من 0)، يقع ابنا العقدة ذات الفهرس i في:
- Ai + 1 و i + 2
- Bi/2 و i/2 + 1
- C2i + 1 و 2i + 2
- D2i و 2i + 1
7.صعبة
لماذا قد يختار خادم دالة تجزئته عشوائيًا من عائلة شاملة (universal)؟
- Aلإلغاء الحاجة إلى إعادة تحجيم الجدول
- Bلجعل جدول التجزئة مرتبًا
- Cلضمان عدم تصادم أي مفتاحين أبدًا، أيًّا كانت المفاتيح التي يرسلها المهاجم
- Dلجعل قدرة المهاجم على اختيار مفاتيح كثيرة تتصادم كلها مستبعدة جدًا
8.صعبة
تريد لكل عنصر في مصفوفة العنصر الأكبر التالي على يمينه، في زمن كلي O(n). أي بنية تساعد؟
- Aشجرة بحث ثنائية يُعاد بناؤها لكل عنصر
- Bمكدس يحفظ العناصر التي تنتظر إجابتها
- Cجدول تجزئة لكل العناصر
- Dطابور يحفظ كل زوج من العناصر
مفتاح الإجابات
- 1. A · المكدس (Stack)
- 2. C · العقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
- 3. D · رؤوس (عقد) تربطها حواف
- 4. A · O(L)، بصرف النظر عن عدد الكلمات المخزّنة
- 5. B · شجرة بحث ثنائية متوازنة
- 6. C · 2i + 1 و 2i + 2
- 7. D · لجعل قدرة المهاجم على اختيار مفاتيح كثيرة تتصادم كلها مستبعدة جدًا
- 8. B · مكدس يحفظ العناصر التي تنتظر إجابتها
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.