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

بأي ترتيب يزور الاجتياز القبلي (preorder) لشجرة ثنائية العقد؟

1. Aالعقدة، ثم الشجرة الفرعية اليسرى، ثم اليمنى
2. Bالشجرة الفرعية اليسرى، ثم العقدة، ثم اليمنى
3. Cمستوى بعد مستوى من الأعلى
4. Dالشجرة الفرعية اليسرى، ثم اليمنى، ثم العقدة

في قائمة مترابطة أحادية، ماذا يحتوي مؤشر التالي في العقدة الأخيرة؟

1. ANull (لا عقدة)
2. Bعنوان العقدة السابقة
3. Cعنوان العقدة الأولى
4. Dعدد العقد في القائمة

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

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

أي شرط توازن تحافظ عليه شجرة AVL عند كل عقدة؟

1. Aأن تكون كل الأوراق على العمق نفسه بالضبط
2. Bأن تُلوَّن كل عقدة بالأحمر أو الأسود
3. Cألا يختلف ارتفاعا الشجرتين الفرعيتين اليسرى واليمنى بأكثر من 1
4. Dأن تحتوي الشجرتان الفرعيتان لكل عقدة العدد نفسه تمامًا من العقد

يحتاج تطبيق إلى بحث سريع، وإلى سرد المفاتيح مرتبة والإجابة عن استعلامات المدى. أي بنية هي الأنسب؟

1. Aجدول تجزئة
2. Bشجرة بحث ثنائية متوازنة
3. Cمكدس
4. Dقائمة مترابطة غير مرتبة

في كومة ثنائية مخزّنة في مصفوفة تبدأ من الفهرس 0، أين أبو العقدة ذات الفهرس i؟

1. Aفي الفهرس ⌊i / 2⌋ + 1
2. Bفي الفهرس i − 1
3. Cفي الفهرس ⌊(i − 1) / 2⌋
4. Dفي الفهرس 2i + 1

ما بنية البيانات التي تدعم ذاكرة تخزين مؤقت LRU (least recently used) بعمليتي get وput في O(1)؟

1. Aخريطة تجزئة مع قائمة مترابطة مزدوجة
2. Bشجرة بحث ثنائية فقط
3. Cمصفوفة مرتبة واحدة
4. Dمكدس فقط

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

1. Aزمن O(1) ومساحة إضافية O(1)
2. Bزمن O(n) ومساحة إضافية O(n)
3. Cزمن O(n log n) ومساحة إضافية O(1)
4. Dزمن O(n) ومساحة إضافية O(1)