Data structures and algorithm

EXAMINATION FOR THE DEGREE OF BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY

BBIT 122/ BIT 2102: DATA STRUCTURES/DATA STRUCTURES AND ALGORITHMS

  DATE: APRIL 2017                                                                                                   TIME: 2 HOURS                         

INSTRUCTIONS:

Answer question ONE and any other TWO questions

 

QUESTION ONE (COMPULSORY) (30MKS)

1. Distinguish the following giving examples of each
2. Complete tree and full tree (2 marks)
3. Static and dynamic data structure (2 marks)

• Homogenous and heterogeneous linked list (2 marks)

1. There are 8, 15, 13, and 14 nodes in 4 different trees. Determine which amongst them can form a full binary tree    (2 marks)
2. A program involves an algorithm. Explain the relationship between the two         (2 marks)
3. Describe four ways of representing an algorithm giving examples                        (12 marks)
4. Define a linked list and briefly describe three      (8 marks)

 

 

QUESTION TWO (20MKS)

1. Explain four critical requirements to consider when writing an algorithm   (4 marks)
2. Use an example to declare an array to store some elements in a program  (2 marks)
3. Suppose you are hired to create a database of a company to store employees’ details. Using examples, explain two ways this information can be stored              (6 marks)
4. Identify four tree traversal techniques used in data structure and use to traverse the tree below.                                                                                                                     (8 marks)

 

QUESTION THREE (20MKS)

1. With suitable examples explain two classes of data structures                        (4 marks)
2. As an expert in software development, explain to a novice the process of developing an effective program       (10 marks)
3. Here is an array of ten integers:

• 3  8  9  1  7  0  2  6  4

1. Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).                   (2 marks)
2. Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array.                       (2 marks)
3. Describe a binary tree and explain its uses     (2 marks)

 

 

QUESTION FOUR (20MKS)

1. As a software developer you have been requested to give advice on data structures. Explain to the person two main factors to be considered when selecting a data structure (4 marks)
2. Briefly describe the following operations as used in linked lists           (5 marks)

1. IsEmpty()
2. i-th(i)

• Head()

1. Insert(x,i)
2. Delete(i)
   1. Describe a situation where storing items in an array is clearly better than storing items on a linked list.         (3 marks)
   2. Explain four factors that affect the running time of a program                          (8 marks)