Computer Science

1. 1.

   A sorted list contains 1024 distinct items. Explain binary search and give the worst-case number of midpoint comparisons to find an item or establish it is absent.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Each midpoint comparison roughly halves the remaining search interval, including the possibility of a final single item.
   2. Compare the target with the middle item.
   3. Discard the half that cannot contain it, repeating until found or the interval is empty.
   4. Worst case is 11 midpoint comparisons for 1024 items.
   5. The time complexity is O(log n); the list must be sorted.

   Marking points

   • Compare the target with the middle item.
   • Discard the half that cannot contain it, repeating until found or the interval is empty.
   • Worst case is 11 midpoint comparisons for 1024 items.
   • The time complexity is O(log n); the list must be sorted.

   Examiner tip: 1024 = 2^10 does not imply a worst case of ten midpoint comparisons: the final item can require an eleventh.

2. 2.

   A table Enrolment(StudentID, StudentName, CourseID, CourseName) uses (StudentID, CourseID) as its key. StudentID determines StudentName and CourseID determines CourseName. Explain the normalisation problem and propose a decomposition into second normal form.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Identify dependencies on only part of the composite key. Separate the entities while preserving their many-to-many enrolment relationship.
   2. The non-key attributes depend on only part of the composite key: partial dependencies.
   3. Create Student(StudentID, StudentName) and Course(CourseID, CourseName).
   4. Keep Enrolment(StudentID, CourseID), using foreign keys to the two new tables.
   5. This avoids repeating student and course names across enrolment rows.

   Marking points

   • The non-key attributes depend on only part of the composite key: partial dependencies.
   • Create Student(StudentID, StudentName) and Course(CourseID, CourseName).
   • Keep Enrolment(StudentID, CourseID), using foreign keys to the two new tables.
   • This avoids repeating student and course names across enrolment rows.

   Examiner tip: Second normal form assumes first normal form; removing partial dependencies is the key step here.

3. 3.

   Simplify NOT(A AND B) using De Morgan's law. Evaluate the result when A = true and B = false.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Negating a conjunction changes AND to OR and negates each input. Substitute the truth values only after rewriting.
   2. NOT(A AND B) = (NOT A) OR (NOT B).
   3. NOT A is false and NOT B is true.
   4. false OR true is true.

   Marking points

   • NOT(A AND B) = (NOT A) OR (NOT B).
   • NOT A is false and NOT B is true.
   • false OR true is true.

   Examiner tip: Changing only AND to OR without negating both operands is not De Morgan's law.

Original, unofficial practice questions from SubjectScout — not official past-paper questions.