ALCCS
FEBRUARY 2009
Code: CS21 Subject: DATA STRUCTURES & ALGORITHM DESIGN
Time: 3 Hours Max. Marks: 100
NOTE:
· Question 1 is compulsory and
carries 28 marks. Answer any FOUR questions from the rest. Marks are indicated against each question.
· Parts of a question should be
answered at the same place.
Q.1 (7
x 4)
a. Consider a queue whose
capacity is 6. Following operations are carried out in the sequence shown:
(i) Objects
A, B, D, H added
(ii) An
object removed
(iii) Object I added
(iv) An object removed
(v) Object C
added
Show the 5 queue representations after each
operation is carried out.
b. Write a recursive function,
which computes mn where both m and n are integers.
c. Calculate the asymptotic complexity of the
code segments shown below (using big-O notation) with respect to the problem
size n:
(i) for (i = 0; i
< n; i=i*2) {
for (j = 1; j < n; j++) {
...
}
}
(ii) for
(i = 0; i < n-2; i++) {
for (j = 0; j < n; j=j*2) {
for (k = 1; k < 5000; k=k*5) {
...
}
}
for (j = 0; j < 1000*n; j=j+1) {
...
}
for (j = 0; j < n/5; j=j+5) {
...
}
}
d. Suppose we build the Huffman code tree for the
set of letters and frequencies given below:
Character:
A B C D E F
Frequency: 1 5 20 30
40 50
What
will be the length of the code for the character B?
e. An array contains n random
integers. It is sorted using merge sort
method. Indicate the time complexity if
this new sorted array is again sorted using
(i) merge sort
(ii) quick sort
f. Given a sequence S containing the
elements 4, 15, 6, 3, 21, and 2. Insert
these elements in the given order into an initially empty Binary Search tree.
g.
A singly linked list STAR contains an
integer in each node. Show how one can
delete the first node from this list.
Q.2 a. Write the adjacency matrix AND the
adjacency linked list for this undirected graph. (10)
b. Given a tree with n vertices, how many
edges does it have? Prove the correctness of your conclusion. (8)
Q.3 a. Show the operation of applying the MergeSort
algorithm on the list
14, 25, 3, 21, 7, 35, 18, 27 (10)
b. What is the efficiency of the MergeSort
algorithm? What is the efficiency of InsertionSort, BubbleSort and
SelectionSort algorithms in the worst case? (8)
Q.4 a. What is meant by breadth-first traversal and breadth-first
search of an undirected graph? Write down an iterative breadth-first
traversal algorithm. (10)
b. Consider the following undirected graph.
Draw
a DFS and BFS tree for the graph starting at node A. If several nodes can be
chosen at some step, pick the vertex that is alphabetically first. (8)
Q.5 a. Two stacks are implemented using an array A
[10] as shown in the figure. What would be the initial values of top for the
two stacks? Arrows shows the direction of growth of the stack.
Array A [10]
S1 S2
Code
the PUSH and POP routines for the stacks. (10)
b. Convert the following infix expression to
postfix expression
A+B*(C+D)/F+D*E
Draw
a binary tree containing keys P, L, A, C, E, such that the postorder traversal
visits nodes in this order: E, A, L, C, P and the inorder traversal visits
nodes in order: E, L, A, P, C. (8)
Q.6 a. Write a recursive algorithm to compute the sum
of squares from given number m to n i.e. Compute m2 + (m+1) 2 …..+
n2 (8)
b. An array contains the following elements [17
46 5 23 20]. Use the heap sort method to
sort the elements in increasing order.
Draw the heap trees as you move through each step. (10)
Q.7 a. Consider the following graph. Using Kruskal’s algorithm, calculate
the minimum spanning tree, listing edges in the minimal spanning tree in the
order they are added to the tree. (10)
b. Solve the following recurrence relation T(n) =
T(n-1) + n. (8)