# UPTU Previous Year Question Papers

# B tech 3rd Semester

# Data Structure Using C 2008-09

**1. Attempt any two parts of the following :**

(a) (i) Define the term Data Structure. List some

linear and non-linear data structures stating the application area where they will be used.

(ii) State the merits and demerits of static and dynamic memory allocation techniques.

(b) (i) Define tail recursion by giving suitable

example.

(ii) How two dimensional arrays are

represented in memory? Also obtain the formula for calculating the address of any element stored in the array, in case of column major order. (Make necessary assumptions yourself).

(c) Write an algorithm to convert a valid arithmetic infix expression into its equivalent postfix expression. Trace your algorithm for A-B/C+D*E+F

**2. Attempt any two parts of the following :**

(a) Write an algorithm to insert and delete a node from doubly linked list. Illustrate with an example. Use your algorithm to develop functions in C.

(b) Explain circular queue and priority queue data structure in detail.

(c) (i) How can we represent a polynomial in a

linked list? Write an algorithm to add two polynomials represented by linked lists.

(ii) Explain the term Garbage collection and compaction.

**3. Attempt any four parts of the following :**

(a) Write an algorithm to insert a node in a threaded binary tree.

(b) Discuss how one can handle overflow in hashing.

(c) Define Tree. How a tree can be stored in memory? Expain with an example.

(d) Write an algorithm to determine whether a binary tree is complete or not.

(e) If the inorder traversal of a binary tree is B,1,D,A,C,QE,H,F and its postorder traversal is I,D,B,QC,H,F,E,A, determine the binary tree.

(f) Write a program in C for binary search. What is the worst case time complexity of binary search?

**4. Attempt any four parts of the following :**

(a) How the choice of pivot element affect the running time of quick sort algorithm? – Explain.

(b) Write Heapsort algorithm. Analyze the running time of your algorithm.

(c) Use quick sort algorithm to sort

15,22,30,10,15,64,1,3,9,#2. Is it a stable sorting algorithm? – Justify.

(d) Obtain the minimum number of entries that can be made in a B-tree of order m and level /.

(e) Discuss the different cases of rotations in AVL trees.

(f) Write a function in C to insert an element into a binary search tree.

** 5. Attempt any four parts of the following :**

(a) Use Kruskal’s algorithm to determine the minimum spanning tree of the graph given below:

(b) Explain the different techniques used to represent a graph in computer memory.

(c) How are deletion of records handled in an indexed sequential file?

(d) Write a suitable algorithm to find the components of a graph.

(e) Discuss the factors involved in selecting a particular file organization.

(f) Write short notes on any two :

(i) Direct file organization

(ii) Prims algorithm

(iii) Indexing.

I can’t find other year papers.