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

## 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) What are the applications of Stack? **(3M)**

b) What are the advantages of circular linked list?**(3M)**

c) Differentiate between space complexity and time complexity. **(3M)**

d) Explain linear and nonlinear data structures. **(2M)**

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

f) Explain asymptotic notations. **(3M)**

g) What is recursion? State its advantages and disadvantages. **(3M)**

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

b) Explain BFS and DFS algorithm with examples. **(10M)**

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

1)Insertion 2)Deletion 3)Traversal

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

Q. 4) a) Explain the properties of Binary search tree. Construct Binary search tree for following elements. **(10M)**

47, 12, 75, 88, 90, 73, 57, 1, 85, 50, 62

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

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

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

Q. 6) a)Write an algorithm for implementing Queue using array. **(10M)**

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