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

ما الورقة في الشجرة؟

1. Aعقدة ليس لها أبناء
2. Bالعقدة ذات القيمة الأكبر
3. Cعقدة ليس لها أب
4. Dعقدة لها ابن واحد بالضبط

ما خاصية الكومة العظمى (max-heap)؟

1. Aمفتاح كل أب أكبر من مفاتيح أبنائه أو يساويها
2. Bمفتاح كل ابن أيسر أكبر من مفتاح شقيقه الأيمن أو يساويه
3. Cكل الأوراق تحتوي المفتاح الأكبر
4. Dالمفاتيح مرتبة من اليسار إلى اليمين

ماذا تفعل عملية peek (أو top) على المكدس؟

1. Aتُرجع العنصر السفلي من المكدس
2. Bتُرجع العنصر العلوي دون إزالته
3. Cتزيل العنصر العلوي وتُرجعه
4. Dتزيل كل العناصر من المكدس

في جدول تجزئة يستخدم العنونة المفتوحة، ما أقصى معامل تحميل ممكن؟

1. A1
2. Bلا يوجد حد أقصى
3. C2
4. D0,5

لماذا يمكن تخزين كومة ثنائية في مصفوفة دون أي مؤشرات؟

1. Aلأن كل المفاتيح في الكومة متساوية
2. Bلأن الأكوام لا تحتوي أبدًا أكثر من 100 عنصر
3. Cلأنها شجرة ثنائية تامة، فتتبع المواضع صيغ فهارس بسيطة
4. Dلأن المصفوفات تُبقي المفاتيح مرتبة تلقائيًا فلا حاجة إلى مؤشرات

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D5 4 3 2 1

بافتراض التجزئة المنتظمة البسيطة، ما الزمن المتوقع للبحث في جدول تجزئة بالتسلسل فيه n مفتاحًا وm دلوًا؟

1. AO(log n)
2. BO(1 + α)، حيث α = n / m
3. CO(n)
4. DO(m)

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

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