Question Paper: Data Structure & Algorithm Analysis : Question Paper May 2015 - Information Technology (Semester 3) | Mumbai University (MU)
0

Data Structure & Algorithm Analysis - May 2015

Information Technology (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.


1 (a) Explain Asymptotic Notations. (3 marks)


1 (b) What is linked list? State the advantages of linked list. (3 marks)


1 (c) Define Double Ended queue. List the variants of Double ended queue. (3 marks)


1 (d) Define Graph. List its types with example. (3 marks)


1 (e) State the properties of Red Black Tree. (3 marks)


1 (f) Explain with example.
i) Degree of tree
ii) Height of tree
(3 marks)


1 (g) Distinguish between linear data structure and non linear data structure. (2 marks)


2 (a) Write a program to implement STACK ADT using array. (10 marks)


2 (b) Write an algorithm to implement Quick sort. Explain with an example. (10 marks)


3 (a) Define binary search tree. Write algorithm to implement insertion ad deletion operation. (10 marks)


3 (b) Give an INFIX expression and write a program to convert in POSTFIX expression. (10 marks)


4 (a) Write a program to sort an array using insertion sort algorithm. (10 marks)


4 (b) What is AVL tree? Construct AVL tree using following sequence of data:
16, 27, 9, 11, 36, 54, 81, 63, 72
(10 marks)


5 (a) Find the minimum spanning tree for the given graph using Kruksal's algorithm. Also find its cost with all intermediate steps..
:IMAGE-
(10 marks)


5 (b) Write functions to implement insert () and traverse () of singly linked list. (10 marks)


6 (a) Write algorithm to traverse a graph using:
i) Breadth First Search
ii) Depth First Search.
(10 marks)


6 (b) What is priority queue? Give implementation of it. (10 marks)

Please log in to add an answer.