Data Structures - May 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) What is Recursion? Write a program to calculate factorial of a number using recursion(10 marks) 1(b) Explain linear and non-linear data structure with example.(5 marks) 1(c) Write ADT for stack. Give application of stack.(5 marks) 2(a) Write a program to implement insertion sort using Java. Show passes of insertion sort for the following input data: 5, 3, 2, 1, 4. (10 marks) 2(b) Give different searching techniques. Write a program to implement Binary Search(10 marks) 3(a) Write a program in Java to copy content of a file to another file(10 marks) 3(b) Write a program in Java to sort n integer numbers using Quicksort. Some the steps to sort the given numbers: 25, 10, 7, 30, 15, 2, 96, 14(10 marks) 4(a) Explain different representation of graph. State advantages and disadvantages of each representation(10 marks) 4(b) What is the use of Huffman Encoding? Apply and give Huffman code for each symbol in sentence "DATA STRUCTURE"(10 marks) 5(a) Write a Java program to implement circular queue using array(10 marks) 5(b) Write a Java program to create a binary search tree. Show BST for the following input: 10, 5, 4, 12, 15, 11, 3(10 marks) 6(a) What is the use of hashing? Show hash table entries for the given dataset using linear probing and quadratic probing: 12, 45, 67, 88, 27, 78, 20, 62, 36, 55(10 marks) 6(b) What are the advantages of linked list over array? Write a program in Java to implement stack using linked list.(10 marks) 7(a) Tree traversal algorithm(10 marks) 7(b) Graph traversal algorithm(10 marks) 7(c) Priority queue(10 marks)