Birla Institute of Technology (BIT Mesra) 2007 MS Software Engineering Data Structure & Algorith - Question Paper

MS Software Engineering
Second Semester – 2007
Mid-semester exam
Duration : two Hours No of pages : 2

Data Structure & Algorithms

1.Give a big-Oh characterization, in terms of n of the running time for every of LOOP1 and LOOP2 methods 1+1

a. Algorithm LOOP1(n) :
S=0;
For (i=1; i<=n; i++)
S=S+i;

b. Algorithm LOOP2(n) :
p=1;
for (i=1; i<=n2; i++)
p=p.i;

2.Arrange the subsequent according to ascending order of complexity. 2

O(log n), O(n), O(n2 ), O(nlog n), O(1), O(2n ), O(n3 ),
O(log2n), O(Ön ).

3.Give the algorithm for implementing methods Push (element) & Pop (element) for a Stack 2+2

4. Construct an arithmetic expression tree for the expression ((a + b) * c) / (( d * e) + f). Perform in-order, pre-order and post-order traversal outcomes for the above tree constructed. 2+2+2+2

5. Mention the applications of Stacks & Queues 2


6. define how collisions are caused in hash tables. Mention any 1 mechanism to resolve collision in Hash tables. 3


7. Illustrate the working of Radix Sort on the subsequent set of Data.
(0,5,6) , (0,1,1), (0,7,8) , (1,1,2), (9,6,5), (5,6,8) , (5,5,4 )
4
8. Construct a heap-tree using Bottom-Up heap construction for the subsequent keys. Perform removeMin operation. Show the Down-Heap bubbling after a removeMin operation.
2+3
5,6,7,16,10,8,21,17,26,15,13,12,9,24,28.

9. provide the algorithm for sorting numbers using Quick-Sort and mention the time complexity. 3+1+2

10. discuss the divide and conquer paradigm and illustrate Merge-Sort to sort elements in ascending order. 2+2
95,34,73,55,27,41,86,80

Earning:   Approval pending.