Examen : Structures de données et complexité algorithmique – ASD3 – Algorithmique et structure de données (ASD3)

هذا الملف يمثل امتحان مادة الخوارزميات وهياكل البيانات (ASD3) الموجه لطلبة السنة الثانية ليسانس أكاديمية في الإعلام الآلي بجامعة سطيف 1. يتكون الامتحان من أربعة تمارين تغطي أهم المفاهيم العملية والنظرية في هياكل البيانات وتحليل الخوارزميات.

يتناول التمرين الأول مقارنة تعقيد العمليات الأساسية على هياكل بيانات مختلفة مثل المصفوفات المرتبة، القوائم المرتبطة، القوائم المرتبة، وأكوام الحد الأدنى والحد الأقصى، مع التركيز على عمليات الإدراج والبحث وإيجاد القيم القصوى والدنيا. يهدف هذا الجزء إلى اختبار قدرة الطالب على ربط اختيار البنية بتكلفة التنفيذ الزمنية.

يركز التمرين الثاني على أسئلة اختيار من متعدد حول مفاهيم الاستقرار في الفرز، البحث بزمن ثابت، تقييم تعابير postfix، خصائص الـ Max Heap، تعقيد البحث الخطي، القوائم الدائرية، الأشجار الثنائية، واستعمال المكدسات والطوابير.

يعالج التمرين الثالث حذف العناصر المكررة من قائمة مرتبطة مرتبة باستعمال دالة removeDuplicates، مع طلب كتابة الخوارزمية، البرنامج بلغة C/C++، تحليل التعقيد الزمني، وتقديم حل عودي. يختبر هذا الجزء فهم الطالب لمعالجة العقد والروابط في القوائم المرتبطة.

أما التمرين الرابع فيتناول إيجاد القيمة القصوى داخل مكدس باستعمال مكدس واحد فقط وبزمن O(1)، مع ضرورة تقديم فكرة الحل وخطوات تطبيقها على مثال.

يمثل الامتحان مراجعة شاملة لمفاهيم ASD3، حيث يجمع بين التحليل النظري والتطبيق البرمجي، ويساعد الطالب على التحضير للمواضيع المتعلقة بالتعقيد، القوائم، المكدسات، والأكوام.