هياكل البيانات وتحليل التعقيد الحسابي (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)ExampleMultiple-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 بحد ذاتها أسوأ حالة.