First question is compulsory.

Answer any FOUR from the remaining questions.

Answer ALL  parts of any question at one place.

1.   (a) Suppose you are performing a breath first search of a graph with n vertices, how large

can the queue get?

(b) what is complexity of dijk stra’s shortest distance algorithm?

(c) What is transitive closure?

(e) Define heap.

(f) what is the average case running time of heao sort method?

(g) suppose that you have a tree where the left  subtree  contains  3000 nodes and the right

subtree contains 100 nodes.for each of the different kinds of traversals,how many nodes

are processed before the root node?

2.   (a) Design a method for stimulating a queue using stacks.write set of routines for push,pop

to manipulate the stacks .

(b) Write a program for towers of hanio problem using concept of linked stacks.

3.   (a) Write procedures for addinga node and deleting a node from a balanced tree and leave the

resulting tree balanced.

(b) Write an algorithm to determine if a binary tree is

(i) Strictly binary

(ii) Complete

(iii) Almost complete.

4.    (a) Is every binary tree uniquely defined by its preorder and inorder traversals?How about by

its preorder and postorder traversals?Would it be uniquely defined by its inorder  and postorder traversals?if yes,write function,which constructs a doubly linked representation of the tree.

(b) Write functions to determine if a binary tree is

(i) strictly binary

(ii) complete and

(iii) Almost complete

5.  (a) Write procedures for adding a node and deleting node from a balanced tree and leave the

resulting tree balanced.

(b) Let x an y be strings represented as a singly linked lists.Write an algorithm to determine

the first character of x that does not occur in the string y.

6.  (a) Give a complete implementation of a priority queue.

(b) Write a C programfor a singly linked circular list,which reverses the direction of the links.

7.   (a) Define maximum spanning tree.also provide one example.

(b) Explain the Warshall’s algorithm with appropriate example.

IT 2.1 Previous PapersCSE,CSE Previous Papers,Data Structures Previous Papers
First question is compulsory. Answer any FOUR from the remaining questions. Answer ALL  parts of any question at one place.    1.   (a) Suppose you are performing a breath first search of a graph with n vertices, how large can the queue get? (b) what is complexity of dijk stra’s shortest distance algorithm? (c) What...