061306T4CSC
COMPUTER SCIENCE LEVEL 6
IT/OS/CS/CR/08/6/A
UNDERSTAND ALGORITHMS AND DATA STRUCTURES
WRITTEN ASSESSMENT
TIME: 3 HOURS
INSTRUCTIONS TO CANDIDATES
1. Answer ALL questions in Section A and ANY THREE from Section B.
This paper consists of 2 printed pages.
Candidates should check the question paper to ascertain that all the pages are printed
as indicated and that no questions are missing.
TURN OVER
SECTION A (40 MARKS)
Answer ALL questions. Each question is worth 4 marks.
1. Define an algorithm and list any three key characteristics that a well-defined
algorithm must possess.
2. A developer has two algorithms for sorting a list. Algorithm X has a time complexity
of O(n²) and Algorithm Y has a complexity of O(n log n). Explain, with a practical
example, which algorithm is more efficient for sorting a very large dataset and why.
3. Differentiate between a Stack and a Queue data structure by stating their fundamental
operating principles and providing one real-world application for each.
4. Describe the process of a Linear Search algorithm. State one major advantage and
one major disadvantage it has compared to a Binary Search.
5. Given the following array: [45, 12, 89, 5, 67], trace the steps of the Bubble Sort
algorithm to sort the array in ascending order. Show the state of the array after each
complete pass.
6. Explain the role of a base case in a recursive algorithm. What is the critical issue that
arises if a base case is not properly defined?
7. Differentiate between a Singly Linked List and a Doubly Linked List. State one
operational advantage of a Doubly Linked List.
8. Explain the term Greedy Algorithm. Provide one example of a problem that can be
solved using a greedy approach.
9. Describe the purpose of the Divide and Conquer paradigm. Name one common
sorting algorithm that uses this strategy.
10. When inserting a new node at the beginning of a Singly Linked List, explain the
sequence of steps (in words or pseudocode) required to ensure the list integrity is
maintained.
SECTION B (60 MARKS)
Answer any THREE questions from this section
QUESTION 11
a) i) Define the term time complexity and space complexity in algorithm analysis. (4 marks)
ii) Categorize the following time complexities from most efficient to least efficient: O(1),
O(n!), O(log n), O(n), O(n²). (2 marks)
b) Write a well-structured C++ code snippet to implement a function that performs a Binary
Search on a sorted array of integers. The function should take the array, its size, and the
target value as parameters and return the index of the target or -1 if not found. Include clear
comments to explain key steps. (10 marks)
c) Explain why the Binary Search algorithm you implemented in (b) requires the input array
to be pre-sorted. (4 marks)
QUESTION 12
a) i) Explain the principle of operation of the Stack data structure, stating the names of its
two primary operations. (4 marks)
ii) Describe a real-world scenario where a Stack would be the most appropriate data structure
to use, justifying your choice. (2 marks)
b) Write a complete C++ code to implement a Stack of integers using an array. Your code
should include functions for push, pop, and displaying the stack elements. Assume a
maximum stack size of 100. (10 marks)
c) Explain one key limitation of implementing a Stack using a fixed-size array, as you did in
part (b). (4 marks)
1
QUESTION 13
a) i) Differentiate between an Array and a Linked List in terms of memory allocation and
efficiency of insertion/deletion operations. (4 marks)
ii) State one key advantage of an Array over a Linked List. (2 marks)
b) Write a C++ code snippet to implement a function that deletes a node containing a
specific value from a Singly Linked List. Your code should handle cases where the node to
be deleted is at the head, in the middle, or at the tail of the list. Assume a
predefined Node structure with data and next pointer. (10 marks)
c) Explain the importance of properly deallocating memory in your Linked List operations to
prevent memory leaks. (4 marks)
QUESTION 14
a) i) Describe the step-by-step process of the Insertion Sort algorithm. (4 marks)
ii) State its best-case time complexity and the scenario in which it is achieved. (2 marks)
b) Write a C++ function that implements the Insertion Sort algorithm to sort an array of
integers in ascending order. Provide comments to explain the logic. (10 marks)
c) Compare Insertion Sort with the Merge Sort algorithm, highlighting one key advantage of
Merge Sort for large datasets. (4 marks)
QUESTION 15
a) i) Explain the concept of a recursive algorithm. (3 marks)
ii) Write a recursive function in pseudocode or C++ to calculate the factorial of a non-
negative integer n. (3 marks)
b) Write a C++ code to implement a Queue data structure using two integer arrays (or arrays
of your choice) to simulate the enqueue and dequeue operations. Your code should include
functions for enqueue, dequeue, and isEmpty. (10 marks)
c) Explain the overflow and underflow conditions in the context of the Queue you
implemented in (b) and how they should be handled. (4 marks)
