GTU Computer Engineering (Semester 3)
Data Structures
June 2014
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary


Answer the following
1 (a) i) Obtain the expression tree from the following post fix representation ab+cde+**.
2 M
1 (a) ii) Define complete binary tree and a full binary tree.
2 M
1 (a) iii) List the features of a good hash function.
2 M
1 (a) iv) List the use of stack, queue and linklists.
2 M
1 (a) v) What are priority queues? Explain its uses.
2 M
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 M

2 (a) Write an algorithm to convert infix to postfix expression and explain it with example.
7 M
2 (b) Translate the following string into polish notation and trace the content of stack A-(B/C+(D%E*F)/G)*H.
7 M
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 M

3 (a) Write a program in any programming language to concatenate two doubly linked lists.
7 M
3 (b) Write an algorithm to insert a node in an oredered linked list.
7 M
3 (c) Give the preorder and Inorder traversal of the tree given in fig 1.

7 M
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 M

4 (a) Explain DFS and BFS with example .
7 M
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 M
4 (c) What is spanning tree? Find the minimum spanning tree for the graph shown in fig

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

5 (a) What do you mean by Hashing? Explain any FOUR hashing techniques.
7 M
5 (b) Define the following terms
i) Node ii) Sibling iii) Path iv) Indegree & outdegree of a vertex v) Connected graph.
7 M
5 (c) Compare and contrast Prim's and Kruskal's algorithm with the help of an example.
7 M
5 (d) Explain AVL tree with the help of an example also show insertion and deletion with the help of an example.
7 M



More question papers from Data Structures
SPONSORED ADVERTISEMENTS