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
AB+CD/GH+(where A=2,B=4,C=6,D=3,G=8,H=7).(4 marks) 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%EF)/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)