# Mumbai University Previous year question papers

## III Sem IT Examination Dec 2012

## Data Structure and Algorithms

N.S.: (1) Question NO.1 is compulsory.

(2) Attempt any four questions out of remaining six questions.

1(a) Write an algorithm for Binary Search Method with example. 5

(b) Explain Asympotic notations and write the properties of asympotic notations. 5

(c) What are linear and non-linear data structures? 5

(d) What is a Vector? Explain any four functions. 5

2(a) Define Binary Tree. Write on algorithm to implement different tree traversal techniques. ‘.

(b) Write a program to create singly linked list and .display the list. 10

3(a) Write an algorithm for merge sort and comment on its complexity. 10

(b) Hash the following in a table of size 11. Use * any *two collision resolution technique. 10

99 67 41 0 17 2 98 20 94 27.

4(a) Write a program to implement queue using array. 10

(b) Explain Huffman Algorithm. Construct Huffman tree for “MAHARASHTRA” with its optimal code.

5(a)Write an algorithm to traverse a graph using – 10

(i) Breadth first search

(ii) Depth first seal’ch.

Write an ADT for stack and implement it using array. The ADT should support following operations :-

(i) Create

(ii) Push

(iii) POP

(iv) Display

6. (a) Write a program to implement Quick sort and show the steps to sort the following elements by Quick sort method :-

19 27 5 9′ 86 4-5 .

(b) Wh~t”is Doubly Linked List? Write an algorithm to implement following operations with DLL :-

(i) Insertion ‘(AII Cases)

(ii) Traverse (Forward and Backward)

7. Write short note on (any four) :-

(a) Pattern Matching

(b) Expression Tree

(c) Red and Black Trees

(d) Shortest Path Algorithm

(e) Priority and Circular Queue

(f) Selection Sort.