RTU Previous Year Question Papers BE CSE Fifth Semester Advanced Data Structure Dec 2011

RTU Previous Year Question Papers BE CSE Fifth Semester

Advanced Data Structure Dec 2011


1. a) State the condition under which insertion of a vertex in a Red-Black tree will result in a sequence of recolouring steps that terminate with the root changing colour.

b) Will the root of Red-Black tree always be black after performing a deletion operation ? Justify with an example.


1    (a) Construct a 2-3 tree for the list 9, 5, 8, 3, 2, 4 and by successive insertion.

(b) Define Dictionary and Dictionary with duplicates. List the operation performed on dictionary.


 2 (a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3,and 9. One at a time into an initially empty min heap ?

(b) Explain the implementation of a binomial heap and its operation with suitable example.


2 Write short note on :

(a) Binomial trees

(b) Implementing fibonancy heap


3 A network G = (V,E) as follows

V   = {a, b, c, d, e, f}

E = {(ab, 2), (Cb, 2), (Cd, 2), (ed, 2), (ef, 2), (ac, 4), (be,

4), (df, 4) }

where the number following each edge is the capacity of that edge :

(i)  A function f is defined on the edge of G with each edge e having f (e) equal to the capacity of e. Explain why this defines a valid st. flow on G for suitably chosen vertices S and t.

(ii) State the Max-flow Min-cut theorem and explain how your answer to part (a) illustrate this theorem.


3. Consider the following graph :



(a)  Apply ItruskaTs algorithm to G. List the edge of the forest that is grown, in the order that they added.

(b) What is the weight of minimum spauing tree in G ?



(a) What- if zero-one principle ? Describe in detail.

(b)Prof that if a comparison network with n input sorts aB 2n bmary string of length n correctly, then it sort all sequence correctly.


(a) Explain the bitonic sorting network with suitable

(b) Write short note on :

(i) Ftirity Queue

(ii)  Operations on disjoint sets.


5 (a) Describe the Chinese remainder theorem.

(b) What  ftvisien theorem ? Explain.


5  Write note on :

(a) Computation of Discrete logarithm

(b) Modular Arithmetic

Leave a Comment