# Data Structure Using C 2011-12

Note Attempt all questions.

1.  Attempt any four parts of the following:

(a) Write an interactive program in C which transpose the given matrix.

(b) Explain the memory representation of a Lower triangular matrix. Determine the address formula of any element ai j, 1 ,< i < n in the lower triangular matrix if the elements are stored in row major order.

(c) Write an algorithm to count the number of nodes between given two nodes in a Linked List.

(d) Write a C function for inserting a new node at the end of a doubly linked list.

(e) What is asymtotic notation ? Explain the big ‘O’ notation.

(f)  Write a program in C which reverse the order elements in a given string and check whether the string is palindrome or not.

2.  Attempt any two parts of the following :

(a) (i) Why circular queues are better than simple queue ?

Write an algorithm to insert and delete an item from the circular link list.

(ii) What do you mean by priority queues ? Describe its applications.

(b) (i) What is recusion ? Explain.

(ii) Convert following expression into infix notations: a + (b + c * d + e) + f/g

(c) (i) Write an algorithm that reverse all the elements in a queue.

(ii) Write an algorithm to insert an item X just after the i* element in a queue.

3.  Attempt any two parts of the following :

(a) Define binary tree. Explain the Linear sequential representation of binary tree. Write the advantages and disadvantages of sequential representation of binary trees.

(b) (i) Determine the height of a complete binary tree with n number of nodes.

(ii) For any non empty binary tree T, if no is the number of leaf nodes (degree= 0) and n2 is the number of internal nodes (degree = 2), then prove that: no = n2 + 1 ECS302/KIH-26377    2

(c) Write algorithms for in order and postorder traversal of a binary tree.

4.  Attempt any two parts of the following :

(a) What is a graph ? Define simple graph, directed graph, cyclic and acyclic graphs. Explain the linked representation of graphs.

(b) (i) What is path matrix ? How path matrix can be determined ? Explain the method.

(ii)  Write BFS graph traversal algorithm and explain.

(c) (i) Write Kruskal’s algorithm to find minimum spanning tree!

(ii) Find the minimum spanning tree using Prim’s algorithm for the given graph :

5.  Attempt any two parts of the following:

(a)  What is AVL tree ? Explain the balancing methods of AVL , trees with an example.

(b) Explain quick sort method and determine its complexities.

(c) Define Hash function. Explain Collision resolution strategies.