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 :-
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.