UNIVERSITY EXAMINATIONS: 2011/2012
SECOND YEAR EXAMINATION FOR THE BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3101A 2102 DATA STRUCTURES AND ALGORITHIMS
DATE: AUGUST, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
a) Define the following terms:
i. Algorithm
ii. Spanning tree
iii. Miniheap and
iv. Selection sort
[4 Marks]
b) State four advantages of implementing data structures as abstract data types
[4 Marks]
c) i. State under what conditions you would choose an array-based
implementation for the stack and also under what conditions would you
choose a pointer-based implementation. [4 Marks]
ii. If you push the letters D, C, B and A in order onto a stack of characters
and then pop them, in what order will they be deleted from the stack?
[2 Marks]
d) Define a recursive function and give any two examples that can be solved
recursively. [2 Marks]
e) The numbers 10, 72, 86, 95,30,15,90,70,60,85 are to be stored for some
processing in that order. Write down the order in which the numbers will be
printed if they are:(i) stored in a queue (ii) stored in a stack and (iii) stored in a
binary search tree and traversed in order.
[8 Marks]
f) i. State a necessary and sufficient condition for a graph to have a spanning
tree. [2 Marks]
ii. Explain how Prims’ algorithm finds a minimal spanning tree [2 Marks]
iii. True or False. If all the weights in a connected graph G are distinct,
distinct spanning trees of G have distinct weight. [2 Marks]
QUESTION TWO
a) 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 (i.e. sorted)?
Explain. [3 Marks]
b) i. A pointer based implementation of a list require more memory than a
array- based implementation. Explain. [2 Marks]
ii. A circular doubly linked list eliminates special cases for insertion and
deletion. Explain [2 Marks]
c) Suppose you have a sorted array and you use a binary search to determine
Whether a given integer occurs in the array. Next you display all the
integers in the sorted array. which algorithm is faster, in general, the
binary search or displaying the integer? Explain in terms of the Big O
notation [3 Marks]
d) i. Explain how the divide and conquer technique works. [3 Marks]
ii. What is a base case in a recursive procedure? Explain why every recursive
procedure must have a base case. [4 Marks]
QUESTION THREE
a) Define the following terms with respect to graphs:
i. Connected graph
ii. Degree of a vertex
iii. Cycle and
iv. Simple path
[4 Marks]
b) Represent the following expression tree: (((A+B)*C+D)*E)-((A+B)*C-D) and
write the prefix and postfix expressions. [6 Marks]
c) i. Describe Dijkstras shortest-path problem. [2 Marks]
ii. State necessary and sufficient condition that a graph has a path with no
repeated edges from v to w(v ≠ w) containing all the edges and vertices.
[2 Marks]
d) Let T be a tree connected by Dijkstra’s algorithm in the process of solving the
single-source shortest path problem for a weighted connected graph G. True or
false:
i. T is a spanning tree of G
ii. T is a minimum spanning tree of G.
[2 Marks]
e) i. Distinguish between preorder and postorder traversal [2 Marks]
ii. Give example of distinct binary trees B1 and B2, each with two vertices,
with preorder vertices listing of B1 equals to the post-order listing of B2.
[2 Marks]
QUESTION FOUR
a) Suppose that you have a stack S and an empty auxiliary stack T. Show how you
can do each of the following tasks by using only the ADT stack operations
i. Display the contents of S in reverse order; that is, display the top last. [3 Marks]
ii. Count the number of items in S, leaving S unchanged. [3 Marks]
iii. Delete every occurrence of a specified item from S, leaving the order of the
remaining items unchanged. [3 Marks]
b) For large arrays and in the worst case, is selection sort faster than insertion sort.
Explain. [2 Marks]
c) The factorial function can be defined can be defined by the recurrence relation
Factorial n
i. Write down the C++ function that implements the definition indicating the
preconditions and post conditions. [3 Marks]
ii. Demonstrate that the function in (i) is recursive by listing the criteria of a
recursive solution and stating how the function meets each criterion. [6 Marks]
QUESTION FIVE
a) i. How do binary search works. What properties must the input have?
[4 Marks]
ii. Estimate how many times faster an average successful search will be in a
sorted array of 100,000 elements if it is done by binary search versus
sequential search [4 Marks]
b) What is the order of each of the following tasks in the worst case? [4 Marks]
i. Displaying all N integers in an array
ii. Displaying the last integer in a linked list.
iii. Adding an item to a stack of N items
iv. Adding an item to a queue of N items
c) i. Beginning with an empty binary search tree, what binary search tree is
formed when you insert the following values in the order given W I L B E
R F O R C E [3 Marks]
ii. Show the results of traversing the BST of (i) above in inorder. [2 Marks]
d) What is the order of magnitude for the following expression? [3 Marks]
i n ii n n n2
