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

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

Semester 3, May 2013.

Con.6456-13

GS-6315

(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) Assume suitable data wherever required but justify.

(4) Illustrate answers with neat sketches whenever required.

1. (a) Write a program in Java to implement circular Queue using array. --- (10 Marks)

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

(c) Explain practical applications of trees. --- (5 Marks)

2. (a) Write a program in java to copy content of a file to another file using command line argument. --- (10 Marks)

(b) What are the advantages of linked list over array? Write a program in java to implement stack using linked list. --- (10 marks)

3. (a) Write a program to implement insertion sort using Java. Show passes of insertion sort for the following input. --- (10 Marks)

15,

23,

22,

11,

44

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

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

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

10,

05,

14,

22,

17,

01,

08

5. (a) Explain the method of Huffman Encoding. Apply Huffman encoding method for the sentence “MALAYALAM”. Give Huffman code for each symbol. --- (10 Marks)

(b) Hash the following in a table of size. 11 use any two collision resolution techniques. --- (10 Marks)

23,

55,

0,

71,

67,

23,

100,

18,

10,

90,

44

6. (a) Write ADT for stack. Give applications of stack. --- (10 Marks)

(b) Explain Priority Queue. --- (5 Marks)

(c) Write a program in java to create a linked list and perform the following operations: --- (5 Marks)

(i) Insert into list

(ii) Search for data

(iii) Delete from list

(iv) Display the list

7. Write short notes on any two:- --- (20 Marks)

(a) Tree Traversal Algorithms

(b) Merge sort with example

(c) AVL tree and multiway tree.