JNTU Kakinada B-Tech 2-2 RT22053 ADVANCED DATA STRUCTURES R13 April 2018 Question Paper

Code No: RT22053
II B. Tech II Semester Supplementary Examinations, April-2018
ADVANCED DATA STRUCTURES (Com. to CSE, IT)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answer ALL the question in Part-A
3. Answer any THREE Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART-A
1. a) Explain the rehashing methods briefly?
b) Show that left and right rotations are inverses of each other. What can you say about double
rotations?
c) Discuss about lazy binomial queue?
d) Which algorithm works with negative edges? Why
e) Explain about the concept of Lower bound?
f) Compare binary tree with multi way tree? (4M+4M+3M+3M+4M+4M)
PART-B
2. Following elements are inserted into an empty hash table with hash function f(x) = x% 13 and
linear probing 112, 44, 52, 45, 37, 278, 89, 28, 61,249
a) Draw the hash table for each insertion.
b) What is the load factor after last insertion?
c) What is the maximum number of buckets examined in an unsuccessful search
(8M+4M+4M)
3. a) What are the different types of imbalances that occur while deleting a node from AVL
trees?
b) How they are rectified? Explain with an example for each type of imbalance? (8M+8M)
4. a) Write an algorithm to insert an element in max heap? Trace the above algorithm for the
following elements? 1, 2, 3, 4, 5, 6, 7, 8
b) While creating the heap for above data will fall in best case or worst case? Justify your
answer? (8M+8M)
5. a) Explain Dijkstra?s algorithm with example.
b) Explain Warshall?s algorithm with example. (8M+8M)
6. a) Discuss about Average Case Complexity of quick Sort?
b) Explain Radix sorting with an example? Discuss its time complexity? (8M+8M)
7. a) Draw the flow chart for Boyer-more algorithm.
b) Discuss about fixed field buffers? (8M+8M)

1 of 1
SET – 1
R13