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

## 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 different types of queues in data structures. **(3M)**

b) How does binary search different from linear search. **(3M)**

c) Explain Doubly Linked List. **(3M)**

d) Define graph and list any three applications of graph. **(2M)**

e) Write postfix form of the following infix expression. **(3M)**

A+(B*(C-D)/E)

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

g)Write a note on recursion. **(3M)**

Q. 2) a) Explain Binary search tree. Construct Binary search tree for following elements. **(10M)**

45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

b) What is Singly Linked List? Write an algorithm to implement following operations

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

1) Insertion(All cases) 2)Deletion(All cases) 3) Traversal

** **

Q. 3) a) Write an algorithm for implementing stack using array. **(10M)**

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

Q. 4) a) Construct the binary tree for Inorder and Preorder traversal sequence given below.**(10M)**

Inorder: DBEAFCG

Preorder: ABDECFG

Write a function to traverse a tree in Postorder sequence.

b) Write an algorithm for quick sort 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) 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)**

Q. 6) a)Write short notes on (Any 4). **(20M)**

a) Asymptotic notations

b) Double Ended Queue (De-Queue)

c) Insertion Sort

d) DFS and BFS

e) Expression Tree.