# Data Structure Using C 2010-11

Note : Attempt all questions.

1.  Attempt any four parts :

(i)  Determine the formula to find the address location of an element in three dimensions array, suppose each element takes four bytes of space and elements are stored in column major order.

(ii) Write and explain the algorithm to find the 7th smallest element in an array.

(iii) Write a program using C to create an array of 10 elements. Take 10 elements in the array pass them to a function which prints the elements in reverse order.

(iv)  Write an algorithm to find the location of an element in the given linked list. Is the binary search will be suitable for this search ? Explain the reason.

(v) How a polynomial equation can be represented through link list ? Explain the method to add two given polynomial equations using link list.

(vi) Define the double link list. Write an algorithm to delete an element from the existing link list.

2.  Attempt any four parts :

(a) Write an algorithm to evaluate an expression given in postfix notation.

(b) Define the recursion. Write a recursive and non recursive program to calculate the factorial of the given number.

(c) What do you mean by priority queue ? Explain the types to maintain the priority queue.

(d) What is a circular queue ? Write a C function to insert an item in the circular queue.

(e) What is the Tower of Hanoi problem ? Explain the solutions of the Tower of Hanoi problem where the number of disks are 4 and number of pegs are 3.

(f)  Convert the following infix expression into postfix expression:

A*(B+D)/E – F*(G + H/K)

3.  Attempt any two parts of the following:

(a) (i) Determine in the terms of level 1 the maximum number of possible nodes at level 1 in the binary tree and also determine the maximum total number of possible nodes in a binary tree if the root node is at level 1.

(ii) How a node can be deleted from the binary search tree ? Explain the methods.

ECS302/VEQ-14854

2 (b) Write the function in C to insert and delete a node in an existing binary search tree.

(c) The preorder and inorder traversal of binary tree is given below, construct the tree—

preorder: FAEK.CDHGB

inorder: EACKFHDBG

4. Attempt any two parts of the following :

(a) Write and explain the breadth first search and depth first graph traversal algorithm. What are their complexities ?

(b) Define the spanning tree. Write the Prim’s algorithm to find the minimum cost spanning tree of the following:

(c) Describe the Dij ikstra’s algorithm for finding shortest path with help of suitable example.

5. Attempt any two parts of the following :

(a) Write the algorithm for bubble sort and insertion sort. Explain their best case and worst case complexities.

(b) Write the algorithm for the merge sort. Explain its complexities. Sort the following using merge sort method:

75,10,20,70, 80,90,100,40,30,50.

(c) Explain the following:

(i)    Heap Sort

(ii)  Radix Sort,   ECS302/ V EQ-14854    3   21125