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.
Posts
