هياكل البيانات والخوارزميات: حزمة المراجعة المكثفة

أوراق القوانين، وأهم خطوات الحل لكل موضوع، و6 مسألة تدريبية، مع الحلول الكاملة في الخلف.

مسائل جديدةالعودة إلى المقرّر

في نافذة الطباعة اختر «حفظ بصيغة PDF» لحفظ نسخة على جهازك.

1القوانين وطرق الحل

نظرية البيانات

مبرهنة المصافحة
Σ deg(v) = 2|E|
البيانات التامة
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
البيان المنتظم
|E| = n·k/2
الشجرة والغابة
|E| = n − 1, |E| = n − c
أوراق الشجرة
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
أويلر
الدارة: كل الدرجات زوجية؛ المسار: درجتان فرديتان بالضبط
دارات هاملتون في Kn
(n − 1)!/2
تحديث ديكسترا
d(v) = min(d(v), d(u) + w(u, v))
المسارات (walks) بطول L
(Mᴸ)ij

الطريقة

  1. اكتب درجة كل رأس؛ مجموع الدرجات يساوي ضعف عدد الحواف.
  2. في أسئلة أويلر، تحقّق من أن البيان متصل وعُدّ الرؤوس ذات الدرجة الفردية.
  3. للأشجار استخدم n − 1 حافة ومبرهنة المصافحة.
  4. في ديكسترا احتفظ بجدول للمسافات المؤقتة وثبّت في كل جولة أصغر رأس غير مثبّت.
  5. لإيجاد شجرة ممتدة دنيا، رتّب الحواف بحسب الوزن وتخطَّ كل حافة تُغلق دورة (كروسكال)، أو أنمِ شجرة واحدة انطلاقًا من رأس البداية (برايم).

2مسائل تدريبية

1.الخوارزميات والتعقيدمتوسطة

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

  1. Aأسّي
  2. Bخطي
  3. Cلوغاريتمي
  4. Dثابت
2.الخوارزميات والتعقيدصعبة

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

  1. AΘ(n log² n)
  2. BΘ(n)
  3. CΘ(n²)
  4. DΘ(n log n)
3.هياكل البياناتمتوسطة

ماذا يحدث حين يُعيد جدول تجزئة التجزئة (rehash) بعد تجاوز معامل تحميله حدًا معينًا؟

  1. Aتُرتَّب المفاتيح الموجودة في مكانها
  2. Bلا تُنقل إلا المفاتيح المتصادمة إلى قائمة فائض جديدة في نهاية الجدول
  3. Cيُحجز جدول أكبر ويُدرج كل مفتاح من جديد
  4. Dتُحذف أقدم المفاتيح لإفساح المجال
4.هياكل البياناتصعبة

ما الخاصية التي يجب أن تحققها الشجرة الحمراء-السوداء؟

  1. Aكل مسار من عقدة إلى أوراقها المنحدرة منها يحتوي على العدد نفسه من العقد السوداء
  2. Bيجب أن يكون لكل عقدة حمراء أبناء حمر، فتشكّل العقد الحمراء سلاسل متصلة حتى الأوراق
  3. Cيجب أن يكون الجذر أحمر
  4. Dيجب أن تكون كل عقدة حمراء
5.نظرية البياناتمتوسطة

لشجرة 2 رؤوس من الدرجة 4, 3 رؤوس من الدرجة 2، وكل رؤوسها الأخرى أوراق (درجة 1). كم ورقة L لها؟

2 × deg 43 × deg 2
L =
6.نظرية البياناتصعبة
ABCDEF

كم مسارًا مغلقًا (closed walk) بطول 2 يبدأ وينتهي عند C؟ يجوز للمسار تكرار الرؤوس والحواف. سمِّ العدد N.

M = مصفوفة التجاورL = 2
N =

3المحاليل

1.الخوارزميات والتعقيد

الإجابة: A · أسّي

لماذا هذه هي الإجابة

تنمو شجرة الاستدعاءات تقريبًا مثل φⁿ (نحو 1,618ⁿ). ويخفّض التذكير (memoisation) التعقيد إلى O(n).

الإجابة

A · أسّي
2.الخوارزميات والتعقيد

الإجابة: A · Θ(n log² n)

لماذا هذه هي الإجابة

يُجري المستوى k نحو n log(n / 2ᵏ) عملًا، والجمع على log n مستوى يعطي Θ(n log² n)، وهي الحالة الثانية الموسعة من النظرية الرئيسية.

الإجابة

A · Θ(n log² n)
3.هياكل البيانات

الإجابة: C · يُحجز جدول أكبر ويُدرج كل مفتاح من جديد

لماذا هذه هي الإجابة

لأن الفهرس يُحسب بباقي القسمة على حجم الجدول، يجب إعادة تجزئة كل المفاتيح في الجدول الجديد الأكبر، ومع المضاعفة تبقى الكلفة المستهلَكة O(1).

الإجابة

C · يُحجز جدول أكبر ويُدرج كل مفتاح من جديد
4.هياكل البيانات

الإجابة: A · كل مسار من عقدة إلى أوراقها المنحدرة منها يحتوي على العدد نفسه من العقد السوداء

لماذا هذه هي الإجابة

قواعد الشجرة الحمراء-السوداء: العقد حمراء أو سوداء، والجذر أسود، وأبناء العقد الحمراء سود، ولجميع المسارات الارتفاع الأسود نفسه، مما يبقي الارتفاع ≤ 2 log₂(n + 1).

الإجابة

A · كل مسار من عقدة إلى أوراقها المنحدرة منها يحتوي على العدد نفسه من العقد السوداء
5.نظرية البيانات

الإجابة: L = 6

أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.

مبرهنة المصافحة لشجرة

L + 14 = 2(L + 5) − 2
L = 6

الإجابة

L = 6

اختصار: L = 2 + Σ (d − 2) على الرؤوس ذات الدرجة d ≥ 3.

6.نظرية البيانات

الإجابة: N = 2

الدرجات: درجة الرأس هي عدد الحواف التي تلتقي عنده. لكل حافة طرفان، فتساوي الدرجات مجتمعةً ضعف عدد الحواف: Σ deg(v) = 2|E| (مبرهنة المصافحة). وعدد الرؤوس ذات الدرجة الفردية زوجي إذن. للبيان Kn عدد n(n − 1)/2 حافة، وللبيان k-المنتظم على n رأسًا nk/2، وللشجرة على n رأسًا n − 1 حافة.

مصفوفة التجاور

A: 0 1 1 0 0 0
B: 1 0 0 1 1 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 0
F: 0 0 0 1 0 0

الجيران المشتركون

(M²)CC = 1·1 + 0·0 + 0·0 + 0·0 + 1·1 + 0·0 = 2

الإجابة

N = 2

ExamProblems · examproblems.com/courses/data-structures-and-algorithms