JNTU, B.Tech I Semester DATA STRUCTURES THROUGH C, November 2008

( Mechanical Engineering, Mechatronics, Metallurgy &Material Technology, Production Engineering, Aeronautical Engineering and Automobile Engineering)

SET-2

1. Write a C program to find the average in a given array of elements and also find min and max elements of that array.

2. Write an algorithm to do the following in a doubly linked linear list.

(a) Left-most insertion in a doubly linked linear list.

(b) Insertion at the right most location in a doubly linked linear list.

3. (a) Derive a method to convert a postfix expression into its prefix form

(b) Consider the following arithmetic expression in postfix notation: 7 5 2 + * 4

1 5 – / –

i. Find the equivalent prefix form of the above .

ii. Obtain the computed value of the expression from its postfix notation

4. (a) Mention and explain various types of queues and give an example for each

(b) Compare various types of queues.

5. (a) Construct a Binary tree for the following three traversals

Preorder: ABCEIFJDGHKL

Inorder : EICFJBGDKHLA

Postorder : IEJFCGKLHDBA

(b) How breadth first search differs from depth first search. Give an example.

6. (a) What are the advantages of adjacency matrix representation of graphs.

(b) Define spanning tree of an undirected graph.

7. (a) Distinguish between linear and binary search methods.

(b) Write an algorithm for non-recursive binary search method.

8. Write an algorithm for heap sort and write a C program for implementing the same.