DATA STRUCTURES (DS), B.E. Computer Science (CS), Semester 3, December 2011.

DATA STRUCTURES (DS), B.E. Computer Science (CS),

Semester 3, December 2011.

(3 Hours)

[Total Mark: 100]

N. B.: (1) Question no 1 is compulsory.

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

(3) Assumptions made should be clearly stated.

(4) Figures to the right indicate marks for each question.

(5) Assume suitable data wherever required bust justify the same.

1. (a) What is recursion? State its advantages and disadvantages. --- (5 Marks)

(b) What is AVL tree? Explain with example. --- (5 Marks)

(c) Define: --- (5 Marks)

1. Abstract Data Type
2. Binary Tree
3. Graph.

(d) Construct Huffman code for “C++ JAVA”. --- (5 Marks)

2. (a) Explain different types of “Tree Traversal” Techniques. Explain each with suitable example. --- (10 Marks)

(b) Explain different ways to represent a graph. Give example. --- (10 Marks)

3. (a) Write a program to implement queue using array. --- (10 Marks)

(b) Explain any two application of stack using program. --- (10 Marks)

4. (a) Explain the working of merge sort. And sort the following elements. --- (10 Marks)

50,

10,

20,

40,

5,

60,

35

(b) Explain circular and priority queue. --- (10 Marks)

5. (a) Write a program to create a doubly linked list and perform the following operations : --- (9 Marks)

1. Insert into the list
2. Delete from the list
3. Search for a data

(b) Write a program in Java that read as text file and counts occurrences of a particular word. --- (11 Marks)

6. (a) What is Hashing? Hash the following in a table of size 11. Use any two collision resolution techniques. --- (10 Marks)

20,

5,

10,

11,

22,

33,

40,

50,

30,

51,

31

(b) Construct binary tree for in order and post order traversal sequence given below. --- (10 Marks)

Inorder	:	“INFORMATION”
Postorder	:	“INOFMAINOTR”

7. Write short notes on any four of the following: - --- (20 Marks)

(a) Comparison of sorting Algorithm

(b) B+ trees

(c) Binary Search

(d) Prefix and Postfix forms of expressions.

(e) Asymptotic notation

(f) Tower of Hannoi.