# الخوارزميات والرسوم البيانية والبرمجة الديناميكية وقواعد البيانات العلائقية

> 32 بطاقة مراجعة بمستوى جامعي عن الترتيب وخوارزميات الرسوم البيانية والبرمجة الديناميكية وSQL والفهارس والمعاملات. تفترض معرفة بأساسيات البرمجة وهياكل البيانات وSQL.

- **Canonical URL:** https://flashcards.world/flashcards/sets/1eabd21b-0c42-47c3-a04b-11f88f26cc5c/
- **Markdown URL:** https://flashcards.world/flashcards/sets/1eabd21b-0c42-47c3-a04b-11f88f26cc5c.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** ar → ar
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | ما القراءة القذرة، وما أول مستوى عزل معياري يمنعها؟ | قراءة بيانات غير مثبتة من معاملة أخرى، سواء أُلغيت تلك المعاملة لاحقًا أم لا. يمنع READ COMMITTED ومستويات العزل المعيارية الأقوى القراءات القذرة. |  |  |
| 2 | لماذا قد يستغرق الترتيب السريع Θ(n²)، وكيف تساعد العشوائية؟ | التقسيمات المتكررة شديدة الاختلال، كاختيار أصغر مفتاح من مفاتيح مختلفة كل مرة، تسبب عملًا تربيعيًا. عند اختلاف المفاتيح أو معالجة التكرارات معالجة مناسبة، تعطي المحاور العشوائية زمنًا متوقعًا O(n log n). اختيار وسيط ثلاثة عناصر أسلوب إرشادي مفيد وليس ضمانًا للحالة الأسوأ. |  |  |
| 3 | كيف تتعامل خوارزمية بيلمان–فورد مع الحواف السالبة وتكشف دورة سالبة يمكن بلوغها؟ | تُرخى جميع الحواف حتى V−1 مرة. يدل تحسّن إضافي من رأس يمكن بلوغه على دورة سالبة يمكن الوصول إليها من المصدر. الزمن الأسوأ O(VE)؛ ولا توجد كلفة منتهية لأقصر مسار إلى الرؤوس التي يمكن بلوغها من هذه الدورة. |  |  |
| 4 | ما معنى خصائص المعاملات ACID؟ | الذرية: جميع الآثار أو لا شيء. الاتساق: تحافظ المعاملات الصحيحة على القيود وثوابت التطبيق. العزل: يلتزم السلوك المتزامن بمستوى العزل المختار. الديمومة: تنجو الآثار المثبتة من الأعطال التي تشملها ضمانات قاعدة البيانات المضبوطة. |  |  |
| 5 | كيف يختلف WHERE عن HAVING في استعلام مجمّع؟ | يرشّح WHERE صفوف المدخل قبل التجميع. ويرشّح HAVING المجموعات الناتجة ويمكنه استخدام شروط تجميعية مثل COUNT(*)>1. |  |  |
| 6 | ما علاقة البرمجة الديناميكية لطول أطول تتابع جزئي مشترك (LCS)؟ | لتكن L[i,j] طول LCS لبادئتين طولاهما i,j. ضع L[0,j]=L[i,0]=0. إذا تطابق الحرفان الأخيران، فإن L[i,j]=1+L[i−1,j−1]؛ وإلا L[i,j]=max(L[i−1,j],L[i,j−1]). يستخدم الجدول الكامل O(mn) زمنًا ومساحة. |  |  |
| 7 | ما الفرق بين الفهرس العنقودي وغير العنقودي لمخزن الصفوف في SQL Server؟ | يخزن الفهرس العنقودي صفوف الجدول بترتيب المفتاح، لذا لا يملك الجدول أكثر من واحد. للفهرس غير العنقودي مفاتيحه ومحددات مواقع الصفوف، وقد يضم أعمدة أخرى. تختلف المصطلحات وتفاصيل التخزين بين أنظمة قواعد البيانات. |  |  |
| 8 | متى تصح خوارزمية ديكسترا، وما حدّ تنفيذها المعتاد بالكومة؟ | مع أوزان حواف غير سالبة، تثبّت مرارًا الرأس ذا أقل مسافة مؤقتة. يستغرق التنفيذ بقوائم تجاور وكومة دنيا ثنائية O((V+E) log V). قد تُبطل الحواف السالبة حجة أن المسافة المثبتة نهائية. |  |  |
| 9 | ما الفرق بين الحفظ التذكري والبرمجة الديناميكية من أسفل إلى أعلى؟ | يحسب الحفظ التذكري المسائل الفرعية عند الحاجة، عادة بالاستدعاء الذاتي، ويخزن النتائج. أما النهج من أسفل إلى أعلى فيحسب الحالات بترتيب تكون فيه اعتمادياتها متاحة مسبقًا، عادة بملء جدول. |  |  |
| 10 | كيف يعمل الترتيب بالإدراج، وما الذي يحدد زمنه عندما تكون البيانات شبه مرتبة؟ | يُدرج كل عنصر في بادئة مرتبة. النسخة المعتادة التي تُزيح العناصر المتجاورة أو تتبادلها تستغرق Θ(n+I)، حيث I عدد أزواج الانقلاب. تكون خطية عندما I=O(n)؛ وصغر المدخل وحده لا يغيّر حد الحالة الأسوأ Θ(n²). |  |  |
| 11 | كيف تختلف الخوارزمية الجشعة عن البرمجة الديناميكية؟ | تلتزم الجشعة باختيار محلي وتحتاج برهانًا على أن هذه الاختيارات تحافظ على الحل الأمثل. تقارن البرمجة الديناميكية البدائل بعلاقة عودية وتعيد استخدام نتائج المسائل الفرعية. يتطلب الحل الأمثل العام نموذجًا وعلاقة صحيحين، لا مجرد اسم «برمجة ديناميكية». |  |  |
| 12 | ما القراءة غير القابلة للتكرار، وأي مستوى عزل معياري يمنعها؟ | تعطي إعادة قراءة صف بيانات متغيرة، أو يختفي الصف، بعد أن تثبّت معاملة أخرى تحديثًا أو حذفًا. يمنع REPEATABLE READ وSERIALIZABLE هذه الظاهرة. |  |  |
| 13 | كيف يجد البحث بالعرض أقصر المسارات في رسم بياني غير موزون؟ | يستخدم BFS طابور FIFO ويستكشف الرؤوس بحسب المسافة بعدد الحواف. تعليم الرأس عند إدخاله الطابور يمنع تكرار زيارته. أول مسار مكتشف إلى رأس يمكن بلوغه يحوي أقل عدد من الحواف. |  |  |
| 14 | ماذا تتطلب الأشكال الطبيعية الأول والثاني والثالث؟ | 1NF: قيم سمات ذرية. 2NF: تحقق 1NF وألا تعتمد سمة غير مفتاحية على مجموعة جزئية حقيقية من سمات أي مفتاح مرشح. 3NF: تحقق 1NF، ولكل اعتماد غير تافه X→A يكون X مفتاحًا فائقًا أو تكون A ضمن مفتاح مرشح ما. السمة غير المفتاحية لا تنتمي إلى أي مفتاح مرشح. |  |  |
| 15 | ما الترتيب الطوبولوجي، وكيف تجده خوارزمية كان؟ | في رسم موجه لا دوري، تقتضي كل حافة u→v أن يسبق u الرأس v. أخرج مرارًا رأسًا درجة دخوله صفر، واحذف حوافه الخارجة، وأضف إلى الطابور الرؤوس التي أصبحت درجة دخولها صفرًا. إذا خرج أقل من V رأسًا، فالرسم الموجه يحوي دورة. |  |  |
| 16 | ما حدّا الزمن والمساحة الإضافية في أسوأ حالة لترتيب الكومة في موضعه؟ | يستغرق بناء الكومة O(n)، ثم تستغرق عمليات الاستخراج مجتمعة O(n log n). باستخدام الغربلة التكرارية إلى أسفل داخل مصفوفة المدخل، يكون الزمن الأسوأ O(n log n) والمساحة الإضافية O(1). |  |  |
| 17 | ما الذي يجعل خوارزمية ترتيب مستقرة؟ | تحافظ العناصر ذات المفاتيح المتساوية على ترتيبها النسبي الأصلي. يمكن أن يكون ترتيب الدمج مستقرًا بأخذ العنصر الأيسر أولًا عند التعادل؛ أما الترتيب السريع المعتاد داخل المصفوفة فعادة غير مستقر. يعتمد الاستقرار على التنفيذ. |  |  |
| 18 | ما الفرق بين INNER JOIN وLEFT JOIN؟ | يعيد INNER JOIN تركيبات الصفوف التي تحقق شرط الربط. يحتفظ LEFT JOIN أيضًا بكل صف أيسر بلا تطابق، ويضع NULL في أعمدة الجانب الأيمن. قد تنتج عدة صفوف يمنى مطابقة عدة صفوف ناتجة لصف أيسر واحد. |  |  |
| 19 | كيف تبني خوارزميتا كروسكال وبريم شجرة امتداد صغرى؟ | في رسم موزون متصل وغير موجه، يفحص كروسكال الحواف بترتيب وزن تصاعدي ويستخدم Union–Find لرفض الدورات. ينمّي بريم شجرة واحدة باختيار أقل حافة وزنًا تعبر من الشجرة إلى رأس خارجها كل مرة. |  |  |
| 20 | كيف يدعم WAL في PostgreSQL الديمومة عند التثبيت المتزامن المعتاد؟ | تصل سجلات اليومية ذات الصلة إلى تخزين دائم قبل تأكيد التثبيت وقبل كتابة صفحات البيانات المعدلة. بعد التعطل، يمكن لـWAL إعادة تطبيق تغييرات لم تصل إلى صفحات البيانات. قد يفقد التثبيت غير المتزامن معاملات حديثة سبق تأكيدها. |  |  |
| 21 | كيف يكتشف البحث بالعمق دورة في رسم بياني موجه؟ | يتعمق DFS باستخدام الاستدعاء الذاتي أو مكدس صريح. الحافة إلى رأس ما يزال نشطًا على مسار DFS الحالي هي حافة خلفية تثبت دورة موجهة؛ ولا تكفي حافة إلى أي رأس سبق زيارته. |  |  |
| 22 | ما علاقة العودية القياسية لحقيبة الظهر 0/1 ذات السعة الصحيحة W؟ | لتكن D[i,w] أفضل قيمة باستخدام أول i عنصرًا بسعة w، مع أوزان صحيحة موجبة wᵢ. ضع D[0,w]=0. إذا كان wᵢ>w، انسخ D[i−1,w]؛ وإلا خذ max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). الزمن O(NW) شبه متعدد الحدود. |  |  |
| 23 | كيف يعمل ترتيب المصفوفة بالدمج بصورته المعتادة، وما حدّا الزمن والمساحة؟ | يرتب نصفين استدعائيًا ثم يدمجهما في زمن خطي. تستغرق النسخة المعتادة Θ(n log n) زمنًا وO(n) مساحة إضافية، بافتراض مقارنات ثابتة الزمن. |  |  |
| 24 | لماذا تفيد أشجار B+ في فهارس قواعد البيانات واستعلامات النطاق؟ | يحافظ عدد التفرعات الكبير على قلة ارتفاع الشجرة، فيقل الوصول إلى الصفحات. تدعم المفاتيح المرتبة والأوراق المترابطة مسح النطاقات. تستهدف فهارس التجزئة البحث بالمساواة ولا توفر بطبيعتها الوصول المرتب نفسه إلى النطاقات. |  |  |
| 25 | ما مرحلتا القفل ثنائي الطور (2PL)؟ | النمو: اكتساب أقفال دون تحريرها. الانكماش: تحرير الأقفال دون اكتساب جديدة. مع أقفال قراءة وكتابة متعارضة مناسبة، يضمن 2PL جداول تنفيذ قابلة للتسلسل بحسب التعارض، لكن يظل الجمود المتبادل ممكنًا. |  |  |
| 26 | ماذا يتطلب البحث الثنائي، ومتى يعمل في زمن O(log n)؟ | يقسم مجال البحث إلى نصفين مرارًا في بيانات مرتبة وفق علاقة المقارنة. في مصفوفة تتيح الوصول بالفهرس في O(1) ومقارنات ثابتة الزمن، يستغرق البحث بين n عنصرًا زمن O(log n). |  |  |
| 27 | لماذا تفيد البرمجة الديناميكية في مسائل تحسين كثيرة؟ | تتيح البنية الجزئية المثلى التعبير عن الحل الأمثل عبر حلول مثلى لمسائل فرعية. عندما تتداخل المسائل الفرعية، يمنع تخزين إجاباتها تكرار العمل. يجب أن تمثل تعريفات الحالات وعلاقة العودية المسألة الأصلية تمثيلًا صحيحًا. |  |  |
| 28 | متى يمكن للترتيب بالعد أو بالمراتب أن يعمل في زمن خطي؟ | يكلف الترتيب بالعد O(n+k) لعدد n من المفاتيح ضمن مجال من k قيمة. ويكلف ترتيب المراتب ذو d تمريرات مستقرة على الخانات وأساس b مقدار O(d(n+b)). لا يكونان خطيين إلا إذا سمحت المعلمات بذلك؛ فهما يستفيدان من بنية المفاتيح، لا من المقارنات وحدها. |  |  |
| 29 | كيف تُقارن مصفوفة التجاور بقوائم التجاور العادية؟ | لعدد V من الرؤوس وE من الحواف، تستخدم المصفوفة O(V²) مساحة وتختبر وجود حافة في O(1). تستخدم القوائم O(V+E)؛ والبحث عن الحافة (u,v) في قائمة غير مرتبة يستغرق O(deg(u))، حيث deg(u) طول تلك القائمة. |  |  |
| 30 | ما القراءة الوهمية، وكيف تُمنع؟ | يجد تكرار استعلام بشرط مجموعة مختلفة من الصفوف المطابقة بعد تثبيت تغييرات معاملة أخرى. يمنع SERIALIZABLE الصفوف الوهمية في النموذج المعياري؛ وبعض التطبيقات، ومنها PostgreSQL REPEATABLE READ، تمنعها أيضًا في مستوى أدنى. |  |  |
| 31 | ما الترتيب المنطقي المبسط لمعالجة استعلام SQL SELECT؟ | لاستعلام بلا CTE أو دوال نافذة أو عمليات مجموعات: FROM/JOIN → WHERE → GROUP BY والتجميعات → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. هذا نموذج منطقي، وليس بالضرورة ترتيب التنفيذ الفعلي الذي يختاره المُحسِّن. |  |  |
| 32 | ما الفرق بين المفتاح الأساسي والخارجي في PostgreSQL؟ | يُعرّف المفتاح الأساسي الصفوف بقيم فريدة وغير NULL. يتطلب المفتاح الخارجي تطابقًا مع قيم المفتاح المشار إليه، مع مراعاة قواعد NULL الخاصة به. ويمكن أن يشير إلى مفتاح UNIQUE مؤهل أو مفتاح أساسي في الجدول نفسه أو غيره. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/1eabd21b-0c42-47c3-a04b-11f88f26cc5c/).
