Jawaharlal Nehru Technological University Hyderabad 2006 B.E Information Technology ADVANCED DATA STRUCTURE - Question Paper

taking any 5 operators. [16]
3. (a) Write a program to change the case of every word in a file to initial capitals.
(b) Write a program to concatenate the 2 provided strings? [8+8]
4. describe the Abstract data kind for Stack. Write a C ++ program to implement
stack ADT using arrays. [16]
5. Develop a class for hash table using linear probing and neverUsed concept to handle
an erase operation. Write complete C++ code for all the methods. Include a
method to reorganize the table when (say) 60% of the empty buckets have never
used equal to false. The reorganization should move pairs around as necessary and
leave a properly configured hash table in which neverUsed is actual for every empty
bucket. [16]
6. (a) What is an AVL search tree? How do we describe the height of it? discuss
about the balancefactor associated with a node of an AVL tree.
(b) discuss how an AVL tree can be used to sort a sequence of n elements in O
(n log n) time. [8+8]
7. (a) Prove that net T be a B-tree of order m and height h. Let d = [m/2] and let
n be the number of elements in T.
i. 2dh-1 - one  n  mn - 1
ii. logm (n + 1)  h  logd ??n+1
2
+ 1
(b) discuss the advantages of splay tree in representation of dictionaries. [10+6]
8. (a) discuss the brute force algorithm with an example
(b) Draw the compact representation of the suffix tire for the string “minimize
minima”. [8+8]
? ? ? ? ?
1 of 1


Code No: R059210503 Set No. 4
II B.Tech I Semester Regular Examinations, November 2006
ADVANCED DATA STRUCTURE
( Common to Computer Science & Engineering and Electronics &
Computer Engineering)
Time: three hours Max Marks: 80
ans any 5 ques.
All ques. carry equal marks
? ? ? ? ?
1. (a) What is a class? How do you describe class in C++?
(b) discuss about the data members and member functions of a class?
(c) discuss about access control mechanism in C++? [5+5+6]
2. (a) What is multiple inheritance? Write a program to illustrate the concept of
Multiple Inheritance.
(b) What is Hybrid inheritance? Write a program to illustrate the concept of
Hybrid Inheritance. [8+8]
3. (a) Write a program that reverses the order of the characters in a string.
(b) A palindrome is a word or group of words that learn the identical forward and
backward. For example “madam” or “wow.” Write a program that takes a
string argument from the command line and prints whether the string was a
palindrome or not. [8+8]
4. Write a method in C++ to join 2 doubly linked lists into a single doubly linked
list. In a join the elements of 2nd list are appended to the end of 1st list. [16]
5. Use linear probing, a hash table with b=17 buckets, and the hash function f(k) =
k% b; begin with an empty hash table and insert pairs whose keys are 7, 42, 25,
70, 14, 38, 8, 21, 34, 11. The pairs are inserted in this order.
(a) Draw the hash table for every insertion?
(b) What is the loading factor after last insertion?
(c) What is the maximum number of buckets examined in an unsuccessful search
of your table?
(d) What is the maximum number of buckets examined in a successful search?
[4+4+4+4]
6. describe a class called binarySearchTree to represent a Binary search tree. Extend
this class by adding a public method outputInRange (Low,High) that outputs,
in ascending order of key, all elements in a binary search tree whose key lies ranging from
Low and High. Use recursion and avoid entering sub trees that cannot possibly
contain any elements with keys in desired range. [16]
7. (a) Write an algorithm of Red-Black tree insertion.
1 of 2

Code No: R059210503 Set No. 4
(b) discuss the operation of splay trees with an example. [8+8]
8. (a) discuss the construction of the kmp flow chart with an example.
(b) discuss the search engines. [10+6]
? ? ? ? ?
2 of 2

Earning:   Approval pending.