**DATA STRUCTURES/****DATA STRUCTURES AND ALGORITHMS**

**INSTRUCTIONS: ANSWER QUESTION ONE (COMPULSORY) AND ANY OTHER TWO QUESTIONS**

** **

**QUESTION ONE (30 MARKS)-COMPULSORY**

- State and explain any FOUR properties of an algorithm. (4 Marks)
- Define the term data structure clearly distinguishing between linear and non-linear data structure (5 Marks)
- Differentiate between the following terms and give an example algorithm for each:
- Iteration
- Recursion (6 Marks)
- Examine any FIVE factors that may affect the running time of an algorithm (5 Marks)
- e) Describe Three types of linked lists used in data structures (6 Marks)
- f) Give an example of a situation where storing items in an array is clearly better than storing items on a linked list (4 Marks)

**QUESTION TWO (20 MARKS)**

__ __

- Define the term queue as applied in data structures (1 Mark)
- Write an algorithm to:
- Check if a queue is full
- Check if a queue is empty

iii. Insert an element E

- Remove and return an element (8 Marks)
- Supposing the characters ‘D’, ‘C’, ‘B’, ‘A’ are placed in a queue (in that order), and then removed one at a time, in what order will they be remove (2 Marks)
- Explain how a binary search algorithm works and state a situation in which it works best.

(2 Marks)

- Given the following values; explain the execution steps of binary search algorithm to search for the number 3.

2, 3, 8, 16, 22, 27, 28, 36, 40, 48 (3 Marks)

- Examine two major disadvantage brought about by linear queues and state the implementation of queues that solves the stated problem (4 Marks)

**QUESTION THREE (20 MARKS)**

** **

- Describe the two stack operations pop ( ) and push ( ) (4 Marks)
- Write an algorithm to:

- Initialize a stack mystack[maxsize]
- Check if the stack in part (i) above is empty

iii. Check if the stack in part (i) above is full

- Push an element into the stack
- Pop and display an element (10 Marks)
- Consider the tree given below:

Show the traversal sequence when searching for G using depth first search for:

- Preorder traversal
- Inorder traversal

iii. Postorder traversal (6 Marks)

__ __

__ __

__ __

**QUESTION FOUR (20 MARKS)**

__ __

- Describe how the following sorting algorithms work:
- Bubble sort
- Selection sort

iii. Insertion sort (6 Marks)

- You have been provided with the following values; 2, 10, 8, 5, 4, 16

Sort the values clearly showing your working using:

- Selection sort
- Insertion sort (6 Marks)
- c) Analyze any TWO operations of an ordinary list. (4 Marks)
- Explain FOUR key aspects you should bear in mind when designing an algorithm and implementing it as a program (4 Marks)