هياكل البيانات وتحليل التعقيد الحسابي (Big-O) والخوارزميات الأساسية
مراجعة بمستوى البكالوريوس تتطلب أساسيات البرمجة: 32 بطاقة عن المصفوفات والقوائم والتجزئة والأشجار والأكوام وأشجار البادئات وUnion–Find ومرشحات بلوم والتعقيد.
- Category
- Computer Science
- Level
- basic
- Languages
- ar → ar
- Cards
- 32
- Markdown
- هياكل البيانات وتحليل التعقيد الحسابي (Big-O) والخوارزميات الأساسية (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | عند مضاعفة السعة، ما التكلفة المستهلكة للإضافة إلى نهاية مصفوفة ديناميكية؟ | O(1) لكل إضافة. قد يكلف تغيير الحجم O(n)، لكن n إضافات بدءًا من مصفوفة فارغة تكلف O(n) إجمالًا. | ||
| 2 | كيف يعالج الربط المنفصل تصادمات التجزئة؟ | تحتوي كل حاوية على مجموعة إدخالات لها فهرس الحاوية نفسه، غالبًا في قائمة مترابطة. تبقى المفاتيح المختلفة في الحاوية إدخالات منفصلة. | ||
| 3 | كيف يتجنب الطابور في مصفوفة دائرية الإزاحة بعد إزالة عنصر؟ | يلتف فهرسا البداية والنهاية باستخدام باقي القسمة على السعة. تُقدّم الإزالة فهرس البداية، فتُعاد الاستفادة من الخانات الحرة دون نقل بقية العناصر. | ||
| 4 | ما ثابت الترتيب الذي يعرّف شجرة بحث ثنائية (BST) بمفاتيح متميزة؟ | عند كل عقدة، جميع مفاتيح الشجرة الفرعية اليسرى أصغر، وجميع مفاتيح اليمنى أكبر. تنطبق القاعدة بصورة تكرارية على الأشجار الفرعية. | ||
| 5 | ما الإجابات التي يعطيها مرشح بلوم يسمح بالإضافات فقط؟ | النتيجة السلبية تعني أن العنصر لم يُضف؛ والإيجابية تعني أنه ربما أُضيف. تضبط قيم التجزئة بتات في مصفوفة؛ فالنتائج الإيجابية الكاذبة ممكنة، أما السلبية الكاذبة فلا تحدث إذا ظلت الحالة سليمة. | ||
| 6 | ما قاعدة الوصول في الطابور والتكاليف المعتادة لعملياته؟ | FIFO: إضافة من الخلف وإزالة من الأمام. كلاهما O(1) بروابط للرأس والذيل أو بمخزن دائري ثابت السعة؛ أما إزاحة المصفوفة فتجعل الإزالة O(n). | ||
| 7 | ماذا تعني f(n) ∈ O(g(n)) لدالتين غير سالبتين f وg؟ | توجد ثوابت c > 0 وn₀ ≥ 0 بحيث f(n) ≤ c·g(n) لكل n ≥ n₀. | ||
| 8 | ماذا تفعل find وunion في بنية المجموعات المتباينة؟ | تُرجع find(x) ممثل مجموعة x. وتدمج union(x,y) مجموعتيهما إن اختلفتا؛ وإن كانتا المجموعة نفسها فلا يتغير التقسيم. | ||
| 9 | ما الفرق بين الاستكشاف الخطي والتربيعي في العنونة المفتوحة؟ | تبقى الإدخالات داخل المصفوفة. لحجم m وفهرس أولي h، تُجرَّب (h+i) mod m أو (h+c₁i+c₂i²) mod m، على الترتيب. يحتاج الاستكشاف التربيعي إلى معاملات مناسبة. | ||
| 10 | ما شجرة البادئات (trie)، ومتى يكلف البحث عن مفتاح من L محارف O(L)؟ | تخزن المفاتيح على مسارات من المحارف، مع علامات للمفاتيح المكتملة. يكون البحث O(L) إذا كان كل انتقال للمحرف التالي O(1). | ||
| 11 | ما شرط توازن AVL؟ | عند كل عقدة، ارتفاع(اليسار) − ارتفاع(اليمين) ∈ {−1, 0, 1}. وتحقق الشجرة أيضًا ثابت ترتيب BST. | ||
| 12 | ما التكلفة المتوقعة وتكلفة أسوأ حالة لجدول تجزئة بالربط المنفصل؟ | مع تحميل محدود وتجزئة جيدة التوزيع وعمليات مفاتيح ثابتة التكلفة، يكون البحث والحذف O(1) متوقعًا. والإضافة مع نمو هندسي O(1) متوقعة مستهلكة. سلسلة من n مفاتيح متصادمة قد تجعل العملية O(n). | ||
| 13 | ما عامل تحميل جدول التجزئة، ولماذا قد يتغير حجمه؟ | α = n/m: عدد الإدخالات n وعدد الحاويات أو الخانات m. تجاوز عتبة التنفيذ قد يؤدي إلى تكبير الجدول وإعادة التجزئة؛ و0.75 ليست عتبة عامة. | ||
| 14 | ما تكاليف الإضافة وإزالة الجذر وقراءة الجذر في كومة ثنائية؟ | O(log n) وO(log n) وO(1)، على الترتيب، إذا لم يلزم تغيير حجم المصفوفة. وقد يكلف تغيير الحجم O(n). | ||
| 15 | كيف يزور الاجتياز حسب المستويات شجرة ثنائية؟ | يستخدم طابور FIFO لزيارة مستوى عمق واحد في كل مرة. إضافة الابن الأيسر قبل الأيمن إلى الطابور تعطي ترتيبًا من اليسار إلى اليمين. | ||
| 16 | كيف يعمل المكدس، ومتى تكون عملياته O(1)؟ | LIFO: آخر عنصر يدخل هو أول عنصر يخرج. عند رأس قائمة مترابطة، تستغرق الإضافة والإزالة وقراءة القمة O(1)؛ وقد يجعل تغيير حجم المصفوفة إضافة واحدة O(n). | ||
| 17 | ما ترتيب الزيارة في الاجتياز السابق والوسطي واللاحق لشجرة ثنائية؟ | السابق: العقدة → اليسار → اليمين. الوسطي: اليسار → العقدة → اليمين. اللاحق: اليسار → اليمين → العقدة. | ||
| 18 | قارن الإضافة في البداية والوصول بالفهرس في قائمة أحادية الربط ومصفوفة ديناميكية. | القائمة: إضافة في البداية O(1)، ووصول بالفهرس O(n). المصفوفة: إضافة في البداية O(n)، ووصول بالفهرس O(1)؛ فالإضافة في البداية تزيح العناصر. | ||
| 19 | ما الفرق بين ضغط المسارات والدمج بالرتبة والدمج بالحجم؟ | يعيد الضغط توجيه العقد المزارة إلى الجذر. بالرتبة يُربط الجذر الأقل رتبة تحت الأعلى؛ وبالحجم تُربط المجموعة الأصغر تحت الأكبر. لا يلزم أن تساوي الرتبة الارتفاع الحالي. | ||
| 20 | ما التكلفة المستهلكة لـunion/find مع ضغط المسارات والدمج بالرتبة؟ | O(α(n)) لكل عملية، حيث α معكوس دالة أكرمان وn عدد العناصر. التهيئة O(n)؛ ويخص الحد سلسلة عمليات، لا تكلفة ثابتة في أسوأ حالة لكل استدعاء. | ||
| 21 | كيف يُصلح اختلال يسار-يمين بعد إضافة إلى AVL؟ | يُدار الابن الأيسر أولًا إلى اليسار، ثم تُدار العقدة غير المتوازنة إلى اليمين. | ||
| 22 | رتّب معدلات النمو من الأبطأ إلى الأسرع عندما n → ∞: n!، n، 1، n²، log n، 2ⁿ، n log n. | تقاربيًا: 1 < log n < n < n log n < n² < 2ⁿ < n!. | ||
| 23 | كيف تعتمد عمليات البحث والإضافة والحذف في BST على الارتفاع h؟ | تستغرق O(h). في الشجرة المتوازنة h = O(log n)، وفي السلسلة h = O(n). يتطلب O(log n) المتوقع افتراضات مثل ترتيب إضافة عشوائي. | ||
| 24 | ما تكلفة بناء كومة من أسفل إلى أعلى من n عنصرًا؟ | O(n). معظم العقد قريبة من الأوراق وتحتاج إلى إنزال قليل؛ وجمع العمل بحسب ارتفاع العقد يعطي مجموعًا خطيًا. | ||
| 25 | لماذا يستغرق الوصول بالفهرس في مصفوفة ثابتة الحجم O(1)؟ | الخانات المتساوية الحجم متجاورة: عنوان(i) = الأساس + i·حجم_الخانة. ويُفترض أن حساب العنوان يستغرق زمنًا ثابتًا. | ||
| 26 | ما الخاصيتان اللتان تعرّفان كومة ثنائية صغرى؟ | هي شجرة ثنائية مكتملة، ومفتاح كل أب لا يزيد على مفاتيح أبنائه. لذلك يحتوي الجذر على قيمة صغرى. | ||
| 27 | ما خصائص دالة التجزئة المناسبة للبحث في جدول؟ | يجب أن تكون حتمية وتوزع المفاتيح المتوقعة جيدًا. قد تكون تجزئة مفتاح ثابت الحجم O(1)؛ أما تجزئة سلسلة جديدة من L محارف فعادةً O(L). | ||
| 28 | لماذا تستطيع قائمة مزدوجة الربط حذف عقدة معطاة في O(1)؟ | يتيح رابطا السابق والتالي إعادة وصل الجارين مباشرة. تُحدَّث البداية والنهاية عند الحاجة؛ ولا يلزم البحث عن العقدة السابقة. | ||
| 29 | ما قواعد الألوان التي تحافظ على توازن BST حمراء-سوداء؟ | العقد حمراء أو سوداء؛ والجذر وأوراق NIL سوداء. ليس للعقدة الحمراء أبناء حمر. كل مسار من عقدة إلى ورقة NIL من نسلها يضم العدد نفسه من العقد السوداء. تحد هذه القواعد الارتفاع بـO(log n). | ||
| 30 | ماذا ينتج الاجتياز الوسطي لشجرة BST بمفاتيح متميزة؟ | جميع المفاتيح بترتيب تصاعدي صارم، مع زيارة n عقدة في O(n). | ||
| 31 | أين يقع أب العقدة i وأبناؤها في مصفوفة كومة طولها n وفهرستها تبدأ من الصفر؟ | الأب: ⌊(i−1)/2⌋ عندما i>0. الابنان: 2i+1 و2i+2، فقط إن كان الفهرسان أقل من n. الفهرس 0 ليس له أب. | ||
| 32 | ما الفرق بين O وΩ وΘ؟ | تمثل حدودًا تقاربية علوية وسفلية ومحكمة، على الترتيب. تصف دالة تكلفة محددة؛ ولا تعني O بحد ذاتها أسوأ حالة. |