II B.Tech I Semester (R07) Supplementary Examinations, November 2011

II B.Tech I Semester (R07) Supplementary Examinations, November 2011
ADVACNED DATA STRUCTURES
(Common to Computer Science & Engineering and Electronics
& Computer Engineering)


1.    (a) what is the need for OOP?
(b) Explain various object oriented programming features.
      2    Write a C++ program to perform basic operations on circular linked list ?
      3    (a) Explain model of external sorting ?
            (b) Explain Poly phase Merge.?
      4    (a)Write a insertion algorithm for red black tree. Also analyze its complexity.?
            (b) Compare and contrast splay tree and binary tree with suitable example.?
      5    (a) Explain in detail the stream class hierarchy.?
            (b) Write notes on
                  i) File streams
                  ii) String streams
6    Compute a table representing the KMP failure function for pattern  string “cgtacgttcgtac”.  ?
7    Let (N) be the average number of full nodes in an n-node binary search tree
      8. (a)Explain linear probing and quadratic probing?
(b) determine a suitable value for the function divisor D when linear Probing is                             used. Do this for each of the following situations.
                                i. n=50, Sn ≤ 3, U n ≤ 20.
                                ii. n = 500, Sn ≤ 5, U n ≤ 60.
                                iii n= 10, Sn ≤ 2, U n ≤ 10.