0
Data Structures : Question Paper Dec 2016 - Computer Engineering (Semester 3) | Mumbai University (MU)

## Data Structures - Dec 2016

### Computer Engineering (Semester 3)

Total marks: 80
Total time: 3 Hours
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.

1(a) Explain linear and non-linear data structure with example
(5 marks) 00

1(b) Write ADT for stack. Give application of stack.
(5 marks) 1955

1(c) Explain practical applications of trees.
(5 marks) 2284

1(d) What is file? Explain various file handling operations in C.
(5 marks) 1944

2(a) Write a program in C to perfrom Quick sort. Show steps with example.
(10 marks) 2204

2(b) Explain Circular queue and Double ended queue with example.
(10 marks) 2183

3(a) Write a program to convert and expression fro infix to postfix using stack.
(10 marks) 2180

3(b) Write a function for BFS traversal of graph.
(10 marks) 2200

4(a) Write a program in C to create a singly linked list and perform the following operations:
i) Insert into list
ii) Search for data
iii) Delete from list
iv) Display data.
(10 marks) 1948

4(b) Insert the following elements in a AVJ search tree: 40, 23, 32, 84, 55, 88, 46, 71, 57
Explain different rotations used in AVL trees
(10 marks) 2196

5(a) Write a program to constract binary tree for the following pre-order and in-order traversal sequences. Pre-Orde: A B D G C E H I F
In-Order: D G B A H E IC F
(10 marks) 00

5(b) What is hashing ? What is mean by collision? Using modulo division method insert the following values in a hash table of size 10. Show how many collisions occurred. 99, 33, 23, 44, 56, 43, 19
(10 marks) 2210

5(b) Let A ={1, 2, 3, 4} and let R={(1, 2) (2, 3) (3, 4) (2, 1)} Find transitive closure of R by using Warshall's algorithm.
(6 marks) 00

5(c) Prove that the set A={0, 1, 2, 3, 4, 5} is a finite Abelian group unde addition modulo6.
(8 marks) 00

### Write short notes on any four of the following Q6.(1,2,3,4,5)

6(1) Huffman coding
(5 marks) 2189

6(2) Iteration VS Recursion
(5 marks) 2177

6(3) Various techniques of Graph representation
(5 marks) 2198

(5 marks) 2188

6(5) Heap Sort
(5 marks) 2206

6(a) Find the oridinary generating functions for the given sequences:
i) {1, 2, 3, 4, 5....}
ii) {2, 2, 2, 2....}
iii) {1, 1, 1, 1....}
(6 marks) 00

6(b) Define group, monoid, semigroup.
(6 marks) 00

6(c) Solve the following recurrence relation:$a_n-7a_{a-1}+10a_{a-2}=0$/ with initial condition a0=1,
a2=6
(8 marks) 00

0