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

## 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) Define stack. Give its applications? **(2M)**

b) What are the different linear and non-linear data structures?. **(3M)**

c) What is Linked list? Explain its types. **(3M)**

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

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

f) Define minimum spanning tree. List the techniques to compute minimum spanning tree. **(3M)**

g) Define expression tree with example. **(3M)**

Q. 2) a) Write an algorithm to create doubly linked list and display the list. **(10M)**

b)Write an algorithm to implement Queue using array. **(10M)**

Q. 3) Write an algorithm to convert INFIX to POSTFIX expression? **(10M)**

b) Write the algorithm for merge sort. Comment on its complexity?**(10M)**

Q. 4) a) Write an algorithm to implement Priority queue?.**(10M)**

b) Explain BFS and DSF algorithm with examples? **(10M)**

Q. 5) a) Define Binary search tree. Explain the different operations on a binary search tree with examples? **(10M)**

b) What is minimum spanning tree? Explain kruskal’s Algorithm with an example. **(10M)**

Q. 6)Short notes on (any 4) **(20M)**

a) Selection Sort

b) Prim’s Algorithm

c) Binary Search

d) Hashing techniques

e) Dijkstra’s Algorithm