DATA STRUCTURES (DS), B.E. Computer Science (CS), Semester 3, May 2010.

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

Semester 3, May 2010.

Con.3670-10

AN-2497

(3 Hours)

[Total Mark: 100]

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

(2) Attempt any four questions from Q. Nos 2 to 7.

(3) Use diagram wherever necessary.

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

1. (a) Write a program in Java to implement Binary search. --- (10 marks)
(b) What is Recursion & write a program in Java to implement “Tower of Hanoi.” ---- (10 Marks)

2. (a) Write a Java program to implement circular queue using linked list. --- (10 Marks)
(b) Construct the binary tree for the in order and post order traversal sequences given below. ---- (10 Marks)

In Order	:	“INFORMATION”
Post Order	:	“INOFMAINOTR”

3. (a) Discuss Threaded binary tree in detail. --- (10 Marks)
(b) Write the program in Java to perform quick sort. Show the steps with example. --- (10 Marks)

4. (a) Explain Huffman Coding with example. Write a Java program to create the binary tree using Huffman Coding for the given characters and their frequencies. Print the Huffman Code for each character. --- (14 marks)
(b) Compare Interation and Recursion. --- (6 Marks)

5. (a) Write a program in Java to sort given n integer number using heap sort. --- (10 Marks)
(b) Explain BFS algorithm, explain it by example. --- (10 Marks)

6. (a) Write short note on B- Trees and B⁺ - Trees. --- (10 marks)
(b) Hash the following in a table of size 11. Use any two collision resolution techniques: - ---(10 Marks)

23,

0,

52,

61,

78,

33,

100,

8,

90,

10,

14

7. (a) Show with example how graphs are represented in Computer Memory. --- (6 Marks)
(b) Discuss practical application of trees. --- (4 Marks)
(c) Write short notes on: - --- (10 Marks)
I. AVL Tree

II. Array Representation of Linked List.

Also see Data structures question papers for December 2010