علوم الحاسوب

1. 1.

   قائمة مرتبة فيها 1024 عنصراً مختلفاً. اشرح البحث الثنائي وحدد أكبر عدد من مقارنات المنتصف لإيجاد عنصر أو إثبات غيابه.

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

   شرح الإجابة

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

   1. تُنصف كل مقارنة منتصف مجال البحث المتبقي تقريباً، مع احتمال عنصر أخير منفرد.
   2. قارن المطلوب بعنصر المنتصف.
   3. استبعد النصف الذي لا يمكن أن يحتويه وكرر حتى تجده أو يفرغ المجال.
   4. أسوأ حالة هي 11 مقارنة منتصف لـ1024 عنصراً.
   5. التعقيد الزمني O(log n) ويجب أن تكون القائمة مرتبة.

   نقاط التصحيح

   • قارن المطلوب بعنصر المنتصف.
   • استبعد النصف الذي لا يمكن أن يحتويه وكرر حتى تجده أو يفرغ المجال.
   • أسوأ حالة هي 11 مقارنة منتصف لـ1024 عنصراً.
   • التعقيد الزمني O(log n) ويجب أن تكون القائمة مرتبة.

   ملاحظة الفاحص: 1024 = 2^10 لا تعني عشر مقارنات في أسوأ حالة؛ قد يتطلب العنصر الأخير الحادية عشرة.

2. 2.

   جدول Enrolment(StudentID, StudentName, CourseID, CourseName) مفتاحه (StudentID, CourseID). يحدد StudentID الاسم ويحدد CourseID اسم المقرر. اشرح مشكلة التطبيع واقترح تفكيكاً إلى الصيغة الطبيعية الثانية.

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

   شرح الإجابة

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

   1. حدد الاعتماد على جزء من المفتاح المركب. افصل الكيانات مع الحفاظ على علاقة التسجيل المتعددة.
   2. تعتمد الصفات غير المفتاحية على جزء فقط من المفتاح المركب: اعتماد جزئي.
   3. أنشئ Student(StudentID, StudentName) وCourse(CourseID, CourseName).
   4. أبقِ Enrolment(StudentID, CourseID) بمفاتيح خارجية إلى الجدولين الجديدين.
   5. يمنع ذلك تكرار أسماء الطلاب والمقررات عبر صفوف التسجيل.

   نقاط التصحيح

   • تعتمد الصفات غير المفتاحية على جزء فقط من المفتاح المركب: اعتماد جزئي.
   • أنشئ Student(StudentID, StudentName) وCourse(CourseID, CourseName).
   • أبقِ Enrolment(StudentID, CourseID) بمفاتيح خارجية إلى الجدولين الجديدين.
   • يمنع ذلك تكرار أسماء الطلاب والمقررات عبر صفوف التسجيل.

   ملاحظة الفاحص: تفترض الصيغة الثانية تحقق الأولى؛ إزالة الاعتماد الجزئي الخطوة الأساسية هنا.

3. 3.

   بسّط NOT(A AND B) باستخدام قانون دي مورغان ثم قيّمه عندما A = true وB = false.

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

   شرح الإجابة

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

   1. يغير نفي الاقتران AND إلى OR وينفي كل مدخل. عوّض قيم الصواب بعد إعادة الكتابة.
   2. NOT(A AND B) = (NOT A) OR (NOT B).
   3. NOT A تساوي false وNOT B تساوي true.
   4. false OR true تساوي true.

   نقاط التصحيح

   • NOT(A AND B) = (NOT A) OR (NOT B).
   • NOT A تساوي false وNOT B تساوي true.
   • false OR true تساوي true.

   ملاحظة الفاحص: تغيير AND إلى OR وحده دون نفي المدخلين ليس قانون دي مورغان.

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