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

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

Semester 3, May 2012.

Con.3889-12

GN-5300

(3 Hours)

[Total Mark: 100]

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

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

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

1. (a) What is Recursion? Write a program to calculate factorial of a number using recursion. --- (10 Marks)

(b) Explain linear and non – linear data structure with example. ---- (5 Marks)

(c) Write ADT for stack. Give application of Stack. --- (5 Marks)

2. (a) Write a program to implement Insertion sort using Java. Show passes of Insertion sort for following input data: --- (10 Marks)

5,

3,

2,

1,

4

(b) Give different searching techniques. Write a program to implement Binary Search. --- (10 Marks)

3. (a) Write a program in Java to copy content of a file to another file. --- (10 Marks)

(b) Write a program in Java to sort n integer numbers using Quicksort. Show the steps to sort the given numbers: --- (10 Marks)

25,

10,

7,

30,

15,

2,

96,

14

4. (a) Explain different representation of graph. State advantages and disadvantages of each representation. --- (10 Marks)

(b) What is use of Huffman Encoding? Apply and give Huffman code for each symbol in sentence “DATA STRUCTURE”. --- (10 Marks)

5. (a) Write a Java program to implement circular queue using array. --- (10 Marks)

(b) Write a Java program to create a binary search tree. Show BST for following input: ---- (10 Marks)

10,

5,

4,

12,

15,

11,

3

6. (a) What is the use of Hashing? Show hash table entries for the given dataset using Linear probing and quadratic probing: --- (10 Marks)

12,

45,

67,

88,

27,

78,

20,

62,

36,

55

(b) What are advantages of Linked List over array? Write a program in Java to implement stack using linked list. --- (10 Marks)

7. Write a sort note on any two : --- (20 Marks)

a) Tree traversal algorithm.

b) Graph traversal algorithm

c) Priority queue.