## Data Structures - Dec 2012

### Computer Engineering (Semester 3)

TOTAL MARKS: 80

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Assume data if required.

(4) Figures to the right indicate full marks.
**1(a)** Compare Iteration and Recursion(5 marks)
**1(b)** Explain different types of data structures with example(5 marks)
**1(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)
**2(b)** Write a program in Java to sort given n integer numbers 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)
**3(b)** Write a program in Java to find the n^{th} term of Fibonacci sequence using recursion(10 marks)
**4(a)** Write a Non-Recursive function for inorder traversal(10 marks)
**4(b)** Write a program in Java to create a singly linked list and perform the following operations

1. Insert into list

2.Search for data

3. Delete from list

4. Display data(10 marks)
**5(a)** Explain Circular queue and Double ended queue with example(10 marks)
**5(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 STACK ADT array implementation for the above program(10 marks)
**6(b)** Construct a binary tree for the following preorder and inorder traversal sequences

Pre-order: A B D G C E H I F

Inorder : D G B A H E I C F (10 marks)
**7(a)** Threaded binary tree(5 marks)
**7(b)** Huffman coding(5 marks)
**7(c)** Applications of stacks(5 marks)
**7(d)** Indexed sequential search(5 marks)
**7(e)** Array implementation of linked list(5 marks)