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

Code No: 07A3EC15 Set No.1
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) How does a C++ structure di?er from a C++ class?
(b) What is a class? How does it accomplish the data hiding?
(c) Write a C++ program to create a bank account which includes account num-
ber, name, account kind and balance. It should include also the operations to
assign initial values, to deposit, to withdraw after checking the balance?
[4+4+8]
2. (a) What does inheritance mean in C++? elaborate the di?erent forms of inher-
itance? provide an example for each?
(b) What is an virtual function? Why we need virtual function?
(c) Write short notes on ?le streams? [8+4+4]
3. (a) De?ne Algorithm? elaborate the characteristics of algorithms?
(b) Order the subsequent functions by growth rate: N,
v
N , N1.5
, N2
, N log N, 2N,
N3
?
(c) Show the stack status and the output string at every step in converting the
subsequent in?x expressions to post?x expressions insisting on the usual prece-
dence and associativity rules? a+b*c-(d*e/f)*g [6+2+8]
4. (a) De?ne Dictionary and Dictionary with duplicates? List the operations per-
formed on a dictionary?
(b) List any 2 applications of dictionaries and/or dictionaries with duplicates?
(c) Use linear probing, a hash table with b = 13 buckets, and the hash function
f(k) = k mod b. begin with an empty hash table and insert pairs whose keys
in order are 7, 42, 25, 70, 14, 38, 8, 21, 34, 11. Draw the hash table subsequent
every insert? [4+4+8]
5. (a) Write a C++ function to remove max element form max heap.
(b) Write a C++ function to insert an element into min heap. [8+8]
6. (a) discuss how to represent binary search tree with duplicates?
(b) discuss the insertion operation of binary search tree with duplicates?
(c) begin with an empty binary search tree with duplicates and insert the keys 2,
2, two and 2? Draw your tree subsequent every insert? What is the tree height
subsequent the insertion of n 2s? [4+8+4]
1 of 2Code No: 07A3EC15 Set No.1
7. Draw the order-7 b-tree resulting from the subsequent keys into any initially empty
tree:4,40,43,26,87,66,22,9,95,25,27,72,46,77,93,12. [16]
8. Write an algorithm for Brute Force trend matching and analyze its time com-
plexity with suitable example. [16]
? ? ? ? ?

Earning:   Approval pending.