yes Sonate USN LL L TT II BCS304 Third Semester B.E./B.Tech. Degree Examination, Dee.2023/Jan.2024 Data Structures and Applications Time: 3 hrs. Max. Marks: 100 Note: 1. Answer any FIVE full questions, choosing ONE full question from each module. 2. M: Marks , L: Bloom’s level , C: Course outcomes. Module — 1 M[L] Cc QA ]a. | Define Data Structures. Explain with neat block schematic different type of | 10] L2 | COL | data structures with examples. What arc the primitive operations that can be performed? i D. | Differentiate between structures and unions shown examples for both. s | L1/ cor ©) What do you mean by pattern matching? Outline Knuth, Morris, Pratt) 5 | L2 | COT pattern matching algorithm. | OR Q2 | a. | Define stack. Give the implementation of Push (), POP () and display ()] 7 | 12] COL | functions by considering its empty and full.conditions. Write an algorithm to evaluate a postfix expression and apply the same for | 7 | 13] COI |__| the given postfix expression 6,2, fy 32-1442, *, + . | Write the Postfix form of the following using stack 6 | L3 | CO1 | @_A*@BtC+D*E) + (i) @+b*e)/(4-e)) Module - 2 a Q3 | a. | What are the disadvantages of ordinary queue? Discuss the implementation | 8 | L2 | CO2 of circular queue. b. | Write a note on miultiple stacks and priority queue. 6 | L2 | Coz e. | Define Queue: Discuss how to represent queue using dynamic arrays. 6 | L2 | Coz = a OR Qa | a. | What isa linked list? Explain the different types of linked lists with neat | 4 ] L2 [ CO2 diagram. . | Give the structure definition for singly linked list (SLL). Write a C function | 8 | L3 | CO2 10, | | @ Insert on element at the end of SLL. | | | Gi Delete a node at the beginning of SLL [Write a C-finetion to add two polynomials show the linked list] 8 [13 | CO2 | representation of below two polynomials p(x) = 3x" + 2x" +1 a(x) =8x"* —3x"" + 10x" | Module ~ 3 Q5 |a.| Write a C-function for the following operations on Doubly Linked List ] 8 | L3 | CO3 | DLL) () addition of a node. (ii) concatenation of two DLL. b. | Write C functions for the following operations on circular linked list 8 [13 | Cos (i) Inserting at the front of a list ii) Finding the length of a circular list Tof2 iBCS304 ©. | For the given sparse matrix, give the diagrammatic linked representation. 13 | CO3 || [2000 4003 A=|0 000 8001 lo 0 6 0} | OR Q6 | a. | Discuss how binary tree are represented using, | 6 ] 12] cos (i) Array (ii) Linked list . | Discuss inorder, preorder, postorder and level order traversal-with suitable [ 8 | 12 | CO3 recursive function for each. ©. | Define Threaded Binary Tree. Discuss In-Threaded binary Tree. if [12 | cos a Module—4 s Q7 ]a. | Write a function to perform the following operations on Binary Search Tree 13 | COs (BST): |G Inserting an element into BST | (i) Recursive search of a BST. . | Discuss selection Trees with an example. 12 | Cos e. | Explain Transforming a first into a binary tree with an example. 12 | cos} = = on i Q8 a. | Define graph. Show the adjacency matrix and adjacency list representation 13 | Co4 | of the graph given below (Refer Fig. Q8 (a). Fig. Q8 (a) . | Define the following Terminologies with examples, Li | Cos | @>—Bigtaph | Weighted graph | Gi). Self toop (iv) Parallel edges ‘e. | Explain in detail elementary graph operations 12 | Co# Module —5 Q9 |.a. | What is collision? What are the methods to resolve collision? Explain linear | 7 | L2 [COS probing with an example. . | Explain in detail, about static and dynamic hashing. 12 | Cos ©. | Discuss Lefist Trees with an example. 12 | COs | OR Q.10 | a. | Explain different types of HASH function with example. 12 | COs . | Discuss AVL tree with an example. Write a function for insertion into an | COs AVL Tree. ©. | Define Red-black Tree, Splay tree. Discuss the method to insert an element ‘COs into Red-Black tree. 2of2BCS Boh Grace marks for BCS-304 : Data Structures and Applications-Regd “Nirmala GR’ ‘ape 12, 2024-11302 AM To: boe@vuacin Respected sir, Greetings!!! With reference to the above subject, | would like to bring to your kind notice that there are two out of syllabus questions 10). b = 6 marks and 10). c- 8 marks keeping students well being in mind, itis decided to give the grace marks as mentioned below for out of syllabus questions. if attended 10.) b - 65 % of 6 = 3.9~ 4 marks 10.) ¢ - 60% of 8 = 4.8 ~ 5 marks can be allotted Kindly accept the request, thanks and regards Dr. Nirmala CR Dean, Placement Professor and Head Dept. of CS &E BIET, Davangere-4 Mobile : 974077037725S 23 Visvesvaraya Technological Univ 0465767, Belagavi, Karnataka -590 018 Scheme & Solution doen. Subject Title: Data Stucke Qa AgpitCation Subject Code: BCSZ04 ‘Question 7 Marks Number ania Allocated a. Diypaton Dale trucins * Geprntnterss frdividuel el Clanstentnon { Dake Shue, PrPeakire att teaeds * Apecsstens ~~ Pp organtading Gnd Stortg elute BR emcory - Date Structure ) Now Strlin( Past); whic (fom YF JX Jenp) | eo Grey (de2 pei) | | iat wise zy cme 4 ¢ > ters | | eu Je faite Cit] 47 | 5 Qeban CU Seedenp ) 2 Ct-denp) 2 Pye at- Corts &Pe #S ‘Subject Title: __ Subject Code | Marks | i Allocated 2 a.| Sate hftnatoo | | Jat ata a "Woneprimitive [treat dlatattauetves | oy a addition anc celtorn take at Gre End Calu TOP | + Xt spllows LIFO Crest In Pint Out) | JuihC) Void Push( ek meat km) a Ctop> = Max Stack S72é -!) Stare Full O° Stack L ++ top] = fens os ™ ay Mine srace SIZES 3LE] Pans _Punbo fl EI P ol Twp=-1 fe Pop) fy (tepe> -) Qatuan Stork Empty 1 Gutain Stax Ltop-“J 4 03M 3 709 27 aq | PRP ko —_> 20 ole] 2b | Marathon: Evacuate CP) joritim tind the VALUG an Grithimetic Exper p | | marten fm Pry, —-Motation! | beng jh uid 2. Noh wants")? at the End 0, | fang, onl ab eee + P |2- Scap P Lope to Sught And Fepecdt Lkep 3 andy eee ee blatant gO Pundit )Sentrel P Entountoca,|‘Subject Title: ___ Subject Code: a Marks Allocated Question Number ey an operand fd Entountard Place “ont state | | t on operate ye Cntounted , then, (@) Remove TOP Ckenents two ttma, whue AY the top elon ond B&B % meet—td top Clhmut W Evalue B orator A (6) Plate the Aesust F (>) pace fo STACK Lend 4 Strutue) Lena 4 step 2 Loop) 3 be 5) Set VALVE Coyral to the tp Ekmend 6 STACK, Bbxye _Eapuation ere] OP: | Ps | STACK Sty Gl273-%%+| 6 ce 673-4 2a+ | 2 Ca G2*AS—-h 2k>] 7 6 [2 —— 62/3-yoxty | 3 ws 3M 16 2/3-4ben | — 3 [3 —e 62/3- oar] | (ore | 62y3—-Goxe-+| 2 wae G213-hoe+ |e a 2 Dis 6273-yor+ f+ o le a Buu = 3) 2c. Dae 4 “the foitentng uaieg Stoen (Ax (BAC ADeE ) +P pene Sethe toes ecw Paty ExgeHior is ay ig f C HO & B AC AS x Ce BS 3m ce Gre ABC + (ae PBC | D ace ABCD | * (Cae ARCHD | | | & Gla PRcHDE y 2 oe PBC # DES ) * + ABA DEH | oF * PBceDey +HP fee Ee ee c ABea Dew rar +) HeSubject Code Subject Title: _ eee — \Seaeer| eee ee 2 oho Ca+ (ba c)/Cd-e)) = aberde -/+ | | | = | | Symbol _ Patt OP stacn | fe empty ¢ | a a ic | + . (+ ¢ a + | b Gb (+0 ai al C4 Cc abe (4(¥ 03m ) cbt ( vA Abt (av ( Abcw / a abcd Go — aber d (+/C- e aber d & C4/C- ) abca de— (+/ ) abCe de-74 Enphy FO) duasewrsoges om WwOne Maxg Pkenh ome ee x 2 ae Ke ry mb Fn Ree Pho pont, Ginnet adi fe ie 7 n Decne g ear Fotatron MAKG > Ly oi > ol 2 | | veel] ay a | | * 4 dex) fot on ve | spot Reon ean, Heli afeieieeateeeite eee ian ; nee Pym as Cont> ofSubject Code ] Marks | Allocated | ‘Subject Title: Question Number [3p Fagurnrntion fC Queue Void teldg (elment Pew ) lam Fess = (Pear +) ) 7-Max sere 3 . Cpyent 22 van) uewe PU) | Qpust Par = tems 4 a With Exglamckion Cliagran> Elmer’ Acte) t : 4 Cfpont == Tes ) 7 Velunn Queue Empiy(y 2 : | 3m pret (front +1) Moxa es Behan Quine pont] ; 5 4 Werth Bsagram Onc Explanatro™ ee d Ws es Bagram ton i Preend + Mubiplt Stetke otog WoRh Enqlainetion 3M | Page a Condo‘Subject Title: Subject Code Question Number | sc Ho pee ge Qyeve. using A ynanat Orhey a We Mabe puncte to alloca mumery 00% MAx_ Queue Tuseheet * Dytre cpuncieons fe Gohatron « a Qeprndason. Woid Sete) ow {staat node *temp: timp = (strut rode *) fralte ¢( Si 8ef (Struct rode)): temp —>lUink = NULL 4 (Tear 2> wu) © pone 2 peers temp 5 Eu Tear lin = temp: Fees keoge J enya 4 Laaeak Wet tye Lert ate Stogly Lirret Lat (SU) Doubly Lskt Lut “(DLO Grud SLL Cfradorn DLL Sqleen vith Gragren Poge #7 3M Marks | _| Allocated | him | iy 1M Cord aii aeile seen‘Subject Title: Subject Code: [ Question 7 Marks | Number Bee Solution = Allocated | Cofuneton +0 Pnted ON Elim ot End ¢ SLL Phe Yor Stertend) € oy natn Creak > aa aos a a — eue + 1 Lets ‘tele ) ddan pnexk = kemp dart = dempy ee Void dase by) Struck rode Atemp? tempo fim : Lempomok 22 NULL) Pry (the Slee cluledol =ya)\ m "temp Pro ) » ee Laem); = doses nul: J ele ee fem pomert 5 Print (“the Fem duetew = Farn) tenp-> fap); Aree C temp) 5 : 5 4 Firat (43k WY Fira Bans bm } \ Seer ree eee eee Oot‘Subject Title Subject Code: fQuexion a TT gohation T Marks | | Number 7 Eee perro eee [Allocated 4 Cs Co punctin to add two Polynomi als | | Porypetnien Pad (polypomier «1, PolyPetnio &7 | Poypantr Cc, Tear, temp: | Fink Sum > Maes (aeer, Sag (# gear )); bi C2 Bear; thie ( A&A b) Suiten ( Compare (QExpor , bo Expon d) { Care -\ ; odteah (bs Coe, , b> expen, G ver): b= bolt; break ; Cae 0: Sum > ODL 4p>loeh { (sump attach (Sum, ab expen, Hrear)} Qsealine ) be b> dtm 3 break: Care 1: Otten (ad Ex por Pre Eset, Ar war); As as\inx » FRCS Bs Gs qasitmn Dower (Od Coe} , A> xPon, Wma: pecye: br be>\nt ) abtech ( doce, b-> Expon, &¥eay) | Bear Prk == NULL: Represnteros w | | (ay > | ey (E> Wet) I oul (48D Gane — ble) Popes 9 Cont dSubject Title: Subject Code: Question Number Solution Allocated ‘Marks 5 tb C. eon te Die @ ‘a 4 anode Vod Srtedkba “ene Cr Cyst 2 Nut) DoD, Gc Fat Lact © Croke fen -pprere Laat tom So ed eer SS) tie © bempprnece = fame prik prev = Hee: apse Teng: 44 Nope Concat ( Node “+ , NOG Sx) t wong Cor > Cates nue) Teturn See? (Secra Nut) Fetvrm fanats Le thie C Cun mext |= NULL) Cur = Cur —pnext 5 Cur > mext = fee; a Sruture fot 5 Sindecting Ot the ont 4 @ lat . Potut Prat (Lut pata tlub, lutprtnien node) a CLC tan) ) * Laake = Node > Nodkke— lin = Modes batt hegre. EMG crook —aitnw = (¥ leat) —> Ixy yy (lar Dlink = node! 9 Ly hey uM _ et ee Page #10 ConteSubject Title: Subject Code: Question Marks Number come Allocated > pb) irsty length of Civcedan Quive Sar length C Lurpotnter laut) Lit Perot temp: Frnt Count = 0; 44 (Wit) bu Temp> Lost; do f County Kemp o temp > Tink 5 Hy sskile CEemp > Last) ) 5 Seturn Counts 04m Cont-fSubject Code: Subject Title: Question Solution Allocated FO] Brnany Tre Sepertedn Using array 3M \—— wt oe List 3M by tatag amy Rompe org. Tree. &) “Reese punetton 4p Prov, Preorder Portorder Nord Sresty Ctreepeinin qty) T acme Shorduy (Pty —plyt Chid ) » Piece Ct-d", per pdatay Trerein Chr —auant chi ); % 5 a cE Dey " ct Preordin (Treeprotartia pty) 9M ty eg - Prat (Std Per date )y Prordin (pty —plytchild )> Preorder ( per nigitt child); 4 Bi Void Patterden (Lreepotata ptr) ce Porordan (er lycra PSE ordi Ctr pmgntrehi) 5 os OY Pty —pdatay » Void, levelorela ( -treaatnite pty) Pn 5 RAS OD Tree pot nin aa Dex Quevé_si2el: 4h CAPEY) Aatorn oe Print, (“id err ciate ): Pee 12 Cot-4Subject Title: Subject Code: ‘Question Number Solution Marks Allocated | 5 b y (py —elirchs Ww) Adda Coty —rlytchild >; Cpty —pnght Chita y Oday Cex > ght Child )) fhe preawy Replace the NULL foxy by Poirier, Called Trendy Riu 4h lonttructon thread: Mh per plete tD NULL , rowan Pretennse g Ho 34 WAY PEY—> Mighehild H NULL —> Fhorda Su come ‘ Example by taking ny Sioa tree Ahewing norda thre ole ct Froary Wee. bad On Tnrordar Travnet 3 , Paget 3 Contd‘Subject Title: Subject Code: Fast rns mec 80 Vod fnsut Cteupotnin node Tat Typ thetkm) trapmta gtr, temp = modified Qorch CM rede , Yh Ctemp II L (# mode) ) £ Maroc (pty, Siauf (#PeY)) 5 Pea —> olata. Key 2 R) Pex —> data fhm = theltem, Per —> Jeftchild = pty aight Chi NOLL) 5 (¥ mode ) 4 (K < temp —> data. key) temp —> \eptearia = Pty, Eke timp—> yyntch Pare elle # mode = ptr; F ¥ | Solum ae. aT Sates oe | Fea | faartton 40 Popde ce faisty fine 99 BST | (Benevy Seah Tred (D nmetiny an Eleva fate BST | Exampe 40) With qqlan ation @ ‘ Im 3MSubject Code = ‘Subject Title : [Question| Solution eae Number KR) Recwve Searcy af a GST Elamend HH Seaen( rePotakr gost , Prt key) (root) Sratveo NULL; HL (eae eet pcate “Hey ) Quorn & Cronk data) 3m (KR < Boot —> data Key) Srerorn Seah (reat > lytehnd LB Quien Search (‘oot —PArIgnechil *): 1M J with Gitanahion Sekehon Tree a A tourmemend tree Th 0 fn Conmple binary tree Go whith Goch mods — obnets & Ploeg Wo ame Laat Lev hak me nods Cextanel modes) Weed fo Reprntint au Re Payal , dnd She Gust 4 dhe modes (Fnteanal Teds J Pupresnt Cf te hone Or [sn among thon . ae — Wnnes “tree — Lda Tre Wftoner Tre: Thy @ felechon tre) bhin the Feteral nodes Pepretnt the fio othe match, 3m Loh Example tre. | i Page 1s CorotSubject Title = Subject Code : Question! Solution ‘Number le tre: wn & tourna cece TE, when the Fhtanal medl ore Ued to Paprtent: ‘the tate | AVL Tee — Gaga os Height talent — -binory heah tre 2M — Te % Bait fo be balanad balento “fatter 4 Each nod? Mm beh | to | Rotaee Foetr (k) = Faaght Clee crs) heathy Page 421 Cont 4‘Subject Title = Questior ic Marks ae Solution | 7 | exam aaet (©) Heo 3M ° ee, © o AVL “Tre. Fuki procm by tarmg Ary Example let 3y 0 © | deznatson SRed-Blace tvee \ ~ Rey balancing Broary Geach ‘tre. om — nokd ft fot Storage Gnd ethereal , Sapseration WH Example Seley tree = Bro Geach tree with addittonal thet Tea Octeked Clements Oh Quick do OCU caged, 2” © ramp « Peehon” Prout pt Red Blue, Elemett addition HAA Ong Example. am — ey See *APPEOVED”