DATA STRUCTURES/DATA STRUCTURES AND ALGORITHMS

DATA STRUCTURES/DATA STRUCTURES AND ALGORITHMS

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

 

QUESTION ONE (30 MARKS)-COMPULSORY

1. State and explain any FOUR properties of an algorithm.                     (4 Marks)
2. Define the term data structure clearly distinguishing between linear and non-linear data structure                                                                                               (5 Marks)
3. Differentiate between the following terms and give an example algorithm for each:
4. Iteration
5. Recursion                                                                                       (6 Marks)
6. Examine any FIVE factors that may affect the running time of an algorithm (5 Marks)
7. e) Describe Three types of linked lists used in data structures               (6 Marks)
8. 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)

 

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

iii. Insert an element E

1. Remove and return an element (8 Marks)
2. 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)
3. Explain how a binary search algorithm works and state a situation in which it works best.

(2 Marks)

3. 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)

1. 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)

 

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

 

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

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

1. Push an element into the stack
2. Pop and display an element (10 Marks)
3. Consider the tree given below:

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

1. Preorder traversal
2. Inorder traversal

iii. Postorder traversal                                                                                  (6 Marks)

 

 

 

QUESTION FOUR (20 MARKS)

 

1. Describe how the following sorting algorithms work:
2. Bubble sort
3. Selection sort

iii. Insertion sort                                                                                           (6 Marks)

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

Sort the values clearly showing your working using:

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