R09 - December, 2011 - Regular Examinations - Set - 1.

II B.Tech I Semester Examinations,December 2011
DATASTRUCTURES THROUGH C
Common to Information Technology, Computer Science And Engineering,
Electronics And Communication Engineering, Electrical And Electronics
Engineering
Time: 3 hours Max Marks: 75
Answer any FIVE Questions
All Questions carry equal marks
*****
1. What is a threaded binary tree? Explain with an example how the threads are
mapped. [15]
2. (a) Describe an e cient algorithm to nd the longest palindrome that is a su x
of a string T of length n.
(b) Compare the trie with hash table. [15]
3. (a) Write short notes about hashing and a chained hash table.
(b) Explain about hashing with tail nodes. [7 8]
4. Write an algorithm of heap sort and also analyze its complexity. [15]
5. (a) Explain constructor overloading with examples?
(b) Write a C program to implement the constructor overloading. [7 8]
6. Show all insertion of the following sequence of letters/numbers in a B - tree of order
7.
All 26 letters A through Z, starting from A as the rst insertion. [15]
7. (a) Write a method to delete the pair with the largest key from a binary Search
tree.
(b) How do de ne the height of an AVL tree? Explain about the balance factor
associated with a node of an AVL tree. [15]
8. (a) Can standard parameters be used with a template function? Explain with an
example.
(b) Write a program using a standard parameter with a template function. [7 8]
*****