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)