UNIVERSITY EXAMINATIONS: 2011/2012
YEAR 2 EXAMINATION FOR THE BACHELOR OF SCIENCE IN
INFORMATION TECHNOLOGY
BIT 2102 DATA STRUCTURES AND ALGORITHMS
DATE: APRIL 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question One and Any other Two Questions
QUESTION ONE [30 MARKS]
(a)Distinguish between Abstract data type (ADT) and Data structures [4 Marks]
(b) (i) What is list? [2 Marks]
(ii) List and explain any two properties of a list
[2 Marks]
(c)Given the expression below, convert them to their postfix or RPN form. Hence represent the results
on a expression tree:
(i) A*B+C [2 Marks]
(ii) ((A+B)*C)/(D-E) [3 Marks]
(iii) A*(B+C) [2 Marks]
(d)Differentiate between a static array and a dynamic array. Use C++ to illustrate the declaration.
[4 Marks]
(e)(i) What is a deque? [2 Marks]
(ii) Explain any four operations that can be carried out on a queue and write the pseudocode for the
operation [4 Marks]
(f) (i) Describe the criteria you will consider before deciding to construct a recursive solution to a
problem [4 Marks]
(ii) What is a base case? [1 Mark]
QUESTION TWO [20 MARKS]
(a)(i) Write the statement you would use for an array-based implementation of the ADT-list.
[3 Marks]
(ii) Use a visual sketch to demonstrate how ADT-linear list may be implemented using an array.
[3 Marks]
(iii) State three problems that might arise if an array is full of gaps. [3 Marks]
(b)(i) Distinguish between a sequential search and a binary search algorithm [4 Marks]
(ii) Perform an analysis for the binary search algorithm [4 Marks]
(c)What is the addresses of A[0,0] in an array stored linearly in Row-major beginning in addresses
alpha if it is declared as A[-5..1,-2…4] [3 Marks]
QUESTION THREE [20 MARKS]
(a)If you push the letters A, B, C, D in order onto a stack of characters and then pop them, in what
order will they be deleted from the stack. [2 Marks]
(b)What do the initially empty stacks S and T ‘look like’ after the following sequence of operations:
S.Push(1,Success)
S.Push(2,Success)
S.Push(3,Success)
T.Push(4,Success)
S.Pop(Success)
T.GetstackTop(Stacktop,Success)
S.Push(StackTop,Success)
S.Push(5,Success)
T.Pop(StackTop,Success)
T.Push(6,Success)
[4 Marks]
(c)Consider the iterative definition of Factorial of n.
(0) 0
( ) *( 1) *( 2) *…..* 2*1
=
= − −
Factorial
Factorial n n n n
(i) Construct a C++ function that implements the definition. [4 Marks]
(ii) Demonstrate that the factorial satisfies the four criteria of a solution. [4 Marks]
(d)(i) What is an algorithm? [2 Marks]
(ii) Describe the following properties that an algorithm must have: precision, uniqueness,
finiteness, input, output and generality [4 Marks]
QUESTION FOUR [20 MARKS]
(a)If you add the letters A,B,C and D in sequence to a queue of characters and then remove them, in
what order will they be deleted from the queue. [2 Marks]
(b)Use visual sketch and C++ assignment statements to demonstrate how to achieve the following
queues operations:
(i) Insert an item into a non-empty queue. [4 Marks]
(ii) Delete an item from a queue of more than one item. [4 Marks]
(c)When sorting an array by using mergesort,
(i) Do the recursive calls to mergesort depend on the values in the array, the number of items in
the array or both? Explain. [3 Marks]
(ii) In what step of mergesort are the items in the array actually swapped( that is sorted)?
Explain. [3 Marks]
(d)(i) Explain how the divide and conquer techniques works. [3 Marks]
(ii) What is a recursive algorithm? [1 Mark]
QUESTION FIVE [20 MARKS]
(a)(i) What is a full binary tree? Give an example. [3 Marks]
(ii) If T is a full binary tree with n-internal nodes how many terminal nodes does T have?
[1 Mark]
(b) (i) What is a binary search tree? [2 Marks]
(ii) Starting with an empty binary tree, what binary search tree is formed when you insert the
following values in the order given: 60,70,20,10,40,30,50. [3 Marks]
(iii)If you delete an item from a binary search tree, will you ever change the shape of the tree?
[3 Marks]
(c)What is the order of the following tasks in the worst case?
(i) Displaying all N integers in an array
(ii) Displaying the last integer in a linked list
(iii)Searching an array of N integers for a particular value by using a binary search
(iv)Adding an item to a stack of N items
[4 Marks]
(d)Evaluate the following postfix expression; AB+C-DE*+. Show the status of the stack after each
step of the algorithm. Assume the following values for the identifier: A=3,B=12,C=7,D=1,E=-5
[4 Marks]
—————————————————
