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

## 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) Translate the given infix expression in to equivalent postfix expression. **(3M)**

b) Explain linear and non linear data structures. **(3M)**

c) What is depth, height and degree of Binary tree. **(3M)**

d) What are the different ways to represent a graph?. **(2M)**

e) What is linked list? Explain types of linked list. **(3M)**

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

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

Q. 2) a) Write an algorithm for implementing queue using array. **(10M)**

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

Q. 3) Explain BSF and DSF algorithm with examples. **(10M)**

b) Traverse the following binary tree into preorder, inorder, postorder by giving its algorithm. **(10M)**

Q. 4) a) What is Doubly Linked List? Write an algorithm to implement following operations

on Doubly linked List.**(10M)**

1) Insertion(All cases) 2) Traversal (Forward and Backward)

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

Q. 5) a) What is Binary search tree. Construct Binary search tree for following elements. **(10M)**

** 13,3,4,12,14,10,5,1,8,2,7,9,11,6,18**

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

Q. 6) a)Write an algorithm for implementing stack 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)**

____________________________________________________________________________________________________________________________