## Data Structures - Jun 2014

### Computer Engineering (Semester 3)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.

### Answer the following

**1 (a) i)** Obtain the expression tree from the following post fix representation ab+cde+**.**(2 marks)
** 1 (a) ii) Define complete binary tree and a full binary tree.(2 marks)
1 (a) iii) List the features of a good hash function.(2 marks)
1 (a) iv) List the use of stack, queue and linklists.(2 marks)
1 (a) v) What are priority queues? Explain its uses.(2 marks)
1 (b) Evaluate the following postfix expression using stack*GH+(where A=2,B=4,C=6,D=3,G=8,H=7).(4 marks)

AB+CD/

**2 (a)**Write an algorithm to convert infix to postfix expression and explain it with example.(7 marks)

**2 (b)**Translate the following string into polish notation and trace the content of stack A-(B/C+(D%E

*F)/G)*H.(7 marks)

**2 (c)**i) Consider a dequeue given below which has LEFT=1,RIGHT=5

_ A B C D E _ _ _ _

Now perform the following operation on the dequeue

1.Add F on the left.

2. Add G on the right

3. Add H on the right.

4. Delete two alphabets from left

5. Add I on the right

ii) Differentiate peep() and pop() functions.(7 marks)

**3 (a)**Write a program in any programming language to concatenate two doubly linked lists.(7 marks)

**3 (b)**Write an algorithm to insert a node in an oredered linked list.(7 marks)

**3 (c)**Give the preorder and Inorder traversal of the tree given in fig 1. (7 marks)

**3 (d)**Given the following traversals create a binary three from that. Also give the postorder traversal for the same.

preorder={7,10,4,3,1,2,8,11}

inorder={4,10,3,1,7,11,8,2}.(7 marks)

**4 (a)**Explain DFS and BFS with example .(7 marks)

**4 (b)**Construct a binary search tree for the following sequence. Also do the inorder and postorder traversal for the same.

45,56,39,12,34,78,54,67,10,32,89,81.(7 marks)

**4 (c)**What is spanning tree? Find the minimum spanning tree for the graph shown in fig (7 marks)

**4 (d)**Write short note on (i) Height Balanced Tree. ii) Indexed-sequential Files.(7 marks)

**5 (a)**What do you mean by Hashing? Explain any FOUR hashing techniques.(7 marks)

**5 (b)**Define the following terms

i) Node ii) Sibling iii) Path iv) Indegree & outdegree of a vertex v) Connected graph.(7 marks)

**5 (c)**Compare and contrast Prim's and Kruskal's algorithm with the help of an example.(7 marks)

**5 (d)**Explain AVL tree with the help of an example also show insertion and deletion with the help of an example.(7 marks)