Visvesvaraya Technological University (VTU) 2009 M.Tech Computer Science Data structures - Question Paper

NMAM INSTITUTE OF TECHNOLOGY, NITTE
(An Autonomous College under VTU, Belgaum )
First Semester M.Tech (Credit System) Degree exams
Dec 2009- Jan 2010
ADVANCED DATA STRUCTURES AND ALGORITHM Time: three Hrs. Max. Marks: 100
Note: ans any 5 full ques.
1. a. describe balanced binary search tree. Construct binary search tree for the data
8, 10 ,3,2,1,5,4,6, and 11. Insert an element seven into binary search tree and
balance the tree using AVL rotation. -8M-
b. What is an Ascending Priority Queue? discuss how to implement this using
Binary Heap? discuss the insertion and deletion operation performed on
binary heap, with an example. -8M-
c. provide an accessing formula to obtain the location of an element in 3D array.
-4M-
2 a. Write recursive function to obtain nth Fibonacci number. Show all recursive
stacks to obtain fourth Fibonacci number. -8M-
b. obtain the prefix and postfix notation for the infix expression,
((A+B)*C-(D-E))$(F+G). Evaluate the found postfix expression using
Stack, when A=1,B=2,C=1,D=2,E=1,F=1,G=2. -12M-
3 a. describe Strongly connected graph and strong components. obtain all Strong
components for the subsequent graph using Depth 1st Search method.
-8M-










b. obtain the critical path for the subsequent set of activities. List Earliest , recent time and total float for every activity.

Job 1-2 1-3 2-3 2-5 3-4 3-6 4-5 4-6 5-6 6-7
Duration 15 15 3 5 8 12 1 14 3 14
-12M-
4. a. describe Spanning tree. obtain the minimum cost spanning tree for the subsequent
graph using Kruskals method. -7M-









b. describe B tree. Show the B tree after inserting subsequent elements 1 by 1 in
order. presume that the order of the tree is 3.
10,20,30,40,50,60,70,80,90,100,110 -8M-
c. describe Biconnected graph. provide an example. -5M-

5. a. Why Asymptotic notations are used? discuss the various Asymptotic notations
used, in detail. -7M-
b. discuss Separate chaining method used to resolve hash clashes. -7M-
c. describe binomial tree. Construct binomial heap containing 13 elements. -6M-

6. a. discuss the Strassen’s matrix multiplication method with an example. -7M-
b.What is an optimal binary search tree? discuss with an algorithm to obtain optimal
binary search tree. -7M-
c.Explain how to solve n-Queens issue using Backtracking Technique. -6M-

7. a. Solve the all pairs shortest path issue for the digraph with the weight matrix,


0 2 8 1 8
6 0 3 2 8
8 8 0 4 8
8 8 2 0 3
3 8 8 8 0
-12M-

b. Consider the subsequent Job sequencing with deadlines issue. Let n=7,
(p1, p2…p7)=(3,5,20,18,1,6,30) and (d1,d2…d7)==(1,3,4,3,2,1,2). obtain the
optimal solution using Greedy technique. -08M-

8. a. discuss Heapsort algorithm in detail. explain it’s time complexity. -08M-
b. Write a note on P and NP issue. -06M-
c. explain the time complexity of Quick sort algorithm. -06M-

Earning:   Approval pending.