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

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

Semester 3, December 2012.

Con.7375-12

KR-3308

(3 Hours)

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.

1. (a) Compare Iteration and Recursion. --- (5 Marks)

(b) Explain different types of data structures with example. --- (5 Marks)

(c) Write a program in Java to implement Binary search on sorted set of integers. --- (10 Marks)

2. (a) Write a program to implement “copy” command for copying bytes from one file to another file using file I/o commands. Program should make use of command line argument. --- (10 Marks)

(b) Write a program in Java to sort given n integer number using heap sort. --- (10 Marks)

3. (a) Write an ADT for rational numbers addition and multiplication. Addition of two rational numbers a/b and c/d is (ad + cb)/ba and multiplication of two rational numbers a/b and c/d is ac/bd. --- (10 Marks)

(b) Write a program in Java to find nth term of Fibbonacci sequence using recursion. --- (10 Marks)

4. (a) Write a Non-Recursive function for inorder traversal. --- (10 Marks)

(b) Write a program in Java to create a singly linked list and perform the following operations: --- (10 Marks)
(i) Insert into list
(ii) Search for data
(iii) Delete from list
(iv) Display data.

5. (a) Explain Circular queue and Double ended queue with example. ---(10 Marks)

(b) Write a program in Java to implement DFS traversal of a graph using adjacency matrix. --- (10 Marks)

6. (a) Write a program to convert an expression from infix to postfix. Use STACKADT Array implimentation of the above program. --- (10 Marks)

(b) Write a program to construct binary tree for the following pre-order and in-order traversal sequences. --- (10 Marks)

Pre-Order	:	A B D G CE H I F
In-Order	:	D G B A H E I C F

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

(a) Threaded binary tree

(b) Huffman coding

(c) Applications of stocks

(d) Indexed sequential search

(e) Array implementation of linked list.