# Data Structure using C 2006-07

Note : Attempt all questions.

1.  Attempt any four parts of the following :

(a)Define data, information, algorithm and data structure. Give the difference between linear and nonlinear data structures with example.

(b)Write a program to input a matrix NxN and to determine :

(i) the no. of elements in matrix

(ii) summation of diagonal elements

(iii) product of diagonal elements.

(c) Define time complexity. Explain Big oh (O) notation.

(d) Write an algorithm for deleting duplicate numbers from a linear array.

(e) Write a program which sort a list of strings.

(1) Write an algorithm for binary search. What are its limitations?

2. Attempt any four parts :

(a) Write an algorithm for matching different parenthesis such as {, [, ( in an algebraic expression.

(b) Given the following arithmetic expression in infix notation as 12/(7-3)+2*(3+8)-7 Translate this expression into postfix notation and then evaluate it.

(c) Write functions to implement recursing versions of pre-order, in-order and post-order tranversals of a binary tree.

(d) Write an algorithm which reverses the order of elements on stack using one additional stack and some additional variables.

(e) Write algorithm for insertion and deletion on priority queues.

(1) Write a program to construct and delete elements in a circular queue using link list.

3.  Attempt any four parts :

(a) Write a short note on Garbage Collection and Compaction.

(b) Write a program to delete a node in a doubly linked list.

(c) Write an algorithm for a single linked circular list which reverses the direction of the links.

(d) Compare the dynamic implementation of a linear linked list.

(e) Write a program to add two polynomials in single variables.

(1) Write a procedure to merge two singly linked list whose elements are sorted in ascending order to produce a single singly linked list sorted in ascending order.

4 Attempt any four parts :

(a) Write a recursive program to compile height of a binary tree.

(b) Draw the binary search tree that results from inserting into an initially empty tree records with keys given below in order ? E, A, S, Y, Q, U, E, S, T, I, O, N and then deleting the Q.

(c)What is a threaded binary tree ? Explain with the help of example. What are its advantages?

(d)Find the incidence matrix of the graph.

(e)Draw all (non similar) trees with exactly six nodes.

(1) Write an algorithm which counts the number of connected components in a graph.

5.  Attempt any four parts :

 Insertion and Deletion in B-Trees Spanning Trees Huffman’s Algorithm Merge Sort Comparison of Indexing and Hashing Tower of Hanoi Problem