Code: C-06 / T-06 Subject: DATA STRUCTURES & ALGORITHM DESIGN
Time: 3 Hours Max. Marks: 100
NOTE: There are 11 Questions in all.
· Question 1 is compulsory and carries 16 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.
· Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.
· Any required data not explicitly given, may be suitably assumed and stated.
Q.1 Choose the correct or best alternative in the following: (2x8)
a. A complete binary tree with the property that the value of each node is at least as large as the values of its children is known as
(A) Binary Search Tree. (B) AVL Tree.
(C) Heap. (D) Threaded Binary Tree.
b. A sorting algorithm is stable if
(A) its time complexity is constant irrespective of the nature of input.
(B) preserves the original order of records with equal keys.
(C) its space complexity is constant irrespective of the nature of input.
(D) it sorts any volume of data in a constant time.
c. A tree in which, for every node, the difference between the height of its left subtree and right subtree is not more than one is
(A) AVL Tree. (B) Complete Binary Tree.
(C) B – Tree. (D)
Tree.
d. The data structure needed to convert a recursion to an iterative procedure is
(A) Queue. (B) Graph.
(C) Stack. (D) Tree.
e. A binary tree stored using linked representation can be converted to its mirror image by traversing it in
(A) Inorder. (B) Preorder.
(C) Postorder. (D) Any order.
f. The prefix form of an infix expression A+B-C*D is
(A) +AB-*CD. (B) -+A B C * D.
(C) -+A B * C D. (D) - + *ABCD.
g. The number of edges in a simple, n-vertex, complete graph is
(A) n*(n-2). (B) n*(n-1).
(C) n*(n-1)/2. (D) n*(n-1)*(n-2)
h. The largest and the second largest number from a set of n distinct numbers can be found in
(A) O (n). (B) O (2n).
(C) O 
. (D)
O (log n).
PART I
Answer any THREE Questions. Each question carries 14 marks.
Q.2 a. What is an Abstract Data Type (ADT)? Explain with an example. (4)
b. Suppose we wish to partition the square roots of the integers from 1 to 100 in to two piles of fifty numbers each, such that the sum of the numbers in the first pile is as close as possible to the sum of the numbers in the second pile. If you could use minimum computer time to answer this question, what computations would you perform on the computer in that time? (5)
c. Suppose we wish to
multiply four matrices of real numbers M1*M2*M3*M4 were M1 is 10*20, M2 is
20*50, M3 is 50*1 and M4 is 1*100. Assume that the multiplication of a p*q
matrix by q*r matrix requires pqr scalar operations, find the optimal order in
which to multiply the matrices so as to minimize the total number of scalar
operations. (5)
Q.3 a. Devise a representation for a list where insertions and deletions can be made at either end. Such a structure is called a deque (double ended queue). Write a procedure for inserting and deleting at either end. (6)
b. Farely fractions of level one is defined as sequence (0/1, 1/1). This sequence is extended in level two to form a sequence (0/1, ½, 1/1), sequence (0/1, 1/3, ½, 2/3, 1/1) at level three, sequence (0/1, ¼, 1/3, ½, 2/3, ¾, 1/1) at level four, so that at each level n, a new fraction (a+b) / (c+d) is inserted between two neighbour fractions a/c and b/d only if c+d <= n. Devise a procedure, which for a number n entered by the user creates – by constantly extending it – a linked list of fractions at level n. (8)
Q.4 a. Show a tree (of more than one node) for which the preorder and inorder traversals generate the same sequence. Is this possible for preorder and post order traversals? If it is, show an example. (5)
b. Write modules to do the following operations on a Binary Tree.
(i) Count the number of leaf nodes.
(ii) Count the number of nodes with two children.
(iii) Find the height of the tree. (9)
Q.5 a. Is it possible to implement a linked list in an array? If yes, give the functions similar to new and delete respectively to allocate and deallocate space from array. (7)
b. If n >=1, prove that for any n-key B-tree T of height h and minimum degree t >= 2, h <= log t (n+1)/2. (7)
Q.6 A cocktail shaker sort designed by Donald Kunth is a modification of bubble sort in which the direction of bubbling changes in each iteration: in one iteration, the smallest element is bubbled up; in the next, the largest is bubbled down; in the next, the second smallest is bubbled up; and so forth. Write an algorithm to implement this and explore its complexity. (14)
PART II
Answer any THREE Questions. Each question carries 14 marks.
Q.7 Consider the following undirected graph:
|
(i) Find a minimum cost spanning tree by Kruskal’s algorithm.
(ii) Find a depth-first spanning tree starting at a and at d.
(iii) Find a breadth-first spanning tree starting at a and at d.
(iv) Find the adjacency list representation of the graph. (3.5 x 4 = 14)
Q.8 a. Work through Binary Search algorithm on an ordered file with the following keys: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}. Determine the number of key comparisons made while searching for keys 2, 10 and 15. (6)
b. What are threaded binary trees? What are the advantages and disadvantages of threaded binary trees over binary search trees? (4)
c. Show that quick algorithm
takes O time
in the worst case. (4)
Q.9 a. Write
an algorithm to convert an infix expression to a postfix expression. Execute
your algorithm with the following infix expression as your input. 
(8)
b. What is recursion? A recursive procedure should have two properties. What are they? (4)
c. What type of recursive procedure can be converted in to iterative procedure without using a stack? Explain with an example. (2)
Q.10 a. Suppose characters a,b,c,d,e,f have probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 respectively. Find an optimal Huffman code and draw the Huffman tree. What is the average code length? (10)
b. Prove that the number of nodes with degree 2 in any Binary tree is 1 less than the number of leaves. (4)
Q.11 a. Suppose that a Binary Search Tree is constructed by repeatedly inserting distinct values in to the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted in to the tree. (7)
b. Equal keys pose problem for the implementation of Binary Search Trees. What is the asymptotic performance the usual algorithm to insert n items with identical keys into an initially empty Binary Search Tree? Propose some technique to improve the performance of the algorithm. (7)