Data Structure & Algorithms (Information Technology Sem III) JUNE 2010

Data Structure & Algorithms Information Technology   Sem III
June 2010	AN-2569
(3 Hours)	[Total Mrks : 100]
N.B: 1)  Question No. 1 is compulsory
2) Attempt any four questions from remaining SIX questions.
1. a) Write a program to implement a STACK ADT using Linked list.	10
b) Explin Huffman coding and construct huffman code for the following	10
"JAVA DATA STRUCTURES"
2. a) Construct the binary tree for the inorderd and post traversal sequence given below  `                 In oreder : "INFORMATION                   Post Order: "INOFMAINOTR"	10
b) Write and explain Radix sort algorithm with suitable example.	10
3. a) Write an algorithm for merge sort and comment on its complexity.	10
b) Calculate and draw the minimum cost spanning tree using Kruskal's algoritham for the          following graph.	10
4.  a)  Explain how interface and packages are created and accessed with their syntax.	10
b)  Write any pattern Matching Algoritham and explain it with suitable example.	10
5.  a) Write a program to implement queue using array.	10
b)  Write a program to search an element in an array using binary search technique.	10
6.  a)  Write algorithm for heap sort and explain Ascending heap with suitable example.	10
b)  Hash the following in a table of size 11. Use any two collision resolution technique              99     67     41     0     17     2     98     20     94     27	10
7.  a)  Write short note on any four of the following:-	20
i)  AVL Trees           ii)  Red and Black Trees          iii)  Asymptotic Notation          iv)  Recursion          v)  Graph traversal technique         vi)  Abstract data type.

Also see Data structure & algorithms question papers for May 2009