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

0

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

**1(b)**Write ADT for stack. Give application of stack.

**1(c)**Explain practical applications of trees.

**1(d)**What is file? Explain various file handling operations in C.

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

**2(b)**Explain Circular queue and Double ended queue with example.

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

**3(b)**Write a function for BFS traversal of graph.

**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.

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

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

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

**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.

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

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

**6(1)**Huffman coding

**6(2)**Iteration VS Recursion

**6(3)**Various techniques of Graph representation

**6(4)**Threaded binary tree

**6(5)**Heap Sort

**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(b)**Define group, monoid, semigroup.

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

_{0}=1,

a

_{2}=6