اختبار: هياكل البيانات والخوارزميات
هل يمكنك خداع شجرة ثنائية؟
مرحبًا بك في اختبار هياكل البيانات والخوارزميات!
سيختبر هذا الاختبار معرفتك بهياكل البيانات (المكدسات، القوائم، الأشجار، إلخ)، والخوارزميات ()، وتعقيد الوقت.
20 سؤالًا… ابدأ!
ما هي بنية البيانات الأكثر ملاءمة لنمط الوصول LIFO (آخر دخول، أول خروج)؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادة ما تتبع ما يجب أن يحدث أولاً أو أخيراً.
المكدسات هي الأكثر ملاءمة لأنماط الوصول LIFO. قوائم الانتظار هي الأكثر ملاءمة لأنماط الوصول FIFO (أول دخول، أول خروج).
ما هو التعقيد الزمني لخوارزمية تستغرق دائمًا نفس الوقت للتشغيل، بغض النظر عن حجم الإدخال؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع من ما يجب أن يحدث أولاً أو أخيرًا.
يمثل O(1) التعقيد الزمني الثابت. يعني أن الخوارزمية تستغرق دائمًا نفس الوقت للتشغيل، بغض النظر عن حجم الإدخال.
ما هو التعقيد الزمني لحساب طول قائمة مرتبطة منفردة؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو آخراً.
لحساب طول قائمة مرتبطة منفردة، يجب عليك اجتياز كل عقدة من الرأس إلى الذيل، مما يؤدي إلى تعقيد زمني O(n).
ما هو متوسط التعقيد الزمني للبحث عن عنصر في شجرة بحث ثنائية متوازنة؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
في شجرة بحث ثنائية متوازنة، متوسط التعقيد الزمني للبحث هو O(log n) لأن كل مستوى يسمح بتقسيم مساحة البحث إلى النصف.
ما هو التعقيد الزمني لخوارزمية الفرز بالدمج في أسوأ الحالات؟
انظر إلى نمط الوصول، وليس اسم البنية. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
تعمل خوارزمية الفرز بالدمج دائمًا بتعقيد أسوأ حالة O(n log n) حيث تقوم بتقسيم المصفوفة إلى نصفين بشكل متكرر ودمج المصفوفات الفرعية المرتبة.
ما هي بنية البيانات المستخدمة عادةً لتنفيذ بحث العرض أولاً (BFS)؟
انظر إلى نمط الوصول، وليس اسم البنية. عادةً ما تتبع الإجابة الصحيحة من ما يجب أن يحدث أولاً أو أخيرًا.
يستخدم BFS طابورًا لاستكشاف العقد مستوىً بمستوى، ومعالجة العقد بطريقة العرض أولاً (حسب “الصف”).
أي خوارزمية تُستخدم عادةً لكشف الدورات في رسم بياني موجه؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
عادةً ما يُستخدم البحث بالعمق (DFS) لكشف الدورات في رسم بياني عن طريق الحفاظ على مكدس استدعاء لتتبع العُقد التي تم زيارتها.
ما هو التعقيد الزمني لفرز الكومة في أسوأ الحالات؟
انظر إلى نمط الوصول، وليس اسم البنية. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
يحافظ فرز الكومة على تعقيد زمني في أسوأ الحالات هو O(n log n)، حيث يقوم ببناء كومة واستخراج العنصر الأقصى بشكل متكرر.
ما هو متوسط تعقيد الوقت للوصول إلى عنصر في جدول التجزئة؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً ما تُستنتج من ما يجب أن يحدث أولاً أو أخيرًا.
جداول التجزئة لها تعقيد وقت متوسط قدره O(1) للوصول إلى العناصر، بافتراض وجود دالة تجزئة جيدة تقلل من التصادمات.
أي مجموعة تحتوي على العمليات النموذجية التي يتم إجراؤها على المكدس؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو آخراً.
العمليات الأساسية للمكدس هي Push (إضافة عنصر)، Pop (إزالة عنصر)، و Peek (عرض العنصر العلوي دون إزالته).
ما هي الخوارزمية الشائعة الاستخدام لإيجاد أقصر مسار في رسم بياني موزون بحواف غير سالبة؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
خوارزمية ديكسترا تُستخدم بشكل متكرر لإيجاد أقصر مسار في الرسوم البيانية ذات أوزان الحواف غير السالبة. تستخدم طابور أولوية لتحديد أقصر مسافة بكفاءة.
أي مجموعة تحتوي على أمثلة لهياكل بيانات أشجار البحث الثنائية ذاتية التوازن؟
انظر إلى نمط الوصول، وليس إلى اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
أشجار AVL وأشجار الأحمر-الأسود هي أنواع من الأشجار ذاتية التوازن، والتي تضمن بقاء الشجرة متوازنة بعد كل إدراج أو حذف.
ما هما العمليتان الأساسيتان للطابور؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
العمليتان الأساسيتان في الطابور هما الإدراج (إضافة عنصر إلى الخلف) والإزالة (إزالة عنصر من الأمام).
ما هي شروط إجراء الترتيب الطوبولوجي على رسم بياني؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
يمكن إجراء الترتيب الطوبولوجي على رسم بياني إذا كان موجهًا ولا دوريًا (DAG). هذا النوع من الترتيب مفيد في مشاكل جدولة المهام.
ما هو التعقيد الزمني لتطبيق تكراري ساذج لمتتالية فيبوناتشي؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
التطبيق التكراري الساذج لمتتالية فيبوناتشي له تعقيد زمني O(2^n) بسبب الحسابات المتكررة الواسعة لكل رقم فيبوناتشي.
ما هي بنية البيانات المستخدمة عادة لتنفيذ طابور الأولوية؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً ما تتبع ما يجب أن يحدث أولاً أو أخيرًا.
غالبًا ما يتم تنفيذ طابور الأولوية باستخدام الكومة لأنها تسمح باستخراج العنصر ذي الأولوية الأعلى أو الأدنى بكفاءة.
أي من المجموعات التالية تسرد ترتيبات الاجتياز بالعمق أولاً الشائعة للشجرة الثنائية؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيراً.
الترتيب الداخلي والترتيب المسبق والترتيب اللاحق هي ترتيبات الاجتياز بالعمق أولاً الثلاثة الشائعة للأشجار الثنائية، ولكل منها ترتيب مختلف لزيارة العقد. الاجتياز بالاتساع أولاً شائع أيضًا، لكنه فئة اجتياز مختلفة.
أي من الخصائص التالية صحيحة بالنسبة للكومة الصغرى؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
في الكومة الصغرى، الجذر دائمًا هو أصغر عنصر، وارتفاع الشجرة هو O(log n)، مما يجعل الإدراج والاستخراج فعالين.
هل خوارزمية ترتيب الفقاعات مستقرة؟
انظر إلى نمط الوصول، وليس اسم الهيكل. الإجابة الصحيحة عادةً تتبع ما يجب أن يحدث أولاً أو أخيرًا.
ترتيب الفقاعات هو خوارزمية ترتيب مستقرة لأنها تحافظ على الترتيب النسبي للعناصر المتساوية أثناء الترتيب.