B.E. Fourth Semcstcr (Compute.r Scicrce & [Link].
Compurer Enginee, rrg) (CGS)
f03ll : Data Structurcs : 4 KS 0l /4 KE 0t
P. Pages : 2 AW - 3042
Timc : Three Hours llllllfiillllllr ll Max. Marks : 80
Notes r I Allquestion carry marks as indicated.
2 Assume suitable data wherevcr necessal,v.
3 Use of pen Blue/Black inVrefill only for writing the answer book.
I a) Describe thc complexity ofpaftem matching algorithm. Hence Eovc the complexiry off$t
pancm matching dgorirhm is O(n2,1.
b) Explain the string operation in view of exbacting a charaoter or letter group of characters
and count the length of stdng.
olt
2 a) find the table and conesponding graph for the sccond pattem matching algorit]un where '7
the pancrn P-abaab.
b) Discuss the mathematical / ,gorithmic notations & lunctions used in dala structue basics. 6
3. a) \lhat do you m€an by bi' .rl- uee traversal ? Explain with an cxample.
b) Explain bubble sort method for the anay list A having followiog conteot 1
A | 24,34,14,19, 15,8,9
Thus discuss thc algorithm.
OR
{. a) \trtte an algoritlEn lbr iNertio! of an element as well as deletion in lioear array assume 7
suitable data and illushate the method.
b) Compare the tridigular matrix aDd Tridiagonal matrix hence discuss their importame and
applicabilit). Illushate wilh suitable example.
5- a) Desoribc the tonns Garbage colleclioo. overflow and underflorv. Explain the remedial 6
soiirti,lr'ls foi thcni.
b) Let P(x) derotes the polyaomial draw the diagram representing P(x) by headcrlist with 1
anay structue P(x) = 4x9 +2x7 - 15x5 +10x2 -10
OR
6. a) Describe the linked list structue illustlate with an example the uaversing of linlicd list 6
b) Explain the iosertion and deletion operation oo linked list. Thus list out at l"iist three
adlan'.ages of linked list.
AW - 3042 I P.T.O
1 a) A list'L'contains charircter saing using quick son arrange them into ascendiog alphabctic 1
order and also tind the location olal clement "11".
L : SANTGADGEBAIIAAN{RAV1\.'TI
b) Flxplai[ with a suilable example the recursive procedure using stack and Queues 7
OR
ti. a) Con rert the following in tix express ion imo reverse polish notation. 1
(A+B)*C-(D+E)i I:
b) Describe thc stack sln cture zmd uTite algorithm for PUSII and POP opemtiotr. List out 7
adtanrages.
!) a) Draw the preorder and ,oslorder lrci) representation foi the following inorder expression I
(A*Er)/C -(D-E)*I
b) Discuss and illustrate tlLe Binar, trc( rcpresentation in menlon' !
OR
10. a) Draw binar), tree for thr lbll.,\uing e{tression and show the lree lraversal using stack 6
(A+B)*C-D -Fl
"(E
b) What do you understand sortingl Explai[ Ilcap Sort uith its advantages and w te 7
algorithm.
U, a) Diff€r,jntiatc seleclion son and Radiri Sod procedure. Bxplain merits and demeits ofthem. 6
b) Exirlain link represc talioir for the graph. Justify \uheather this repiesentation is better than
allay or not.
OR
12. a) Discuss thc operations and trarersins the gmph using linked rcpresentation 6
b) Explain thc Warshail's algoritlxn. How this algodthm irnds the path illustate with an 7
exaurple.
AW - 3042
