علوم الحاسوب

1. 1.

   تتبّع بحثاً خطياً عن 7 في [4, 9, 7, 2] من اليسار إلى اليمين مع التوقف عند أول تطابق. حدّد الفهرس الصفري وعدد المقارنات.

   [3 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

   1. ابدأ بالفهرس صفر وتقدم بعد عدم التطابق فقط. يوقف التطابق في العنصر الثالث البحث فلا يقارن العنصر الأخير.

   نقاط التصحيح

   • القيم المقارنة 4 و9 و7.
   • الفهرس المعاد = 2.
   • توجد 3 مقارنات مساواة.

   ملاحظة الفاحص: ميّز الموضع الثالث عن الفهرس الصفري اثنين.

2. 2.

   اشرح الشرط المسبق للبحث الثنائي ولماذا قد يفوت قيمة موجودة عند تطبيقه مباشرة على [8, 2, 9, 1].

   [3 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

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

   نقاط التصحيح

   • يجب أن يكون التسلسل مرتباً بما يتفق مع المقارنة.
   • تلغي كل مقارنة نصفاً بناءً على الترتيب.
   • في تسلسل غير مرتب قد يحتوي النصف المستبعد الهدف.

   ملاحظة الفاحص: يساعد الوصول العشوائي سرعة التنفيذ ولا يحل محل شرط الترتيب.

3. 3.

   ابحث ثنائياً عن 23 في [3, 7, 11, 15, 19, 23, 27] بحدود شاملة وmid = floor((low+high)/2) وفهرسة صفرية. سجّل فهارس الوسط حتى العثور عليه.

   [3 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

   1. بداية low=0 وhigh=6. بما أن 15 صغير جداً استبعد الفهارس حتى ثلاثة؛ ووسط أربعة إلى ستة هو خمسة ويطابق مباشرة.

   نقاط التصحيح

   • الوسط الأول = 3 وقيمته 15.
   • ثم low = 4 والوسط = 5 وقيمته 23.
   • يُعثر عليه عند الفهرس 5 بعد مقارنتين للوسط.

   ملاحظة الفاحص: قد يمنع تحديث low إلى mid بدلاً من mid+1 تقدم البحث.

4. 4.

   نفّذ فرز الإدراج على [5, 2, 4, 1] بإدراج كل عنصر تالٍ في البادئة المرتبة. أعطِ المصفوفة بعد كل دورة خارجية.

   [3 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

   1. احفظ العنصر التالي وازح عناصر البادئة الأكبر يميناً ثم ضعه في الفجوة. تزيد كل دورة البادئة المرتبة عنصراً وتحفظ اللاحقة غير المعالجة.

   نقاط التصحيح

   • بعد إدراج 2: [2, 5, 4, 1].
   • بعد إدراج 4: [2, 4, 5, 1].
   • بعد إدراج 1: [1, 2, 4, 5].

   ملاحظة الفاحص: اعرض حالات الدورات الخارجية لا القائمة النهائية فقط.

5. 5.

   تنفّذ خوارزمية FOR i=1 TO n وداخلها FOR j=1 TO i مع عملية في كل دورة داخلية. اشتق عدد العمليات والتعقيد الزمني وقيّم هل تضاعف n يضاعف العدد أربع مرات بالضبط.

   [4 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

   1. يعتمد الحد الداخلي على i فمجال الدورات مثلث لا مربع n في n. قارن كثير الحدود الدقيق عند n و2n قبل تقريب الحد المسيطر عند n كبير.

   نقاط التصحيح

   • العدد = 1 + 2 + ... + n.
   • العدد = n(n+1)/2.
   • الزمن Theta(n^2).
   • النسبة 2(2n+1)/(n+1)، تقترب من 4 ولا تساويها تماماً لـn موجب محدود.

   ملاحظة الفاحص: التناسب التقاربي ليس مساواة دقيقة للمدخلات المحدودة.

6. 6.

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

   [4 درجة] · بدون آلة حاسبة

   شرح الإجابة

   الشروح الإرشادية مبنية على نقاط التصحيح وليست اشتقاقات متحققاً منها بصورة مستقلة.

   1. يحدد الثابت معنى القيمة المخزنة بعد كل عنصر معالج. يثبته البدء بعضو فعلي وتحفظه مقارنة عضو جديد، ويثبت استنفاد المصفوفة الشرط اللاحق.

   نقاط التصحيح

   • هيّئ largest بالعنصر الأول؛ فهو أكبر قيمة في بادئة العنصر الواحد.
   • لكل قيمة تالية استبدل largest فقط إن كانت أكبر، لتحفظ ثابت أكبر قيمة للبادئة.
   • عند الإنهاء تصبح البادئة المصفوفة كلها، فتكون largest أكبر قيمة كلية.
   • تفشل التهيئة بالصفر لمصفوفة سالبة كلها لأن الصفر قد لا يكون عنصراً.

   ملاحظة الفاحص: يحتاج برهان الصحة شرط عدم الفراغ إضافة إلى وصف الحلقة.

أسئلة تدريبية أصلية غير رسمية من SubjectScout، وليست أسئلة أوراق سابقة رسمية.