Question Paper: Data Structures : Question Paper Jun 2014 - Computer Engineering (Semester 3) | Gujarat Technological University (GTU)
0

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)

ADD COMMENTlink
written 18 months ago by gravatar for Team Ques10 Team Ques10 ♦♦ 400
Please log in to add an answer.