JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA-II Semester Supplementary Examinations July 2010 DATA STRUCTURES (through JAVA)

Code No: 32002

Time: 3hours
Max.Marks:60

Answer any Five questions

All questions carry equal Marks

1. Write short notes on the following
a) Dynamic Method Dispatch
b) Member Access Rules
c) Interfaces and abstract classes

2. a) What is a Thread? Explain its Life Cycle?
b) Explain and implement how to create User-defined Exception class with an example program?

3. a) What is Pseudo-code? Describe in Pseudo-code how to insert an element at the beginning of Doubly Linked List?
b) Explain in detail different ways of analyzing algorithms?

4. What is Queue? Explain the methods of Queue ADT? Write the code-fragments for Array-based java implementation of the Queue?

5. Write Pseudo-code for the Pre-order, Post-order, In-order traversal of the sub-tree rooted at node ‘V’?

6. a) Define and explain AVL trees with an example?
b) Draw the order-7 B-Tree resulting from inserting the following keys (in this order) into an initially empty Tree T: 4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12

7. a)Write an algorithm for java Implementation of Merge Sort?
b) What is hash-code? Compare and contrast insertion sort, merge sort, quick sort and Radix-sort?

8. a) Write Huffman-Coding – Algorithm?
b) Write Knuth-Morris-Pratt algorithm for pattern matching?