# RGPV Exams Questions Papers 3rd SEM Dec 2007 Data Structure

RGTU B.E. (Third semester) EXAMINATION, Nov-Dec. 2007

(Common for EC/EE/EX Engg – DATA STRUCTURE – CS/EE/IP-304)

Note. Attempt any five questions. All question carry equal marks. Make suitable assumption

necessary.

1. (a) Write the properties of AVL tree and give two example of AVL tree.

(b) A binary tree T has 9 nodes. The in order and preorder traversals of T yield the following sequence

of nodes:

Inorder : E A C K F H D B G

Preorder : F A E K C D H G B

Draw the tree

2. (a) Consider the following arithmetic expression p, written in postfix notation

P: 12, 7, 3, – , 1, 2, 1, 5, +, *, +

(i) Translate P by inspection and hand; into its equivalent infix expression.

(ii) Evaluate infix expression.

(b) Differentiate between a tree and a graph .Is it possible to connect a graph into tree? If yes, how?

3. (a) What do you mean by hashing and what is hash function ? Explain with example.

(b) Sort the following integers using insertion sort:

25, 7, 48, 37, 12, 92, 86, 33

4 (a) It is possible to keep two stacks in a single array, If one grows from position —– of the array and

the other grows from the last position . Write a procedure PUSH (axis) that pushes element x onto

stacks where s is one or the other of these two stacks. Include all necessary error checks in your

precedence.

(b) Enlist different operation which is normally performed on any linear array. Write the algorithms

for any two such functions.

5. (a) Explain memory allocation and garbage collection .

(b) Explain stack and write an algorithms for PUSH and POP operation.

6. (a) write a c procedure which implement circular queue.

(b) Write depth first search algorithms. Also draw linked representation of the following graph:

7. (a) Write a procedure which removes the first element of a list and adds it to the end of the list with

out changing any data field. Also write a procedure which deletes the k^{th }element from a link list.

(b) Write a program in c which does multiplication of two matrices.

8. (a) Write sort notes on any four of the following :

(i) Abstract data type

(ii) Triangular array

(iii) Threaded binary tree

(iv) Priority queue

(v) Types of data structure