Data Structures - May 2013

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) Write a program in Java to implement circular Queue using array(10 marks) 1(b) Explain linear and non-linear data structure with example(5 marks) 1(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) 2(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 15, 23, 22, 11, 44(10 marks) 3(b) Give different searching techniques. Write a program to implement binary search(10 marks) 4(a) Explain different representation of graph. State advantages and disadvantages of each representation(10 marks) 4(b) Write a Java program to create a binary search tree. Show BST for the following input: 10, 05, 14, 22, 17, 01, 08(10 marks) 5(a) Explain the method of Huffman Encoding. Apply Huffman encoding method for the sentence "MALAYALAM". Give Huffman code for each symbol(10 marks) 5(b) Hash the following in a table of size 11. Use any two collision resolution techniques. 23, 55, 0, 71, 67, 23, 100, 18, 10, 90, 44(10 marks) 6(a) Write ADT for stack. Give applications of stack(10 marks) 6(b) Explain Priority Queue(5 marks) 6(c) Write a program in Java to create a linked list and perform the following operations
1. Insert into list
2. Search for data
3. Delete from list
4. Display the list(5 marks) 7(a) Tree traversal algorithms(10 marks) 7(b) Merge sort with example(10 marks) 7(c) AVL tree and multiway tree(10 marks)