BIT 121 DATA STRUCTURES AND ALGORITHMS

 BIT 121 DATA STRUCTURES AND ALGORITHMS

QUESTION ONE

a)     Define an algorithm and explain different criteria that satisfy the algorithm? (3 marks)

b)     i. What is a binary search tree? How is it different from a binary tree? (2 marks)
ii. Write an algorithm for the preorder traversal of a tree. (2 marks)

c)      Differentiate between Data Structure, Primitive Data type and abstract DataType (ADTs) (3marks)

d)     Explain the concept of memory leak and stack overflow as used in the study of data structures. (2 marks)

e)     Algorithm analysis is the study of an algorithm’s efficiency with respect to resource utilization. What are these resources? (2 marks)

f)       You are given an array elements of size n=100 of time complexity of f(n). Suppose you are to search for a given value using sequential search strategy explain the condition that will result in the following types of analysis.

i. Best Case (2 marks)

ii. Worst case (2 marks)

g)     Construct a binary tree representing an arithmetic expression. (4 marks)

((((3 + 1) * 3)/((9 – 5) + 2)) – ((3 * (7 – 4)) + 6))

 

h)     Figure 1 shows the structure of an array  named score in computer memory

72  67  86  94  55  69 65  71  53  78  82  56 67  89  73  67  54  78

Figure 1

Write a java code excerpt that will:

i. Create and initialize the structure as in figure 1 above. (2 marks)

ii. Compute Total and mean of each row and populate as new two columns on Right-hand-side of the structure. (3 marks)

iii. Sort the marks in ascending order. (Hint use the sort () method or function sparingly) (3 marks)

 

 

QUESTION TWO

a)     What are the different ways of representing a Binary Tree? (2 marks)

b)     Consider the binary tree in Figure 2:

Figure 2

 

Show intermediate tree steps to add element 58 in this tree. (3 marks)

c)      Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, in to an initially empty binary heap. (3 marks)

d)     Write the steps required to evaluate the postfix expression. (3 marks)

e)     Convert the infix (a+b)*(c+d)/f into postfix & prefix expression. (2 marks)

f)       Find out the inorder, preorder, postorder traversal for the binary tree representing the expression (a+b*c)/(d-e) with the help of procedures. (3 marks)

g)      If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact the list is known to be sorted? Give separate answers for

i. lists represented as arrays. (2 marks)

ii. lists represented as linked lists. (2 marks)

QUESTION THREE

a)     What is the difference between circular linked list doubly link list. Mention the applications of each type of list. (4 marks)

b)     What would be appropriate measures of cost to use as a basis for comparing the two sorting algorithms? (2 marks)

c)      Write a java code extract that implements the algorithms for pushing, popping and deleting data elements from the stack data structure. (4 marks)

d)     i. Write the selection sort algorithm (Ascending order), determine the running time (big O) and illustrate how it will sort the following list of elements: 89, 45, 68, 90, 29, 34 and 17. (5 marks)

ii. Write a java program to implement the algorithm in d (i) above. (5 marks)

 

QUESTION FOUR

a)     What is meant by a non-linear data structure? (2 marks)

b)     Distinguish between stack and queue. (3 marks)

c)      Suppose an array Score contains 6 elements as follows: 19, 11, 23, 9,3 and 15. Using relevant illustration explain how you will carry out the following Sorting algorithms. Which one will you prefer?

i. Insertion sort (3 marks)

ii. Bubble sort (3 marks)

d)     You must keep track of some data. Your options are:

A linked-list maintained in sorted order A linked-list of unsorted records A binary search tree An array-based list maintained in sorted order An array-based list maintained in sorted order. An array-based list of unsorted records

 

For each of the listed scenarios, which choices would be best? Explain your answer. (3 marks)

e)     The elements of arrays in Table 1 and Table 2 represent 5 student and score of 2 students in five subjects respectively. Use it to answer questions that follow.

Student

BIT1

BIT2

BIT3

BIT4

BIT5

Table 1: Array of Students

            Score

11	15	19	16	17
10	26	25	28	23

Table 2: Array of Score

i. write a signature/syntax of creating array and initializing a students and a scores arrays (3 marks)

            ii. State the output of the following code segments (3 marks)

1 3 4

Student[3] Student[1][2] Student[2][2]

 

QUESTION FIVE

a)     Draw a Binary search tree for the following input list 60, 25, 75, 15, 50, 66, 33, 44. Trace the algorithm to delete the nodes 25, 75, 44 from the tree. (4 marks)

b)     Give the main property of a heap that is implemented as an array (2 marks)

c)      Explain how searching algorithms work using 60, 25, 75, 15, 50, 66, 33, 44 and 33 as the search key. (4 marks)

d)     Draw a binary tree to evaluate the following fully parenthesized expression and evaluate it.

(((8 * 3) + 2)/ (21 – (2 ^ 3)))

i. Binary Tree for the Above Expression (3 marks)

ii. Evaluation of the fully parenthesized expression (3 marks)

e)     Suppose that a particular algorithm has time complexity T(n) = 3(2ⁿ), and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?