أسئلة تدريبية مجانية متعددة الخيارات في هياكل البيانات مع تلميحات وشروح، بثلاثة مستويات: المصطلحات والحقائق الأساسية, تطبيق المفاهيم, الحالات والتحليل.
بنية البيانات طريقة لتنظيم البيانات في الذاكرة بحيث تكون بعض العمليات سريعة: إيجاد عنصر أو إضافة عنصر أو حذفه.
لا توجد بنية سريعة في كل شيء. واختيار بنية يعني اختيار العمليات التي ينبغي أن تكون رخيصة. وتُكتب تكاليفها بـ O الكبيرة، حيث n عدد العناصر.
اللبنتان الأساسيتان هما المصفوفة والقائمة المترابطة.
تخزّن المصفوفة عناصرها في كتلة واحدة من الذاكرة، الواحد تلو الآخر. ويستطيع الحاسوب حساب موضع العنصر i، لذا فقراءة a[i] تستغرق O(1). أما الإدراج في المقدمة فيعني إزاحة كل عنصر: O(n).
تخزّن القائمة المترابطة كل عنصر في عقدة بمؤشر إلى العقدة التالية. والمؤشر الأخير null. الإدراج عند الرأس (h) لا يغيّر إلا مؤشرًا واحدًا: O(1). لكن للوصول إلى العنصر i عليك اتباع i مؤشرًا: O(n).
القائمة المترابطة المزدوجة لها أيضًا مؤشر إلى العقدة السابقة، فيمكنك السير في الاتجاهين.
تحقّق ذاتي أي عملية هي O(1) للمصفوفة لكنها O(n) للقائمة المترابطة البسيطة؟
إدراج عنصر جديد في المقدمة
زيارة كل عنصر مرة واحدة
عدّ العناصر واحدًا واحدًا
قراءة العنصر عند الفهرس i
الإجابة: قراءة العنصر عند الفهرس i. تحسب المصفوفة عنوان العنصر i مباشرةً. أما القائمة المترابطة فعليها اتباع i مؤشرًا من الرأس. والإدراج في المقدمة هو الحالة العكسية: رخيص للقائمة، مكلف للمصفوفة.
2المكدّسات والطوابير
المكدّس (stack) كرُزمة أطباق: تضيف وتزيل من الأعلى فقط. وآخر عنصر دخل هو أول عنصر يخرج: LIFO.
push يضع عنصرًا في الأعلى، وpop يزيل العنصر العلوي، وpeek يقرأ العلوي دون إزالته. وكلها O(1).
الاستخدامات: وظيفة التراجع في المحرر، ومكدّس الاستدعاءات في برنامج، والتحقق من توازن الأقواس، والبحث بالعمق أولًا.
الطابور (queue) كصف عند الصندوق: تنضم من الخلف وتغادر من الأمام. وأول عنصر دخل هو أول عنصر يخرج: FIFO.
enqueue يضيف من الخلف، وdequeue يزيل من الأمام. وكلاهما O(1).
deque (الطابور ثنائي الطرف) يسمح بالإضافة والإزالة من الطرفين. وطابور الأولوية يزيل دائمًا العنصر الأعلى أولوية أولًا؛ وعادةً يُبنى على شكل كومة.
تحقّق ذاتي أي بنية بيانات تناسب زر «التراجع» في محرر النصوص أفضل مناسبة؟
بيان
جدول تجزئة
طابور
مكدّس
الإجابة: مكدّس. يجب أن يتراجع التراجع عن أحدث إجراء أولًا: آخر داخل أول خارج. أما الطابور فكان سيتراجع عن أقدم إجراء أولًا.
3الأشجار والأكوام وجداول التجزئة والبيانات
الشجرة لها عقدة عليا واحدة هي الجذر. ولكل عقدة أخرى أب واحد بالضبط. والعقد التي لا أبناء لها هي أوراق. وللشجرة ذات n عقدة n − 1 حافة.
في الشجرة الثنائية لكل عقدة ابنان على الأكثر. وتضيف شجرة البحث الثنائية (BST) قاعدة: المفاتيح في الشجرة الفرعية اليسرى أصغر من العقدة، والمفاتيح في الشجرة الفرعية اليمنى أكبر.
يتبع البحث في BST مسارًا واحدًا نزولًا، فتكلفته O(الارتفاع). والشجرة المتوازنة (AVL، الأحمر والأسود) تُبقي الارتفاع قريبًا من log₂ n. أما إدراج المفاتيح مرتّبة فيصنع سلسلة ارتفاعها n.
الكومة (heap) شجرة ثنائية يكون فيها كل أب أصغر من أبنائه (كومة صغرى) أو أكبر (كومة كبرى). والقيمة الصغرى أو الكبرى عند الجذر، وتكلفة الإدراج والإزالة O(log n).
يخزّن جدول التجزئة أزواج مفتاح–قيمة. وتحوّل دالة التجزئة المفتاح إلى فهرس، فيستغرق الإدراج والبحث O(1) في المتوسط. ومفتاحان لهما الفهرس نفسه يمثلان تصادمًا، يُحل بالتسلسل (قائمة لكل خانة) أو بالعنونة المفتوحة (تجربة خانة أخرى).
للبيان رؤوس تصل بينها حواف، وقد يكون لها اتجاه أو وزن. ويُخزَّن كمصفوفة مجاورة، بذاكرة O(V²)، أو كقوائم مجاورة، O(V + E).
تحقّق ذاتي تُدرج المفاتيح 50 و30 و70 و20 و40 بهذا الترتيب في شجرة بحث ثنائية فارغة. ما الابن الأيسر للعقدة 30؟
20
40
70
ليس لها ابن أيسر
الإجابة: 20. العدد 20 أصغر من 50 فيذهب يسارًا إلى 30. وهو أصغر أيضًا من 30 فيذهب يسارًا مرة أخرى. أما 40 فأكبر من 30 ويصبح ابنها الأيمن.
4الطريقة خطوة بخطوة
كثيرًا ما تصف الأسئلة مهمة وتسأل أي بنية تناسبها، أو تسأل كيف تبدو البنية بعد بعض العمليات.
ابحث عن العملية التي يجب أن تكون سريعة: الوصول بالموضع، أو بالمفتاح، أو أحدث عنصر، أو أقدم عنصر، أو أصغر عنصر، أو مدى.
طابقها مع بنية: فهرس ← مصفوفة، مفتاح ← جدول تجزئة، الأحدث ← مكدّس، الأقدم ← طابور، الأصغر أو الأكبر ← كومة، الترتيب أو المدى ← شجرة بحث متوازنة.
افحص تكلفة العمليات الأخرى التي تحتاجها المهمة، بـ O الكبيرة.
في سؤال التتبّع، نفّذ العمليات واحدة واحدة واكتب الحالة بعد كل منها.
تحقّق من الحالة النهائية بقاعدة البنية: LIFO أو FIFO أو ترتيب BST أو ترتيب الكومة.
5مثال محلول
تابع كل خطوة. حاول أن تتوقّع الخطوة التالية قبل أن تفتحها.
مثال محلول
تُدرج المفاتيح 50 و30 و70 و20 و40 و60 بهذا الترتيب في شجرة بحث ثنائية فارغة. ما الاجتياز بالترتيب الداخلي (in-order)، وكم مقارنة يحتاج البحث عن 60؟
1
أدرج الجذر
المفتاح الأول، 50، يصبح الجذر.
2
أدرج 30 و70
30 أصغر من 50 فيذهب إلى اليسار. و70 أكبر من 50 فيذهب إلى اليمين.
3
أدرج 20 و40 و60
20: أصغر من 50، وأصغر من 30، فيكون يسار 30. 40: أصغر من 50، وأكبر من 30، فيكون يمين 30. 60: أكبر من 50، وأصغر من 70، فيكون يسار 70.
4
اجتز بالترتيب الداخلي
يزور الاجتياز بالترتيب الداخلي الشجرة الفرعية اليسرى، ثم العقدة، ثم الشجرة الفرعية اليمنى.
وهذا يعطي 20 و30 و40 و50 و60 و70: المفاتيح مرتبة، كما هي الحال دائمًا في BST.
5
ابحث عن 60
قارن مع 50: أكبر، اذهب يمينًا. قارن مع 70: أصغر، اذهب يسارًا. قارن مع 60: وُجد.
يحتاج البحث إلى 3 مقارنات، واحدة لكل مستوى.
الإجابة
الاجتياز بالترتيب الداخلي: 20, 30, 40, 50, 60, 70. ويحتاج البحث عن 60 إلى 3 مقارنات.
6أخطاء شائعة
الخلط بين LIFO وFIFO. المكدّس يُرجع أحدث عنصر، والطابور أقدم عنصر.
الظن أن القائمة المترابطة تتيح وصولًا سريعًا بالفهرس. عليها أن تسير من الرأس.
افتراض أن BST دائمًا O(log n). الشجرة المتوازنة فقط كذلك؛ أما الإدراج المرتّب فيعطي O(n).
نسيان التصادمات في جدول التجزئة. O(1) هي المتوسط، لا أسوأ حالة.
الخلط بين طرق الاجتياز. القبلي (preorder): العقدة أولًا. الداخلي (in-order): العقدة في المنتصف. البعدي (postorder): العقدة أخيرًا.
استخدام مصفوفة مجاورة لبيان كبير متناثر. إنها تهدر ذاكرة O(V²).
تحقّق ذاتي تُضيف 1 ثم 2 ثم 3 إلى طابور فارغ بهذا الترتيب. أي عنصر يُرجعه أول dequeue؟
1 و2 و3 معًا
1
2
3
الإجابة: 1. الطابور أول داخل أول خارج، فيغادر 1 أولًا. أما 3 فهو الجواب للمكدّس (pop) الذي يُرجع أحدث عنصر.
7كيف تبدو أسئلة الامتحان
سهل: المصطلحات والحقائق. LIFO وFIFO، وما هي العقدة والجذر والورقة، وقاعدة BST، وما تفعله دالة التجزئة.
متوسط: تطبيق المفاهيم. أي بنية تناسب مهمة، ونتيجة push وpop أو إدراجات BST، واجتياز الأشجار، وجدول تجزئة بالفحص الخطي، والتكاليف بـ O الكبيرة.
صعب: الحالات والتحليل. الأشجار المتوازنة، والأكوام في المصفوفات، وأشجار B، وأشجار trie، وunion-find، ومرشحات Bloom، وتصاميم مثل ذاكرة LRU المؤقتة.
في كومة مخزّنة في مصفوفة تبدأ من الفهرس 0، يقع ابنا الفهرس i عند 2i + 1 و2i + 2، ويقع أبوه عند ⌊(i − 1) / 2⌋.