Data Structure (2130702)

BE | Semester 3 
  Summer - 2014|06/04/2014
Total Marks 70

Q1 (a) Answer the following

  (b) Evaluate the following postfix expression using stack

Q2 (a) Write an algorithm to convert infix to postfix expression and explain it with example

  (b) Translate the following string into polish notation and trace the content of stack

OR

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

Q3 (a) Write a program in any programming language to concatenate two doubly linked lists.

  (b) Write an algorithm to insert a node in an ordered linked list

OR

Q3 (a) Give the preorder and Inorder traversal of the tree given in fig 1. figure:1 Q3A

  (b) Given the following traversals create a binary tree from that. Also give the postorder traversal for the same.

Q4 (a) Explain DFS and BFS with example

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

OR

Q4 (a) What is a spanning tree? Find the minimum spanning tree for the graph shown in fig 2. figure:2 Q4A

  (b) Write short notes on (i) Height Balanced Tree. (ii) Indexed-Sequential Files

Q5 (a) What do you mean by Hashing? Explain any FOUR hashing techniques

  (b) Define the following terms

OR

Q5 (a) Compare and contrast Prim’s and Kruskal’s algorithm with the help of an example

  (b) Explain AVL tree with the help of an example also show insertion and deletion with the help of an example.