UNIVERSITY EXAMINATIONS: 2012/2013
SECOND YEAR EXAMINATION FOR THE BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
DATA STRUCTURES AND ALGORITHMS
DATE: DECEMBER, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
a) Briefly define the following terms: [5 Marks]
i. Abstract data type (ADT)
ii. Data abstraction
iii. Data encapsulation
iv. Spanning tree
v. Order of magnitude
b) List and describe any five properties that an algorithm must possess. [5 Marks]
c) State and explain any six orders of magnitude commonly used in asymptotic time
complexity analysis. [6 Marks]
d) Distinguish between the following terms:
i. Analysis of algorithm and complexity of algorithm
ii. Depth-First-Search and Breadth-First-Search traversal algorithm
iii. Binary tree and binary search tree.
[6 Marks]
e) When sorting an array 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]
f) For large arrays and in the worst case is selection sort faster than insertion sort?
Explain [2 Marks]
QUESTION TWO
a) The following function computes the product of the first N≥1 real numbers in an
array.Demonstrate that this function is recursive by listing the criteria of a recursive
solution and state how this function satisfies the properties of a recursion function.
Double Product (const double A [], int N)
// Preconditions: 1<=N<=Max Size of A
// Post conditions: Return the product of the first N items in A; A is unchanged
{
If (N= =1)
return A [0];
else
return A [N-1]*Product (A, N-1);
} // end Product.
[8 Marks]
b) Write down the C++ specification for the array-based implementation of the ADTlist illustrating your answer with a diagram [6 Marks]
c) i. Explain how the use of the new operator can be used to allocate an array
dynamically. [2 Marks]
ii. Increasing the size of a dynamically allocated array can waste storage and time.
Explain [2 Marks]
iii. Show how you can increase the size of a dynamically allocated array [2 Marks]
QUESTION THREE
a) Define the structure node and write the C++ definition of the term. [3 Marks]
b) What is the value of the member next in the last node in the list [1 Mark]
c) What is a head pointer? Show how the pointer is created. [2 Marks]
d) i. Using the current pointer cur, write down the specification on how to display the
data in a linked list to which head points. [3 Marks]
ii. Using a diagram explain how to delete a specified node from a linked list. Write
the assignment statement to accomplish the task [5 Marks]
iii. For the case of (ii) above does the method work for any node N, regardless of
where in the linked list it appears? [2 Marks]
e) 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,T,N,J,A,B,E
[2 Marks]
ii. If you delete an item from a binary search tree and then insert it back into the
tree, will you ever change the shape of the tree? [2 Marks]
QUESTION FOUR
a) i. What is an ADT stack and why is it referred as LIFO? [2 Marks]
ii. Distinguish between an infix form of expression and postfix form of the
expression [2 Marks]
iii. Explain how a tree can be used to represent an expression [2 Marks]
b) i. Represent the expression as a binary tree and write the prefix and postfix form of
the expression: (((A+B)*C+D)*E)-((A+B)*C-D). [6 Marks]
ii. Find the value of the postfix expression: ADBCD*-+* using the following
identifiers A=1, B=2, C=3 and D=4. [4 Marks]
c) For the following situations, which of these ADTs( 1 through 4) would be most
appropriate (1) a queue (2) a stack, (3) a list, (4) none of these [4 Marks]
i. Integers that needs to be sorted
ii. The items on a cash register tape
iii. A program that uses backtracking
iv. Airplanes that stack above a busy airport waiting to land
QUESTION FIVE
a) Consider a sequential search of N data items.
i. If the data items are sorted into ascending order, how can you determine that
your desired item is not in the data collection without always making N
comparisons? [3 Marks]
ii. What is the order of the sequential search algorithm when the desired item is not
in the data collection? Do this for both sorted and unsorted data, and consider the
best, average and worst cases. [4 Marks]
b) How does binary search works? What properties must the input have? [3 Marks]
c) i. Define
f (n) O g(n)
. What is this notation called? [1 Mark]
ii. Give an intuitive interpretation on how f and g are related if
f (n) O g(n)
[2 Marks]
d) i. State a necessary and sufficient condition for a graph to have a spanning tree
[2 Marks]
ii. What is a minimal spanning tree? [2 Marks]
iii. Explain how Prims’ algorithm finds a minimal spanning tree. [3 Marks]
