# Data Structure and Analysis-Engineering-Mumbai University-Dec2018

## MUMBAI UNIVERSITY

## Subject: Data Structure and Analysis

## Semester: 3

**[Total Time: 3 Hours]**

**[Total Marks: 80 Marks]**

**N.B.: 1) Q.1 is compulsory**

** 2) Attempt any three questions out of the remaining five**

** 3) Assume suitable data if required.**

____________________________________________________________________________________________________________________________

Q. 1) (a)Explain linear and non linear data structures. **(2M)**

b) Define a graph. List the types of graph with examples. **(3M)**

c) What is expression tree? Give Example. **(3M)**

d) Define asymptotic notations with an example. **(3M)**

e)Define Double Ended queue. List the variants of double ended queue. **(3M)**

f) What is Recursion? State its advantages and disadvantages. **(3M)**

g)What is linked list? State the advantages of linked list. **(3M)**

Q. 2) a) Write an algorithm for merge sort and comment on its complexity. **(10M)**

b)Write an algorithm for implementing stack using array. **(10M)**

Q. 3) Define Binary Tree. Find in-order, pre-order and post-order of following binary tree. **(10M)**

b) Write an algorithm for implementing Queue using array.**(10M)**

Q. 4) a) Explain Quick sort using an example. Write algorithm for it and comment on its complexity.**(10M)**

b) What is collision? What are the methods to resolve collision? Explain Linear probing with an example. **(10M)**

Q. 5) a) Write an algorithm for converting infix to postfix expression.**(10M)**

b) Define Binary Search Tree. Write an algorithm for following operations on binary search tree. **(10M)**

1)Insertion 2)Deletion

Q. 6)a)Write an algorithm for following operations on Doubly linked List **(10M)**

1)Insertion 2)Deletion 3)Traversal

b) What is Minimum Spanning Tree? Draw the MST using kruskal’s and prim’s algorithm and find out the cost with all intermediate steps. **(10M)**