Data Structures - Dec 2011

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 ? State its advantages and disadvantages.(5 marks) 1 (b) What is AVL tree ? Explain with example.(5 marks) 1 (c) (i) Abstract data type(2 marks) 1 (c) (ii) Binary tree(2 marks) 1 (C) (iii) Graph(1 marks) 1 (d) Construct Huffman code for C++JAVA (5 marks) 2 (a) Explain different types of tree traversal techniques. Explain each with suitable example.(10 marks) 2 (b) Explain different ways to represent a graph. Give example.(10 marks) 3 (a) Write a program to implement queue using array.(10 marks) 3 (b) Explain any two applications of stack using a program.(10 marks) 4 (a) Explain the working of merge sort and sort the following elements :
50 , 10 , 20 , 40 , 5 , 60 , 35 (10 marks) 4 (b) Explain circular and priorty queue. (10 marks) 5 (a) Write a program to create a doubly linked list and perform the following operations
(i) Insert into the list
(ii) Delete from the list
(iii) Search for a data(9 marks) 5 (b) Write a Java program that reads a text file and counts all occurrences of a word. (11 marks) 6 (a) What is hashing ? Hash the following in a table size of 11. Use any two collision techniques.
20, 5 ,10, 11, 22, 33, 40, 50, 30, 51, 31(10 marks) 6 (b) Construct binary tree for inorder and postorder traversal sequence given below.
Inorder = INFORMATION
Postorder= INOFMAINOTR (10 marks)

Write short notes on any four of the following :-

7 (a) Comparison of sorting algorithm (5 marks) 7 (b) B+ trees (5 marks) 7 (c) Binary search (5 marks) 7 (d) Prefix and postfix forms of expressions. (5 marks) 7 (e) Asymptotic notation(5 marks) 7 (f) Tower of Hannoi (5 marks)