1.سهلة
يتكوّن المخطط (graph) من:
- Aمفاتيح وقيم تجزئة فقط
- Bجذر وأوراق فقط
- Cصفوف وأعمدة
- Dرؤوس (عقد) تربطها حواف
ورقة عمل هياكل البيانات مع الإجابات
2.سهلة
ما الورقة في الشجرة؟
- Aعقدة ليس لها أبناء
- Bالعقدة ذات القيمة الأكبر
- Cعقدة ليس لها أب
- Dعقدة لها ابن واحد بالضبط
3.سهلة
في المخطط، ما الدورة؟
- Aمسار يبدأ وينتهي عند الرأس نفسه
- Bمسار يزور كل رأس
- Cحافة وزنها صفر
- Dرأس ليست له حواف
4.متوسطة
تضمن أشجار AVL والأشجار الحمراء-السوداء:
- Aتخزين المفاتيح بترتيب الإدراج
- Bألا يكون لأي عقدة ابنان
- Cبحثًا في زمن ثابت في جميع الحالات
- Dارتفاعًا قدره O(log n) عبر إعادة التوازن
5.متوسطة
لديك مرجع إلى عقدة في منتصف قائمة. في أي قائمة يمكنك إزالتها في O(1)؟
- Aالمصفوفة المرتبة
- Bالقائمة المترابطة الأحادية
- Cالمصفوفة الديناميكية
- Dالقائمة المترابطة الثنائية
6.متوسطة
في كومة ثنائية مخزّنة في مصفوفة تبدأ من الفهرس 0، أين أبو العقدة ذات الفهرس i؟
- Aفي الفهرس 2i + 1
- Bفي الفهرس i − 1
- Cفي الفهرس ⌊i / 2⌋ + 1
- Dفي الفهرس ⌊(i − 1) / 2⌋
7.صعبة
يُحذف عادةً عقدة لها ابنان من شجرة بحث ثنائية عن طريق:
- Aإزالة الشجرة الفرعية بأكملها
- Bاستبدالها بخلفها في الترتيب الداخلي (أو سلفها) ثم حذف تلك العقدة
- Cإعادة بناء الشجرة الفرعية تحتها من الصفر وإعادة إدراج كل مفتاح كانت تحتويه
- Dمبادلتها مع الجذر
8.صعبة
بافتراض التجزئة المنتظمة البسيطة، ما الزمن المتوقع للبحث في جدول تجزئة بالتسلسل فيه n مفتاحًا وm دلوًا؟
- AO(n)
- BO(m)
- CO(1 + α)، حيث α = n / m
- DO(log n)
مفتاح الإجابات
- 1. D · رؤوس (عقد) تربطها حواف
- 2. A · عقدة ليس لها أبناء
- 3. A · مسار يبدأ وينتهي عند الرأس نفسه
- 4. D · ارتفاعًا قدره O(log n) عبر إعادة التوازن
- 5. D · القائمة المترابطة الثنائية
- 6. D · في الفهرس ⌊(i − 1) / 2⌋
- 7. B · استبدالها بخلفها في الترتيب الداخلي (أو سلفها) ثم حذف تلك العقدة
- 8. C · O(1 + α)، حيث α = n / m
حلول كاملة خطوة بخطوة: تدرّب على هذا الموضوع في examproblems.com.