علوم الحاسوب

1. 1.

   يتلقى مكدس فارغ PUSH(A) وPUSH(B) وPOP() وPUSH(C) وPOP(). حدّد القيم المعادة بالترتيب والمكدس المتبقي.

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

   شرح الإجابة

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

   1. يزيل المكدس أحدث عنصر مضاف لم يُزل. تكشف إزالة B العنصر A ثم تترك إضافة C وإزالته A الأصلي دون تغيير.

   نقاط التصحيح

   • يعيد POP الأول B.
   • يعيد POP الثاني C.
   • يبقى A فقط.

   ملاحظة الفاحص: لا تطبق سلوك أول داخل أول خارج على مكدس.

2. 2.

   اشرح مناسبة الطابور لخدمة مهام الطباعة بترتيب الوصول وحدّد طرفي الإدخال والإزالة.

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

   شرح الإجابة

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

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

   نقاط التصحيح

   • يوفر ترتيب أول داخل أول خارج.
   • تُدرج المهام الجديدة في الخلف.
   • تُزال أقدم مهمة منتظرة من الأمام.

   ملاحظة الفاحص: لا يضمن FIFO وحده زمناً أقصى للانتظار.

3. 3.

   أدخل المفاتيح 10 و17 و24 في جدول تجزئة فارغ حجمه 7 باستخدام h(k)=k mod 7 والسبر الخطي وخانات صفرية. حدّد خاناتها النهائية.

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

   شرح الإجابة

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

   1. لباقي القسمة لكل المفاتيح قيمة ثلاثة. يتقدم السبر الخطي للخانة التالية حتى يجد فارغة، فتكوّن التصادمات عنقوداً دون استبدال المفاتيح السابقة.

   نقاط التصحيح

   • يشغل 10 الخانة 3.
   • يتصادم 17 في 3 ويشغل الخانة 4.
   • يسبر 24 الخانتين 3 و4 ثم يشغل 5.

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

4. 4.

   لرسم غير موجه حوافه A-B وA-C وB-D وC-D، نفّذ BFS من A مع إدراج الجيران غير المزورين أبجدياً ووسمهم عند الإدراج. أعطِ ترتيب الزيارة وعدد حواف أقصر مسار من A إلى D.

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

   شرح الإجابة

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

   1. يعالج طابور BFS جميع الرؤوس عند مسافة واحدة قبل التالية. يضع البدء بـA كلاً من B وC عند مسافة واحدة ثم يكتشف D عند مسافة اثنتين.

   نقاط التصحيح

   • ترتيب الزيارة A ثم B ثم C ثم D.
   • تُدرج D من B ولا تُدرج ثانية من C.
   • أقصر عدد حواف 2.

   ملاحظة الفاحص: يمنع الوسم عند الإدراج تكرار مدخلات الطابور عبر آباء مختلفين.

5. 5.

   يستخدم جدول تجزئة السبر الخطي ويتوقف البحث عند خانة فارغة. اشرح لماذا قد يفسد حذف مفتاح بمجرد تفريغ خانته البحث وكيف تعالج العلامات المحذوفة ذلك.

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

   شرح الإجابة

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

   1. الخانة الفارغة التي لم تُستخدم دليل أن لا مفتاح على سلسلة السبر يقع بعدها؛ أما المحذوفة فليست كذلك. تحفظ حالة حذف مستقلة هذا الفرق المنطقي.

   نقاط التصحيح

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

   ملاحظة الفاحص: يجب أن يميز البحث الخانات غير المستخدمة من المحذوفة.

6. 6.

   استخدم خوارزمية ديكسترا من A على رسم غير موجه: A-B=4 وA-C=1 وC-B=2 وB-D=1 وC-D=5. حدّد أقصر مسار من A إلى D واشرح لماذا تتطلب الخوارزمية أوزان حواف غير سالبة.

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

   شرح الإجابة

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

   1. تشمل بدائل D الأولية طريق C بوزن ستة. يعطي الإرخاء من B المحسنة أربعة بسوابق D<-B<-C<-A. يضمن الامتداد غير السالب أن بادئة أطول غير مثبتة لن تتغلب لاحقاً على أصغر مسافة مثبتة.

   نقاط التصحيح

   • تُثبت C عند مسافة 1.
   • تتحسن B إلى مسافة 3 عبر C.
   • أقصر مسار A-C-B-D ووزنه الكلي 4.
   • قد تسمح حواف سالبة لمسار لاحق بتحسين مسافة مثبتة فتُبطل قاعدة التثبيت الجشعة.

   ملاحظة الفاحص: للرسوم الموزونة ليس عدد حواف BFS بديلاً عن أقل وزن كلي.

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