B.E. (Fifth semester) EXAMINATION, Nov-Dec. 2007
(Common for EC/EE/EX Engg.)
Note. Attempt any five questions. All question carry equal marks. Make suitable assumption
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
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
(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 kth 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