Jawaharlal Nehru Technological University Hyderabad 2011-2nd Sem M.C.A Code No: F3201 –s –uary - DATA STRUCTURES AND ALGORITHMS - Question Paper

Time: 3hours Max. Marks: 60
ans any 5 ques.
All ques. carry equal marks
- - -
1. a) choose a theta notation for the subsequent expressions
i) n2+2n+1
ii) two lg n +4n + 3n lg n
iii) (6n+4)(1+lg n)
iv) 1+2+4+8+………+2n-1
b) Write ADT for stack
c) Differentiate ranging from Array and Linked allocations of linear list with respect to
time complexities of different operations

2. a) Write an algorithm for converting the provided infix expression into post fix
expression and demonstrate stack contents for the expression a+b*(c-d)+e
b) Write a linear time algorithm that swaps the left and right children of every node
in a binary tree.

3. a) What is a heap? provide applications of heap. Write algorithm for insertion and
deletion operations of heap. Illustrate your algorithms with examples.
b) Write an algorithm to obtain whether the provided graph contains a cycle of length k
or not.

4. a) provided a text file, you want to obtain the frequency of occurrences of every word in
the text. Which data structure is most efficient? Justify your ans.
b) Write an algorithm for insertion sort and demonstrate your algorithm on
subsequent dataset.
18 six 12 five 10 three eight seven 11

5. There are n bolts and n nuts. every bolt is exactly matches with 1 nut and vice
varsa. provided 1 bolt and 1 nut, there can be 3 various situations: The bolt
is bigger or bolt and nut matches exactly or bolt is smaller. Devise an efficient
algorithm for matching n bolts with n nuts. What is the time complexity of the
algorithm?

6. a) What is an AVL tree? Write an algorithm for insertion of an element into AVL
tree.
b) describe Red-Black tree. elaborate the applications of Red-Black trees?

7. a) discuss the principle of optimality.
b) Using dynamic programming, Write an algorithm for ordering matrix
multiplication to minimize the number of scalar multiplications and
demonstrate your algorithm for the subsequent matrices.
A2,2 X B2,3 X C3,4 X D4,2 X E2,5

8. Write short notes on the subsequent
a) Tries
b) Collision resolution in hash tables

Earning:   Approval pending.