2010 Jawaharlal Nehru Technological University, Hyderabad Code No: R05211201 R05 Set No. 4 II B.Tech I Semester Supplementary Examinations,June 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS Question paper
Code No: R05211201 R05 Set No. 4
II B.Tech I Semester Supplementary Examinations,June 2010
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1. (a) De ne inheritance? Explain about the access control mechanism in Inheri-
tance in C++?
(b) Write a program to illustrate the concept of hierarchical Inheritance? [8+8]
2. 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 con gured hash table in which neverUsed is true for every empty
bucket. [16]
3. (a) Solve the following recurrence relation using substitution method
T(n) = 1 where n 4
= T(pn) + c where n > 4
(b) Explain Big Oh notation with an example. [8+8]
4. (a) Derive the time complexity of Quick sort in average case.
(b) Write a non recursive algorithm for pre order traversal of a tree. [8+8]
5. Start with an empty AVL search tree and insert the following keys in the given
order:
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
Draw the gures depicting the tree immediately after each insertion and following
the rebalancing rotation (if any). Label all nodes with their balance factors and
identify their rotation types. [16]
6. (a) Prove to yourself that all exception objects (the ones that are thrown) are
properly destroyed.
(b) Prove to yourself that if you create an exception object on the heap and throw
the pointer to that object, it will not be cleaned up. [8+8]
7. (a) Explain about the dynamic memory allocation and de-allocation in C++.
(b) Explain about static inner classes with a program. [8+8]
8. Using algorithm OBST compute W(i, j), R(i, j) and C(i, j) for the identi er set
(a1; a2; a3; a4)=(end, goto, print, stop, continue) with p1 = p2 = 0:125; p3 = p4 =
00625; p5 = 0:1875 q0 = 0; q1 = 0:1875; q2 = q3 = q4 = q5 = 0:0625 using R(I, j) and
construct the optimal binary search tree. [16]
KEYWORDS:JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS,JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS QUESTION PAPER,JNTU,JNTU QUESTION PAPER,JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD SUPPLEMENTARY EXAMINATIONS JUNE JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS
Code No: R05211201 R05 Set No. 4
II B.Tech I Semester Supplementary Examinations,June 2010
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1. (a) De ne inheritance? Explain about the access control mechanism in Inheri-
tance in C++?
(b) Write a program to illustrate the concept of hierarchical Inheritance? [8+8]
2. 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 con gured hash table in which neverUsed is true for every empty
bucket. [16]
3. (a) Solve the following recurrence relation using substitution method
T(n) = 1 where n 4
= T(pn) + c where n > 4
(b) Explain Big Oh notation with an example. [8+8]
4. (a) Derive the time complexity of Quick sort in average case.
(b) Write a non recursive algorithm for pre order traversal of a tree. [8+8]
5. Start with an empty AVL search tree and insert the following keys in the given
order:
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
Draw the gures depicting the tree immediately after each insertion and following
the rebalancing rotation (if any). Label all nodes with their balance factors and
identify their rotation types. [16]
6. (a) Prove to yourself that all exception objects (the ones that are thrown) are
properly destroyed.
(b) Prove to yourself that if you create an exception object on the heap and throw
the pointer to that object, it will not be cleaned up. [8+8]
7. (a) Explain about the dynamic memory allocation and de-allocation in C++.
(b) Explain about static inner classes with a program. [8+8]
8. Using algorithm OBST compute W(i, j), R(i, j) and C(i, j) for the identi er set
(a1; a2; a3; a4)=(end, goto, print, stop, continue) with p1 = p2 = 0:125; p3 = p4 =
00625; p5 = 0:1875 q0 = 0; q1 = 0:1875; q2 = q3 = q4 = q5 = 0:0625 using R(I, j) and
construct the optimal binary search tree. [16]
KEYWORDS:JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS,JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS QUESTION PAPER,JNTU,JNTU QUESTION PAPER,JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD SUPPLEMENTARY EXAMINATIONS JUNE JNTU 2010 ADVANCED DATA STRUCTURES AND ALGORITHMS