Jawaharlal Nehru Technological University Kakinada 2008 B.Tech Computer Science and Engineering advanced data structures - Question Paper

Time: three hours Max Marks: 80
ans any 5 ques.
All ques. carry equal marks
? ? ? ? ?
1. (a) What do you mean by dynamic initialization of object? Why do we need to
do this?
(b) How Is dynamic initialize of objects achieved?
(c) Write a C++ program for generating Fibonacci series? [4+4+8]
2. (a) elaborate all the restrictions and limitations in overloading operators?
(b) Write a C++ program to demonstrate overloading add(+) and compare (=)
operators on strings? [8+8]
3. (a) What is the key di?erence ranging from algorithm and program?
(b) discuss the 8 asymptotic identity rules?
(c) discuss the steps to implement the subsequent operations of singly-linked list
without head node using illustrative examples?
i. removing at front
ii. removing at end
iii. removing node before a speci?ed node
iv. removing node after a speci?ed node. [2+4+2+2+3+3]
4. (a) What is skip list? How it is di?erent from a linear linked list?
(b) discuss with a neat example the insertion operation?
(c) discuss with a neat example the deletion operation? [4+6+6]
5. (a) If a d-heap is stored as an array, for an entry located in position k, where are
the parents and children?
(b) Write a C++ function to build a binary heap? How many number of compar-
isons needed for it? [8+8]
6. begin with empty binary search tree:
(a) Insert the keys 15,5,20,14,30,22,2,4,5,7,9,18 in this order. Draw the tree fol-
lowing every insert using binary search insert method.
(b) Delete the keys 2, 4, five in the order and draw the tree subsequent every deletion.
[8+8]
7. (a) De?ne splay trees? discuss splay operation using a suitable example?
1 of 2Code No: 07A3EC15 Set No.3
(b) begin with a splay tree that is a 10- node full binary tree; the keys are1-10.
Remove the keys in the order 10, 9, 8... 1. Draw your tree immediately
subsequent every deletion. [8+8]
8. Write an Hu?man coding algorithm and prove that Hu?man’s algorithm constructs
an optimal pre?x code for a string of length n with d distinct characters in O(n +
d log d)? [16]
? ? ? ? ?







2 of 2Code No: 07A3EC15 Set No.4
II B.Tech. I Semester Regular Examinations, November -2008
ADVANCED DATA STRUCTURES
( 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) define the importance of destructors?
(b) What is the copy constructor? elaborate it uses?
(c) Write a C++ function for Tower of Hanoi? [4+4+8]
2. (a) elaborate the rules for virtual functions?
(b) Write a C++ program to demonstrate runtime polymorphism using virtual
function? [8+8]
3. (a) What is dequeue? discuss different operations need to be supported by de-
queue?
(b) Write a C++ program to evaluate post?x expression? [6+10]
4. (a) Write an insert routine for hash tables with quadratic probing?
(b) Write a routine to rehashing for open addressing hash tables? [10+6]
5. (a) What is priority queue? discuss any 2 applications of priority queue?
(b) Show the outcome of inserting 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 22 and 35, one
at a time into an initially empty max heap? [8+8]
6. (a) discuss the algorithm for right-to-right and left-to-left rotation.
(b) explain above rotation for the subsequent keys. 3,43,12,33,4,34,21,22,25,15,16,17.
[8+8]
7. (a) discuss brie?y the representation of red-black trees using an example?
(b) Starting with a red- black tree that is 10- node full binary tree the keys are1-
10, all nodes are black. Remove the keys in the order 7,6,5,10.draw your tree
subsequent every deletion and immediately after rotation or color change that
is performed. tag all the nodes with their color and identity their rotation
types(if any) that is done. [4+12]
8. calculate a table representing the KMP failure function for trend string “cg-
tacgttcgtac”. [16]
? ? ? ? ?
1 of 1

Earning:   Approval pending.