C_questions

Q.178 Whatdoyoumeanbyhashing?Explainanyfivepopularhashfunctions.(5) Ans: Hashing Hashingprovidesthedirectaccessofrecordfrom thefilenomatterwheretherecord isinthefile.ThisispossiblewiththehelpofahashingfunctionH whichmapthe keywith the corresponding key address or location.It provides the key-to- addresstransformation. Fivepopularhashingfunctionsareasfollows:- DivisionMethod:Anintegerkeyxisdividedbythetablesizem andtheremainderis takenasthehashvalue.Itcanbedefinedas H(x)=x%m+1 Forexample,x=42andm=13,H(42)=45%13+1=3+1=4 MidsquareMethod:Akeyismultipliedbyitselfandthehashvalueisobtainedby selectinganappropriatenumberofdigitsfromthemiddleofthesquare.Thesame positionsinthesquaremustbeusedforallkeys.Forexampleifthekeyis12345, squareofthiskeyisvalue152399025.If2digitaddressesisrequiredthenposition 4thand5thcanbechosen,givingaddress39. FoldingMethod:Akeyisbrokenintoseveralparts.Eachparthasthesamelengthas thatoftherequired address exceptthe lastpart.The partsare added together, ignoringthelastcarry,weobtainthehashaddressforkeyK. Multiplicativemethod:Inthismethodarealnumbercsuchthat0<c<1isselected.For anonnegativeintegralkeyx,thehashfunctionisdefinedas H(x)=[m(cx%1)]+1 Here,cx%1isthefractionalpartofcxand[]denotesthegreatestintegerlessthanor equaltoitscontents. DigitAnalysis:Thismethodformsaddressesbyselectingandshiftingdigitsofthe originalkey.Fora given key set,thesame positions in the key and same rearrangementpatternmustbeused.Forexample,akey7654321istransformedto theaddress1247byselectingdigitsinposition1,2,4and7thenbyreversingtheir order. Q.179 Drawthe11-item hashtableresultingfromhashingthekeys12,44,13,88,23, 94,11,39,20,16and5usingthehashfunctionh(i)=(2i+5)mod11 (7) Ans: Tablesizeis11 h(12)=(24+5)mod11=29mod11=7 h(44)=(88+5)mod11=93mod11=5 h(13)=(26+5)mod11=31mod11=9 h(88)=(176+5)mod11=181mod11=5 h(23)=(46+5)mod11=51mod11=7 h(94)=(188+5)mod11=193mod11=6 h(11)=(22+5)mod11=27mod11=5 h(39)=(78+5)mod11=83mod11=6 h(20)=(40+5)mod11=45mod11=1 h(16)=(24+5)mod11=29mod11=4 h(5)=(10+5)mod11=15mod11=4

Q.180 Explainanytwomethodstoresolvecollisionduringhashing. (4) Ans: Thetwomethodstoresolvecollisionduringhashingare: OpenaddressingandChaining. Openaddressing:Thesimplestwaytoresolveacollisionistostartwiththehash addressanddoasequentialsearchthroughthetableforanemptylocation.Theidea istoplacetherecordinthenextavailablepositioninthearray.Thismethodiscalled linearprobing.An emptyrecord isindicated bya specialvaluecalled null.The majordrawbackofthelinearprobemethodisclustering. Chaining:Inthistechnique,insteadofhashingfunctionvalueaslocationweuseitas anindexintoanarrayofpointers.Eachpointeraccessachainthatholdstheelement havingsamelocation. Q.181 Findouttheminimum spanningtreeofthefollowinggraph. (8)

Ans: Theminimum spanningtreeofgivengraph:- Step1: Edge(a,c) cost=5 addtotreeT Step2: Edge(c,e) cost=4 addtoT Step3: Edge(c,f) cost=3 addtoT Step4: Edge(f,d) cost=1 addtoT

Step5: Edge(f,b) cost=2 addtoT Thustheabovetreeistheminimum spanningtreeofthegraph. Q.182 Giveanalgorithm tocomputethesecondminimum spanningtreeofagraph. (8) Ans:Findouttheminimum spanningtreeusingPrim`sorKruskal`sAlgorithm.Remove oneedgefrom MST.Onevertexwillbecomeisolated.Addanedge,whichisnotinthe MST,suchthatthevertexgetsconnected.Findouttheincreaseinthetotalweightof thespanningtree. RepeatthisprocesswitheveryedgeoftheMST. Removethatedge,whoseremovalandadditionofsomeotheredge,willincreasethe totalweightofMSTbyminimum.Thiswillgivethesecondminimum spanningtree. Forexample:- LetGbeasfollows:- A 1 B 6252C3D8

NowMST:- AB122D C RemoveABfrom MST Nowtogetaspanningtree,eitherDBistobeaddedorCDistobeadded.Additionof DBwillincreasetheweightby2units(i.e.3–1)andadditionofCDwillincreasethe weightby4units(5-1).ThereforeremovalofABwillincreasetheweightofthenext spanningtreeby2. Now removeedgeCBthenCD orBC istobeadded,edgeCVD willincreasethe weightofthetreeby3units(5-2) SimilarlyifAD istoberemoved,itwillbereplacedbyCD whichwillincreasethe weightofthetreeby3.Thusthesecondminimum spanningtreeisobtainedby remainingABandaddingDB. Q.183 Define a threaded binary tree.Write an algorithm forinordertraversalofa threadedbinarytree. (6) Ans: ThreadedBinaryTree:- Ifanodeinabinarytreeisnothavingleftorrightchildoritisaleafnodethenthat absenceofchildnodeisrepresentedbythenullpointers.Thespaceoccupiedby thesenullentriescan beutilized to storesomekind ofvaluableinformation. Onepossiblewaytoutilizethisspaceistohavespecialpointerthatpointtonodes higherinthetreethatisancestors.Thesespecialpointersarecalledthreadsand thebinarytreehavingsuchpointersiscalledthreadedbinarytree. Therearemanywaystothreadabinarytreeeachofthesewayseithercorrespond eitherin-orderorpre-ordertraversalofT.AThreadedBinaryTreeisabinarytreein whicheverynodethatdoesnothavearightchildhasaTHREAD(inactualsense, alink)toitsINORDERsuccessor.Bydoingthisthreadingweavoidtherecursive methodoftraversingaTree,whichmakesuseofstacksandconsumesalotof memoryandtime. Thenodestructureforathreadedbinarytreevariesabitanditslikethis structNODE { structNODE*leftchild; intnode_value; structNODE*rightchild; structNODE*thread; } TheINORDERtraversalfortheabovetreeis--DBAEC.So,therespectiveThreaded Binarytreewillbe--

BhasnorightchildanditsinordersuccessorisAandsoathreadhasbeenmadein betweenthem.Similarly,forD andE.C hasnorightchildbutithasnoinorder successoreven,soithasahangingthread. Thealgorithm fordoingtheabovetaskisasfollows; Voidinorder(NODEPTRroot) { NODEPTRp,trail; p=root; do { trail=null; while(p!=null) { trail=p; p=p->left; } if(trail!=null) { printf(“%d\\n”,trail->info); p=trail->right; while(trail->rt&&p!=NULL) { printf(“%d/x”,p->info); trail=p; p=p->right; } } }while(trail!=NULL); } Q.184Giveanalgorithm tosortdatainadoublylinkedlistusinginsertionsort. (10) Ans: SimpleInsertionsortiseasilyadaptabletodoublylinkedlist.InthisLet'smakethe ThreadedBinarytreeoutofanormalbinarytree... methodthereisanarraylinkofpointers,oneforeachoftheoriginalarrayelements. Initiallylink[i]=i+1for0<=I<n-1andlink[n-1]=-1.Thusthearraycanbethoughtof asadoublylinklistpointedtobyanexternalpointerfirstinitializedto0.Toinsertthe kthelementthelinkedlististraverseduntiltheproperpositionforx[k]isfound,or untiltheendofthelistisreached.Atthatpointx[k]canbeinsertedintothelistby

merelyadjustingthelistpointerswithoutshiftinganyelementsinthearray.This reducesthetimerequiredforinsertionbutnotthetimerequiredforsearchingforthe properposition.ThenumberofreplacementsinthelinkarrayisO(n). voidinsertion_sort(inputtypea[],unsignedintn) { unsignedintj,p; inputtypetmp; a[0]=MIN_DATA; /*sentinel*/ for(p=2;p<=n;p++) { tmp=a[p]; for(j=p;tmp<a[j-1];j--) a[j]=a[j-1]; a[j]=tmp; } } Q.185 WhatisanAbstractDataType(ADT)?Explainwithanexample. (4) Ans: AbstractdatatypesorADTsareamathematicalspecificationofasetofdataandthe setofoperationsthatcan beperformed on thedata.Theyareabstractin the sensethatthefocusisonthedefinitionsoftheconstructorthatreturnsanabstract handlethatrepresentsthedata,andthevariousoperationswiththeirarguments.The actualimplementationisnotdefined,anddoesnotaffecttheuseoftheADT. Forexample,rationalnumbers(numbersthatcanbewrittenintheform a/bwherea andbareintegers)cannotberepresentednativelyinacomputer.A RationalADT couldbedefinedasshownbelow. Construction:CreateaninstanceofarationalnumberADTusingtwointegers,aand b,wherearepresentsthenumeratorandbrepresentsthedenominator. Operations:addition,subtraction,multiplication,division,exponentiation,comparison, simplify,conversiontoareal(floatingpoint)number. Tobeacompletespecification,eachoperationshouldbedefinedintermsofthedata. Forexample,whenmultiplyingtworationalnumbersa/bandc/d,theresultisdefined asac/bd.Typically,inputs,outputs,preconditions,postconditions,andassumptions totheADTarespecifiedaswell. Whenrealizedinacomputerprogram,theADTisrepresentedbyaninterface,which shieldsacorrespondingimplementation.UsersofanADTareconcernedwiththe interface,butnottheimplementation,astheimplementationcanchangeinthefuture. ADTstypicallyseenintextbooksandimplementedinprogramminglanguages(or theirlibraries)include: · StringADT · ListADT · Stack(last-in,first-out)ADT · Queue(first-in,first-out)ADT · BinarySearchTreeADT · PriorityQueueADT

· ComplexNumberADT(imaginarynumbers) Thereisadistinction,althoughsometimessubtle,betweentheabstractdatatype andthedatastructureusedinitsimplementation.Forexample,aListADTcanbe representedusinganarray-basedimplementationoralinked-listimplementation.A Listisanabstractdatatypewithwell-definedoperations(addelement,remove element,etc.)whilealinked-listisapointer-baseddatastructurethatcanbeused tocreatearepresentationofaList.Thelinked-listimplementationissocommonly usedtorepresentaListADTthatthetermsareinterchangedandunderstoodin commonuse. Similarly,aBinarySearchTreeADTcanberepresentedinseveralways:binarytree, AVLtree,red-blacktree,array,etc.Regardlessoftheimplementation,theBinary SearchTreealwayshasthesameoperations(insert,remove,find,etc.) Q.186 Suppose we wish to multiply four matrices of realnumbers M1*M2*M3*M4wereM1is10*20,M2is20*50,M3is50*1andM4is1*100. Assumethatthemultiplicationofap*qmatrixbyq*rmatrixrequirespqrscalar operations,find theoptimalorderinwhich to multiplythematricesso asto minimizethetotalnumberofscalaroperations. (5) Ans: HereM1=10x20 M2=20x50 M3=50x1and M4=1x100 Nowoptimalorderis 1. M2*M3=[20x50]*[50x1]=[20x1] Andnoofscalaroperationsare20*50*1=1000 2. M1*M2M3=[10x20]*[20x1]=[10x1] Andnoofscalaroperationsare10*20*1=200 3. M1M2M3*M4=[10x1]*[10x100]=[10x100] Andnoofscalaroperationsare10*1*100=1000 Sototalnoofscalaroperationsrequireare1000+200+1000=2200. Q.187Show atree(ofmorethanonenode)forwhichthepreorderandinordertraversals generatethesamesequence.Isthispossibleforpreorderandpostordertraversals? Ifitis,showanexample.(5) Ans: A binarytreewith 5 nodes0 ,1,2,3 and 4 whoseinorderand post order sequencesarethesame.

Thisisnotpossibleforpreorderandpostordertraversals. Q.188 WritemodulestodothefollowingoperationsonaBinaryTree. (i) Countthenumberofleafnodes. (ii) Countthenumberofnodeswithtwochildren. (9) Ans: (i)Leafcount(T) { staticintn=0; if(T!=NULL) {leafcount(Tleft); if(Tleft==NULL&&Tright=NULL) n++ leafcount(Tright) } return(n);} (ii)Leafcount(T) { staticintn=0; if(T!=NULL) {leafcount(Tleft); if(Tleft!=NULL&&Tright!=NULL) n++ leafcount(Tright) } return(n);} Q.189 Ifn>=1,provethatforanyn-keyB-treeTofheighthandminimum degreet>=2, h<=logt(n+1)/2. (7) Ans: InthecaseofaB-treewithaminimum noofkeys,thereisonekeyintheroot, 2nodesatdepth1,2ti-1nodesatdepthi. Lethbetheheightofthetreeandnbethenoofnodes.Then h n>=1+(t-1)2ti-1 i=1 whichworksouttoth<=(n+1)/2

Sowetakethelogtofbothsides h<=logt(n+1)/2 Q.190 AcocktailshakersortdesignedbyDonald Kunthisamodificationofbubblesortinwhichthedirectionofbubblingchangesin eachiteration:inoneiteration,thesmallestelementisbubbledup;inthenext,the largestisbubbleddown;inthenext,thesecondsmallestisbubbledup;andsoforth. Writeanalgorithm toimplementthisandexploreitscomplexity. (14) Ans: Cocktailsort,alsoknownasbidirectionalbubblesort,cocktailshakersort,shaker sort,ripplesort,orshuttlesort,isastablesortingalgorithmthatvariesfrom bubble sortinthatinstead ofrepeatedlypassing throughthelistfrom top to bottom, itpassesalternatelyfrom toptobottom andthenfrom bottom totop.Itcanachieve slightlybetterperformancethanastandardbubblesort. ComplexityinBigOnotationisO(n²)foraworstcase,butbecomesclosertoO(n)if thelistismostlyorderedatthebeginning. voidcocktail_sort(intA[],intn) { intleft=0,right=n; boolfinished; do { finished=true; --right; for(inti=left;i<right;i++) if(A[i]>A[i+1]) { std::swap(A[i],A[i+1]); finished=false; } if(finished)return;finished= true; for(inti=right;i>left;i--) if(A[i]<A[i-1]) { std::swap(A[i],A[i-1]); finished=false; } ++left; }while(!finished); } Q.191 Considerthefollowingundirectedgraph: (i) Findaminimum costspanningtreebyKruskal’salgorithm. (ii) Findadepth-firstspanningtreestartingataandatd. (iii) Findabreadth-firstspanningtreestartingataandatd. (iv) Findtheadjacencylistrepresentationofthegraph. (3.5x4= 14)

Ans: (i)Findaminimum costspanningtreebykruskal’salgorithm . Assumedh=3 Edges (gf) = 1 Accept (ab) = 2 Accept (de) = 2 Accept (bc) = 3 Accept (dh) = 3 Accept (cd) = 4 Accept (ih) = 4 Accept (ef) = 5 Accept (ac) = 5 Reject (bh) = 6 Reject (ai) = 7 Reject (id) =8 Reject (dg) = 9 Reject Sominimum costspanningtreeis: bc e a df ih g AndCostis2+3+4+2+5+1+3+4=24 (ii)FindaDepthfirstspanningtreestartingataandd. bc e a d f ih g bc e d af ih g (iii)Findabreadthfirstspanningtreestartingataandd. bc e

ad i h g f b e c a df Ih g (iv)Findtheadjacentlistrepresentationofthegraph. a b,c,i b a,c,h c a,b,d d c,e,g,h,i e d,f f e,g g d,f h b,d,i i a,d,h Q.192 WorkthroughBinarySearchalgorithm onanorderedfilewiththefollowing keys:{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.Determine the numberofkey comparisonsmadewhilesearchingforkeys2,10and15. (6) Ans: HereList={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} BinarySearchforkey2 (1)Herebottom =1Top=16andmiddle=(1+16)/2=8 Since2<list(8) (2)bottom =1Top=middle-1=7andmiddle=(1+7)/2=4 2<list(4) (3)bottom =1Top=middle-1=3andmiddle=(1+3)/2=2 2=List(2) Sototalnumberofcomparisonsrequire=3 BinarySearchforkey=10 (1)Herebottom=1Top=16andmiddle=8 10>List(8) (2)bottom =middle+1=9Top=16middle=(9+16)/2=12 10<List(12)

(3)bottom =9Top=middle-1=11middle=(9+11)/2=10 10=List(10) Sototalnoofcomparisons=3 BinarySearchforkey=15 (1)Herebottom=1Top=16andmiddle=8 15>List(8) (2)bottom =middle+1=9Top=16middle=(9+16)/2=12 15>List(12) (3)bottom =middle+1=13Top=16middle=(13+16)/2=14 15>List(14) (4)bottom =middle+1=15Top=16middle=(15+16)/2=15 15=List(15) Sototalnoofcomparisons=4 Q.193 Whatarethreadedbinarytrees?Whataretheadvantagesanddisadvantagesof threadedbinarytreesoverbinarysearchtrees? (4) Ans: AThreadedBinaryTreeisabinarytreeinwhicheverynodethatdoesnothavearight childhasaTHREAD(inactualsense,alink)toitsINORDERsuccessor.Bydoingthis threadingweavoidtherecursivemethodoftraversingaTree,whichmakesuseof stacksandconsumesalotofmemoryandtime. Thenodestructureforathreadedbinarytreevariesabitanditslikethis-- structNODE { structNODE*leftchild; intnode_value; structNODE*rightchild; structNODE*thread; } Let'smaketheThreadedBinarytreeoutofanormalbinarytree... TheINORDERtraversalfortheabovetreeis--DBAEC.So,therespectiveThreaded Binarytreewillbe-- BhasnorightchildanditsinordersuccessorisAandsoathreadhasbeenmadein betweenthem.Similarly,forD andE.C hasnorightchildbutithasnoinorder successoreven,soithasahangingthread. Advantage 1.BydoingthreadingweavoidtherecursivemethodoftraversingaTree,which makesuseofstackandconsumesalotofmemoryandtime. 2.Thenodecankeeprecordofitsroot. Disadvantage1.ThismakestheTreemorecomplex.2.Morepronetoerrorswhenboththe childarenotpresent&bothvaluesofnodespointertotheiransentors. Q.194 Show that quickalgorithm takesO timeintheworstcase. (4) Ans: TheWorstCaseforQuick-SortThetreeillustratestheworstcaseofquick-sort,which occurswhentheinputisalreadysorted! TheheightofthetreeisN-1notO(log(n)).Thisisbecausethepivotisinthiscasethe largestelementandhencedoesnotcomeclosetodividingtheinputintotwopieces eachabouthalftheinputsize.Itiseasytoseethatwehavetheworstcase.Sincethe pivotdoesnotappearinthechildren,atleastoneelementfrom levelidoesnot

appearinleveli+1soatlevelN-1youcanhaveatmost1elementleft.Sowehavethe highesttreepossible.Notealsothatlevelihasatleastipivotsmissingsocnahave atmostN-ielementsin allthe nodes.Ourtree achieves this maximum.So the timeneeded is proportionalto the totalnumber of numbers written in the diagramwhichisN +N-1+N-2+...+1,whichisagaintheonesummationwe knowN(N+1)/2orΘ(N2. Hencetheworstcasecomplexityofquick-sort isquadratic. Q.195 Writeanalgorithm toconvertaninfixexpressiontoapostfixexpression. Executeyour algorithm withthefollowinginfixexpressionasyourinput. (8) Ans: Algorithm:Polish(Q,P) SupposeQisanarithmaticexpressionwritteninfixnotation.Thisalgorithm finds theequivalentpostfixexpressionP. 1.Push“(”ontoSTACK,andadd“)”totheendofQ 2.ScanQfrom lefttorightandrepeatSteps3to6foreachelementofQuntilthe STACKisempty: 3.Ifanoperandisencountered,addittoP 4.Ifaleftparenthesisisencountered,pushitontoSTACK. X5.Ifanoperator isencountered,then: XX(a)repeatedlypopfrom STACKandaddtopeachoperator(onthetopofstack) hasthesameprecedenceasorhigherprecedencethan

(b)add toSTACK. [EndofIfstructure] 6.Ifarightparenthesisisencountered,then: (a)Repeatedlypopfrom STACKandaddtoPeachoperator(onthetopof STACK) untilaleftparenthesisisencountered. (b)Removetheleftparenthesis.[DonotaddtheleftparenthesistoP] [EndofIfstructure.] [EndofStep2loop.] 7.Exit Example: Input(m+n)*(k+p)/(g/h)^(a^b/c) Step1:( Output:nil Step11:) * Output:mn+kp+ ( Step2:m Output:m Step12:/ Output:mn+kp+* ( / Step3:+ Output:m Step13:( ( Output:mn+kp+* + / ( Output:mn Step14:g ( Output:mn+kp+*g Step4:n + Output:mn+ / Output:mn+kp+*g ( Step15:/ / Step5:) ( / Step6:* Output:mn+ Step16:h/ Output:mn+kp+*gh ( * / Step7:( ( Output:mn+ Step17:^^ Output:mn+kp+*gh/ Step8:k * / ( Output:mn+k * Step9:+ + Output:mn+k Step18:(( Output:mn+kp+*gh/ ( ^ * / Step10:p Output:mn+kp Step19:a( Output:mn+kp+*gh/a + ^ ( /

* Output:mn+kp+*gh/a Step20:^ ^ Output:mn+kp+*gh/ab ( ^ / Step21:b ^ ( ^ / Step22:/ / Output:mn+kp+*gh/ab^ ( ^ / Step23:c / Output:mn+kp+*gh/ab^c ( ^ / Step24:) ^ Output:mn+kp+*gh/ab^c/ / Step25:End Output:mn+kp+*gh/ab^c/^/ Q.196 Whatisrecursion?A recursiveprocedureshouldhavetwoproperties.What arethey? (4) Ans: Recursionmeansfunctioncallitselfrepeately. Properties: (1)Theremustbesomebasecasewheretheconditionend. (2)Eachrecursivecalltotheprocedureinvolveasmallercaseoftheproblem . Q.197 Supposecharactersa,b,c,d,e,fhaveprobabilities0.07,0.09,0.12,0.22,0.23,0.27 respectively.FindanoptimalHuffmancodeanddrawtheHuffmantree.Whatis theaveragecodelength? (10) Ans: HuffmanTree:

HuffmanCodeare a=1111 b=1110 c=110 d=00 e=01 f=10 Averagecodelength=P(a).4+P(b).4+P(c).3+P(d).2+P(e).2+P(f).2 =0.07*4+0.09*4+0.12*3+0.22*2+0.23*2+0.27*2 =.28+.36+.36+.44+.46+.54=2.44 Q.198 Provethatthenumberofnodeswithdegree2inanyBinarytreeis1lessthanthe number ofleaves. (4) Ans: TheproofisbyinductiononthesizenofT. LetL(T)=Noofleaves&D2(T)=NoofnodesofTofdegree2 ToProveD2(T)=L(T)-1 BasicCase:n=1,thenTconsistsofasinglenodewhichisaleaf. L(T)=1andD2(T)=0 SoD2(T)=L(T)-1 InductionStep:Letn>1andassumeforallnonemptytreesT1ofsizek<n that D2(T`)=L(T`)-1 Sincen>1,atleastoneofx=left(T)ory=right(T)isnonempty. Assumexisnonempty;theothercaseissymetric Bytheinductionhypothesis, D2(x)=L(y)-1 IFyisempty,thenagainbytheinductionhypothesis, D2(y)=L(y)-1and D2(T)=D2(x)+D2(y)+1 =L(x)-1+L(y)-1+1 =L(x)+L(y)-1 D2(T)=L(T)-1HenceProved Q.199 Equalkeysposeproblem fortheimplementationofBinarySearchTrees.Whatis theasymptoticperformancetheusualalgorithm toinsertnitemswithidentical keysinto an initiallyemptyBinarySearch Tree?Propose sometechnique to improvetheperformanceofthealgorithm. (7)

Ans: A sympoticperformance willbe linearin O(n).Thatis the tree created willbe skewsymmetric.Identicalkeysshouldbeattachedeitherasleftorrightchildofthe parent,whereverpositionsareavailable.Foreg.18,3,5,2,4,7,2,9,2,16,2,11,2,10,2 Thecreationofthetreeshouldbeasfollows: i.e.similarkeysshouldnotskewtotheBST.Thenperformancewillbecomeinferior. Q.200 Consideralistofnumbers9,20,6,10,14,8,60,11given.Sortthem usingQuickSort. Givestepwisecalculation. (8) Ans: 9,20,6,10,14,8,60,11 choosing9asPivot(Pass—1) 6,8,9,10,14,20,60,11 Thesublistontheleftsideof9issortedtherefore,nomoresortingonleftsublist Nowchoosing10asPivot(pass–2) (10isalreadyintheposition) 6,8,9,10,14,20,60,11 Choosing14asPivot(pass–3) 6,8,9,10,11,14,60,20 Choosing60asPivot[pass–4) 6,8,9,10,11,14,20,60 Q.201Whatisasparsematrix?Explainanefficientwayofstoringasparsematrixin memory. (4) Ans: SparseMatrix Amatrixinwhichnumberofzeroentriesaremuchhigherthanthenumberofnon zeroentriesiscalledsparsematrix.Thenaturalmethodofrepresentingmatricesin memoryastwo-dimensionalarraysmaynotbesuitablefoesparsematrices.One maysavespacebystoringforonlynonzeroentries.ForexamplematrixA (4*4 matrix)representedbelow wherefirstrowrepresentthedimensionofmatrixandlastcolumntellsthenumberof nonzerovalues;secondrow onwardsitisgivingthepositionandvalueofnonzero number.

0 0 0 0 0 9 0 0 Herethememoryrequiredis16elementsX2bytes=32bytes Theabovematrixcanbewritteninsparsematrixform asfollows: 4 0 2 3 Herethememoryrequiredis12elementsX2bytes=24bytes Q.202 Evaluatethefollowingprefixexpressions (9) (i) +*2+/14251 (ii) – *63– 41 (iii) ++26+– 1324 Ans: Evaluatingaprefixexpression. (i) + * 2 + / 14 2 5 1 =+ * 2 +7 51 =+ * 2 12 1 =+ 24 1 = 25 (ii) - *63-41 =- 18 - 41 =- 18 3 = 15 (iii) + +2 6 +- 13 2 4 =+ 8 +- 13 24 =+ 8 + 11 4 =+ 8 15 = 23 Q.203 (i)GivefourpropertiesofBig–ONotations. (4) (ii)GivethegraphicalnotationsofBig-Oestimationsforthefollowingfunctions: ,n, ,n2,n3,2n (3) Ans:

(i)FourpropertiesofBig-Onotationsare: 1. Reflexivity 2. Symmetry 3. TransposeSymmetry 4. Transitivity Reflexivity: f(n)=O(f(n)) SymmetryandTransposeSymmetry f(n)=O(g(n))iffg(n)=(f(n)) Transitivity f(n)=O(g(n))andg(n)=O(h(n))impliesf(n)=O(h(n)) (ii) n Sqrtn n! n2 n3 n4 logn nlogn 2n 2 1.41 2 4 8 16 0.301 0.6020 4 03 6 3 1.73 6 9 27 81 0.477 1.4313 8 121 64 4 2.00 24 16 64 256 0.602 2.4082 16 06 4 5 2.24 120 25 125 625 0.698 3.4948 32 97 5 6 2.45 720 36 216 1296 0.778 4.6689 64 151 08 7 2.65 5040 49 343 2401 0.845 5.9156 128 098 86 8 2.83 4032 64 512 4096 0.903 7.2247 256 0 09 2 9 3.00 3628 81 729 6561 0.954 8.5881 512 80 243 83 10 3.16 3628 100 1000 1000 1 10 1024 800 0 Q.204 Writeanalgorithm toinsertanelementkindoublelinkedlistat (8) (i)Startoflinkedlist (ii)AfteragivenpositionPoflist

(iii)Endoflinkedlist. Ans: Algorithm toinsertanelementkindoublelinkedlistatapositionwhichis:- (i)Startofalinkedlist whileinsertingatthestartofthelinkedlistwehavetochangetheroot nodeandsoweneedtoreturnthenewroottothecallingprogram. nodeptrinsertatstart(nodeptrroot,nodeptrk) { k->next=root; k->back=root->back; root->back->next=k; root->back=k; returnk; } (ii)Afteragivenpositionpoflist Hereweassumethatppointstothatnodeinthedoublylinkedlistafterwhich insertionisrequired. insertafter(nodeptrp,nodeptrk) { if(p==null) { printf(“voidinsertion/n”); return; } k->back=p; k->next=p->next; p->next->back=k; p->next=k; return; }

(iii)Endoflinkedlist Herekistheelementtobeinsertedandrootisthepointertothe firstnodeofthedoublylinkedlist. insertatend(nodeptrroot,nodeptrk) { nodeptrtrav; while(trav->next!=root) trav=trav->next; k->next=root; root->back=k; trav->next=k; k->back=trav; return; } Q.205 Writeanalgorithm toaddtwopolynomialsusinglinkedlist. (8) Ans: Algorithm toaddtwopolynomialsusinglinkedlistisasfollows:- Letpandqbethetwopolynomialsrepresentedbythelinkedlist. 1.whilepandqarenotnull,repeatstep2. 2.Ifpowersofthetwotermsateequal thenifthetermsdonotcancel theninsertthesum ofthetermsintothesumPolynomial Advancep Advanceq Elseifthepowerofthefirstpolynomial>powerofsecond Theninserttheterm from firstpolynomialintosum polynomial Advancep Elseinserttheterm from secondpolynomialintosum polynomial Advanceq 3.copytheremainingtermsfrom thenonemptypolynomialintothesum polynomial. Thethirdstepofthealgorithmis tobeprocessedtilltheendofthepolynomialshas notbeenreached. Q.206 Writemodulestoperform thefollowingoperationonBinarytree (8) (i)countnumberofleafnodes (ii)findheightoftree Ans: (i)countnumberofleafnodes intleafcount(node*t) { staticintcount=0; if(t!=NULL) { leafcount(tleft) if(tleft==NULL&&tright==NULL) count++; leafcount(tright);

} (8) return(count); } (ii)Moduletofindheightoftree height(Left,Right,Root,height) 1. IfRoot=Nullthenheight=0; return; 2. height(Left,Right,Left(Root),heightL) 3. height(Left,Right,Right(Root),heightR) 4. IfheightLheightRthen height=heightL+1; Else height=heightR+1; 5. Return; Q.207 CreateB-Treeoforder5from thefollowinglistofdataitems: 20,30,35,85,10,55,60,25 Ans: Forthegivenlistofelementsas 20 30 35 85 10 55 60 25 TheB-Treeoforder5willbecreatedasfollows Step1: Insert20,30,35and85 Step2: Step3: Step4:

Step5: ThisisthefinalB-treecreatedafterinsertingallthegivenelements. Q.208Writeanalgorithm toinsertanelementkintobinarysearchtree.Givetheanalysis andexample. (8) Ans: Thealgorithm toinsertanelementkintobinarysearchtreeisasfollows:- /*Getanewnodeandmakeitaleaf*/ getnode(k) left(k)=null right(k)=null info(k)=x /*Initializethetraversalpointers*/ p=root trail=null /*searchfortheinsertionplace*/ whilep<>nulldo begin trail=p ifinfo(p)>x thenp=left(p) else p=right(p) end /*Toadjustthepointers*/ Iftrail=null Thenroot=k/*attachitasarootintheemptytree*/ else ifinfo(trail)>x then left(trail)=k else right(trail)=k Analysis:-Wenoticethattheshapeofbinarytreeisdeterminedbytheorderof insertion.Ifthevaluesaresortedinascendingordescendingorder,theresulting treewillhavemaximum depthequaltonumberofinputelements.Theshapeofthe treeisimportantfrom thepointofviewofsearchefficiency.Thedepthofthetree determinesthemaximum numberofcomparisons.Thereforewecanmaximize searchefficiencybyminimizingtheheightofthetree. eg.Forthevaluesas6,7,8,9,10 thebinarytreeformedwouldbeasfollows

Q.209Fillinthefollowingtable,showingthenumberofcomparisonsnecessarytoeitherfind avalueinthearrayDATAordeterminethatthevalueisnotinthearray. (8) DATA 26 42 96 101 102 162 197 201 243 [1] [2] [3] [4] [5] [6] [7][8] [9] NumberofComparisons Value Sequential BinarySearch OrderedSearch 26 2 103 244 Value Ans: Sequential BinarySearch 26 OrderedSearch 4 2 4 103 1 3 244 1 4 6 9 Q.210 Explainthefunctionalityoflinearand quadraticprobingwithrespecttohashingtechnique. (8) Ans: LinearProbing:Thesimplestwaytoresolveacollisionistostartwiththehash addressanddoasequentialsearchthroughthetableforanemptylocation.The ideaistoplacetherecordinthenextavailablepositioninthearray.Thismethodis calledlinearprobing.Anemptyrecordisindicatedbyaspecialvaluecallednull.The arrayshouldbeconsideredcircular,sothatwhenthelastlocationisreachedthe searchproceedstothefirstrecordofthearray.Anunoccupiedrecordlocation isalwaysfoundusingthismethodifatleastoneisavailable;otherwise,thesearch haltsunsuccessfullyafterscanningalllocations.Themajordrawbackofthelinear probemethodisthatofclustering. Whenthetableisinitiallyempty,itisequallylikelythatanewrecordwillbeinserted inanyoftheemptypositionbutwhenthelistbecomeshalffull,recordsstartto

appearinlong strings ofadjacentpositions with gaps between the strings. Thereforethesearchtofindanemptypositionbecomeslonger. Quadraticprobing:Intheabovecasewhenthefirstinsertionismadetheprobability ofnewelementbeinginsertedinaparticularpositionis1/n wherenisthesizeof thearray.Atthetimeofsecondinsertiontheprobabilitybecomes2/nandsoonfor the kthinsertion the probabilityis k/n,which is ktimes as compared to any otherremainingunoccupiedposition.Thustoovercomethephenomenonoflong sequenceofoccupiedpositionstobecomeevenlongerweusequadraticrehash,in thismethodifthereisacollisionathashaddressh,thismethodprobesthearrayat locationsh+1,h+4,h+9,...Thatis(h(key)+i2% hashsize)fori=1,2,...givesthe ithhashofh. Q.211 Thefollowingvaluesaretobestoredinahashtable 25,42,96,101,102,162,197,201 Usedivision method ofhashingwith atablesizeof11.Usesequential methodofresolvingcollision.Givethecontentsofarray. (8) Ans: Tablesizeisgivenas11 H(25)=(25)mod11+1=3+1=4 H(42)=(42)mod11+1=9+1=10 H(96)=(96)mod11+1=8+1=9 H(101)=(101)mod11+1=2+1=3 H(102)=(102)mod11+1=3+1=4 H(162)=(162)mod11+1=8+1=9 H(197)=(197)mod11+1=10+1=11 H(201)=(201)mod11+1=3+1=4

Q.212 WriteKruskal’salgorithm andgivetheanalysis.CompareitwithDijkstra’s method. (8) Ans: Kruskal’sAlgorithm forminimum costspanningtree 1.MakethetreeTempty. 2.Repeatsteps3,4and5aslongasTcontainsless thann-1edgesandEnotempty;otherwiseproceedtostep6. 3.Chooseanedge(v,w)from Eoflowestcost. 4.Delete(v,w)from E. 5.If(v,w)doesnotcreateacycleinTthenadd(v,w)toT elsedicard(v,w). 6.IfTcontainsfewerthann-1edgesthenprint(‘nospanningtree’). Thecomplexityofthisalgorithm isdeterminedbythecomplexityofsorting methodapplied;foranefficientsortingitisO(ElogE).Italsodependsonthe complexityofthemethodsusedforcycledetectionwhichisofO(V)asonly V-1edges are added to tree which gives a totalofO(E logV)time.So complexityofKruskal’salgorithm isisO(V+ElogV).AsVisasymptotically nolargerthanE,therunningtimecanalsobeexpressedasO(ElogV). Dijkstrahasnotdevelopedanyalgorithm forfindingminimum spanningtree.Itis Prim’salgorithm.Dijkstra’salgorithm tofindtheshortestpathcanbeusedto findMSTalso,whichisnotverypopular. Q.213 Writealgorithm forBreadthFirstSearch(BFS)andgivethecomplexity. (8) Ans: Thistraversalalgorithm usesaqueuetostorethenodesofeachlevelofthegraph asandwhentheyarevisited.Thesenodesarethentakenonebyoneandtheir adjacentnodesarevisitedandsoonuntilallnodeshavebeenvisited.Thealgorithm terminateswhenthequeuebecomesempty. Algorithm forBreadthFirstTraversalisasfollows: clearq(q) visited(v)=TRUE whilenotempty(q)do forallverticeswadjacenttovdo ifnotvisitedthen { insert(w,q) visited(w)=TRUE } delete(v,q); Hereeachnodeofthegraphisenteredinthequeueonlyonce.Thusthewhileloop isexecutedntimes,wherenistheorderofthegraph.Ifthegraphisrepresentedby adjacencylist,thenonlythosenodesthatareadjacenttothenodeatthefrontof thequeuearecheckedtherefore,theforloopisexecutedatotalofEtimes,whereE isthenumberofedgesinthegraph.Therefore,breadthfirstalgorithm isO(N*E)for linkedexpression.Ifthegraphisrepresentedbyanadjacencymatrix,theforloopis executedonceforeachothernodeinthegraphbecausetheentirerow ofthe adjacencymatrixmustbechecked.Therefore,breadthfirstalgorithm isO(N2)for adjacencymatrixrepresentation.

Q.214 AbinarytreeThas10nodes.TheinorderandpreordertraversalsofTyieldthe followingsequenceofnodes: Inorder:D B H E A I F J C G Preorder:A B D E H C F I J G DrawthetreeT. (8) Ans: Givenofatree,the INORDER: D B H E A I F J CG PREORDER: A B D E H C F I J G Thenthetreeofwhosetraversalisgivenisasfollows Q.215 ConstructAVLtreefrom thefollowingsetofelements (8) {March,May,November,August,April,January,December,July} Ans: TheAVLtreefrom thegivensetofelementsisasfollows: {March,May,November,August,April,January,December,July} Q.216 Evaluatethefollowingpostfix-expressionusingstack.Show thecontentof thestackineachstep. 623+-382/+*2$3+ (6)

Ans: Thecontentofstackineachiterationwillbeasfollows: Symbol Opnd1 Opnd2 Value Stack 6 6 2 6,2 3 +235 6,2,3 -6 5 1 6,5 3651 1 8651 1,3 2651 1,3,8 /8 2 4 1,3,8,2 +347 1,3,4 *177 1,7 2177 7 $ 7 2 49 7,2 3 7 2 49 49 + 49 3 52 49,3 52 Thevaluereturnedis52. Q.217 Writeanalgorithm thatwillsplitacircularly linkedlistintotwocircularlylinkedlists. (7) Ans: Afunctionthatsplitacircularlinkedlistintotwolinkedlistisasfollows: nodeptrsplitlist(nodeptrp) { nodeptrp1,p2,p3; p1=p2=p3=p; if(notp)returnNULL; do{ p3=p2; p2=p2->next;/*advance1*/ p1=p1->next; if(p1)p1=p1->next;/*advance2*/ }while(p1); /*nowform newlistafterp2*/ p3->next=NULL;/*terminate1sthalf*/ returnp2; }/*splitlist*/ Q.218 LetA[n]beanarrayofnnumbers.Designalgorithmstoperform thefollowing operations: Add(i,y):Addthevalueytotheithnumberinthearray Partial-sum(i):returnsthesum ofthefirstinumbersinthearray (4) Ans:

Operation1 add(i,y) { A[i]=A[i]+y; } Operation2 partialsum (i,y) { intsum=0; for(;i>0;i--) sum =sum +A[i]; returnsum; } Q.219 CalculatetheefficiencyofQuicksort. (4) Ans: EfficiencyofQuicksort Assumethatthefilesizenisapowerof2 sayn=2m m=log2n (takinglogonbothsides).................(A) Assumealso thattheproperposition forthepivotalwaysturnsoutto beexact middleofthesubarray.Inthatcase,therewillbeapproxncomparisons(actuallyn-1) onthefirstpass,afterwhichthefileissplitintotwosubfileseachofsizen/2.Eachof them willhaven/2comparisonsandfileisagainsplitinto4fileseachofsizen/4and soonhalvingitm times. Proceedinginthisway:- No.ofcomparisons 1.fileofsizen 1*n=n 2.fileofsizen/2 2*n/2=n 3.fileofsizen/4 4*n/4=n ... ... nfileofsize1 n*1=n Totalno.ofcomparisonsforentiresort =n+n+n+.......+n(m times) =nm =nlog2n (fromA) ThereforetheefficiencyofQuicksortisO(nlog2n). Q.220 Formulateanalgorithm toperform insertionsortonalinkedlist. (8) Ans: SimpleInsertionsortiseasilyadaptabletosinglylinkedlist.Inthismethodthere isanarraylinkofpointers,oneforeachoftheoriginalarrayelements.Initiallylink[i] =i+1for0<=I<n-1andlink[n-1]=-1.Thusthearraycanbethoughtofasalinear linklistpointedto byanexternalpointerfirstinitializedto 0.To insertthekth elementthelinkedlististraverseduntiltheproperpositionforx[k]isfound,oruntil theendofthelistisreached.Atthatpointx[k]canbeinsertedintothelistbymerely adjustingthelistpointerswithoutshiftinganyelementsinthearray.Thisreduces thetimerequiredforinsertionbutnotthetimerequiredforsearchingfortheproper position.ThenumberofreplacementsinthelinkarrayisO(n).

Eachnodefromtheunsortedlinkedlististobedetachedonebyonefrom thefront andattachedtothenewlistpointedbyshead.Whileattaching,thevaluegotstored ineachnodeisconsideredsothatitisinsertedattheproperposition. Shead=head head=headnext Sheadnext=NULL While(head!=NULL) { P=head head=headnext q=Shead while(qinfo<Pinfo&q!NULL) { r=q q=qnext } Pnext=q rnext=P } Q.221 ThefollowingvaluesaretobestoredinaHash-Table: 25,42,96,101,102,162,197,201 Usethe Division method of Hashing with a table size of 11.Use the sequentialmethodforresolvingcollision. (6) Ans: Thegivenvaluesareasfollows:- 25 42 96 101 102 162 197 201 Tablesizeis=11 DivisionmethodofHashing:- H(k)={Hashaddressrangefrom 0tom-1.Key(mod)table-size.} H(25)=3 H(42)=9 H(96)=8 H(101)=2 H(102)=3 H(162)=8 H(197)=10 H(201)=3 TheHashtableisasfollows Hash[0]=[197] Hash[1]=[NULL] Hash[2]=[101] Hash[3]=[25] CollisionOccurred

Hash[4]=[102] Insertedinnextavailableslot Hash[5]=[201] Hash[6]=[NULL] Hash[7]=[NULL] Hash[8]=[96] Hash[9]=[42] Hash[10]=[162] 0 197 1 2 101 3 25 ---102(collision) 4 102 ---201 5 201 6 7 8 96 9 42 10 162 Q.222 Rewriteyoursolutiontopart(b)usingrehashingasthemethodofcollision resolution.Use[(key+3)modtable-size]asrehashfunction. (5) Ans:Rehashfunction[(key+3)modtablesize] H(25)=28mod11 H(42)=45mod11 H(96)=99mod11 H(101)=104mod11 H(102)=105mod11 H(162)=165mod11 H(197)=200mod11 H(201)=204mod11 Thenewlycreatedhashfunctionisasfollows:- Hash[0]=[96] Hash[1]=[42] Hash[2]=[162] Hash[3]=[197] Hash[4]=[NULL] Hash[5]=[101] Hash[6]=[25] Hash[7]=[102] Hash[8]=[201] Hash[9]=[NULL] Hash[10]=[NULL] Q.223 How manyAVLtreesof7nodeswithkeys1,2,3,4,5,6,7arethere? Explainyouranswer. (6) Ans: Step1

Step2 Norebalancingrequired Step3 Step4 Step5 Step6 Step7

Q.224 DescribetheDijkstra’salgorithm forfindingashortestpathinagivengraph. (8) Ans: LetG =(v,e)beasimplegraph.Leta&zbeanytwoverticesofthegraph. SupposeL(x)denotesthelabelofthevertexzwhichrepresentsthelengthofthe shortestpathfrom thevertexatothevertexz.Wijdenotestheweightoftheedge eig=(Vi,Vj) 1.letP=Qwherepisthesetofthoseverticeswhichhavepermanentlabels& T={allverticesofthegraphG} SetL(a)=0,L(x)=∞forallx€T&x≠a 2.SelectthevertexvinTwhichhasthesmallestlabel.Thislabeliscalledthe permanentlabelofv. AlsosetP=PU{v}andT=T-{v} ifv=zthenL(z)isthelengthoftheshortestpathfrom thevertexatozand stop. 3.Ifv≠zthenrevisethelabelsofverticesofTi.e.theverticeswhichdonothave permanentlabels.ThenewlabelofavertexxinTisgivenby L(x)=min{oldL(x),L(v)+w(y,x)} wherew(v,x)istheweightoftheedgejoiningthevertexv&x Ifthereisnodirectedgejoiningv&xthentakew(v,x)=∞ 4.Repeatsteps2and3untilzgetsthepermanentlabel. Q.225 Explainthedifferencebetweendepthfirstandbreadthfirsttraversingtechniques ofagraph. (4) Ans: Depth-firstsearchisdifferentfrom Breadth-firstsearchinthefollowingways: Adepthsearchtraversaltechniquegoestothedeepestlevelofthetreefirst andthenworksupwhileabreadth-firstsearchlooksatallpossiblepathsatthe samedepthbeforeitgoestoadeeperlevel.Whenwecometoadeadendina depth-firstsearch,webackupaslittleaspossible.Wetryanotherroutefrom arecentvertex-therouteontopofourstack.Inabreadth-firstsearch,wewant tobackupasfaraspossibletofindarouteoriginatingfromtheearliestvertices. Sothestackisnotanappropriatestructureforfindinganearlyroutebecauseit keepstrackofthingsintheorderoppositeoftheiroccurrence-thelatestroute isontop.Tokeeptrackofthingsintheorderinwhichtheyhappened,weusea FIFOqueue.Therouteatthefrontofthequeueisaroutefrom anearliervertex; therouteatthebackofthequeueisfrom alatervertex. Q.226 Considerthefollowingundirectedgraphandanswerthefollowingquestions.

Assume thatthe edges areordered alphabetically (i.e.when facing with alternatives,choosetheedgesinalphabeticalorder) (i) Listthenodes(cities)ofthegraphbydepthfirstsearchstarting from Varanasi. (ii) Listthenodes(cities)ofthegraphbybreadthfirstsearchstarting from Calcutta. (8) Ans: (i)Thelistofnodesfrom thegraphbyperformingDepth-First-Searchstarting from Varanasiisasfollows VaranasiKanpurBangaloreCalcuttaDelhiPuneRanchi LucknowTrichi (ii)

Thelistofnodesfrom thegraphbyperformingBreadth-First-Searchstartingfrom Calcuttaisasfollows CalcuttaBangaloreDelhiPune Kanpur RanchiLucknowTrichi Varanasi Q.227 Considerthefollowingfunction F(intn,intm) {ifn<=0ORm<=0thenreturn1elsereturn(F(n-1,m)+F(n,m-1));} Now answerthe followingquestions assuming thatn and m are positive integers. (i) WhatisthevalueofF(n,2),F(5,m),F(3,2),F(n,m)? (ii) HowmanyrecursivecallsaremadetothefunctionF,includingthe originalcallwhenevaluatingF(n,m)? (4) Ans:

Therecursioncontinuestilleveryfunctioncallgetsitsabsolutevalue.Orderis (i) Thevalueof a. F(n,2)=O(n) b. F(5,m)=O(m) c. F(3,2)=O(1). d. F(n,m)=O(n).O(m)=O(n.m). (ii)WhileevaluatingF(n,m),sinceitisoforderO(n,m)sothenumberofrecursive callsrequiredisoftheordernxm. Q.228 Writearecursivefunctionthathasoneparameterwhichisanintegervalue (4) calledx.Thefunctionprintsxasterisksfollowedbyxexclamationpoints. Donotuseanyloops.Donotuseanyvariablesotherthanx. Ans: Therecursivefunctionprintast()fortherequiredtaskisasfollows:- voidprintast(inta) { if(a>0) { printf(\"*\"); a--; printast(a); } if(a!=0) printf(\"!\"); } Q.229 SortthefollowinglistusingselectionSort.Showeachpassofthesort. 45,25,75,15,65,55,95,35 (7)

Ans: Theoriginalarrayis45,25,75,15,65,55,95,35 AfterPass1 AfterPass2 AfterPass3 AfterPass4 AfterPass5 AfterPass6 AfterPass7 Thearrayissortedafter7passesofselectionsort. Q.230 WhatisHashing?CanaperfectHashfunctionbemade?Justifyyouranswer. Explaininbriefthevariousmethodsusedtoresolvecollision. (9)

Ans: Hashing:Hashingprovidesthedirectaccessofrecordfrom thefilenomatter where the record is in the file.This is possible with the help ofahashing functionHwhichmapthekeywiththecorrespondingkeyaddressorlocation.It providesthekey-to-addresstransformation. Noaperfecthashfunctioncannotbemadebecausehashingisnotperfect. Occasionally,acollisionoccurswhentwodifferentkeyshashintothesame hashvalueandareassignedtothesamearrayelement.Programmershave come up with various techniques fordealing with this conflict.Two broad classesofcollisionresolutiontechniquesare:openaddressingandchaining. Openaddressing:Thesimplestwaytoresolveacollisionistostartwiththe hashaddressanddoasequentialsearchthroughthetableforanemptylocation. Theideaistoplacetherecordinthenextavailablepositioninthearray.This methodiscalledlinearprobing.Anemptyrecordisindicatedbyaspecialvalue callednull.Themajordrawbackofthelinearprobemethodisclustering. Chaining:Inthistechnique,insteadofhashingfunctionvalueaslocationweuse itasanindexintoanarrayofpointers.Eachpointeraccessachainthatholds theelementhavingsamelocation. Because twoentries cannot be assigned the same array element,the programmercreatesalinkedlist.Thefirstuser-definedstructureisassignedto thepointerinthearrayelement.Thesecondisn’tassignedtoanyarrayelement andisinsteadlinkedtothefirstuser-definedstructure,therebyformingalinked list. Forexample:inatablesizeof7 42,56botharemappedtoindex0as42%7=0and56%7=0. 25,42,96,101,102,162,197canbemappedasfollows: 012344216210125C102192NULL5696NULLNULLNULLNULLNULL Q.231 DefineaBtreeoforderm. (10) Writealgorithmsto (i) SearchforakeyinB-tree. (ii) InsertakeyinaB-tree. (iii) Deleteakeyfrom aB-tree. Ans: BTreeoforderm Abalancedmultiwaysearchtreeoforderm inwhicheachnonrootnodecontainsat leastm/2keysiscalledaB-Treeoforderm.whereordermeansmaximum numberof sub-trees.

AB-Treeoforderm iseithertheemptytreeoritisanm-waysearchtreeTwiththe followingproperties: (i) TherootofThasatleasttwosubtreesandatmostm subtrees. (ii) AllinternalnodesofT(otherthanitsroot)havebetween[m /2]andm subtrees. (iii)AllexternalnodesofTareatthesamelevel. Algorithm tosearchforakeyinB-treeisasfollows: B-treesearchmakesann-waychoice.Byperformingthelinearsearchinanode, correctchildCiofthatnodeischosen.Oncethevalueisgreaterthanorequaltothe desiredvalue is obtained,the child pointerto the immediate leftofthe value isfollowed.Otherwiserightmostchildpointerisfollowed.Ifdesiredvalueisobtained, thesearchisterminated. B-treesearch(x,k) Thisfunctionsearchesthekeyfrom thegivenB-tree TheDisk_Readoperationindicatesthatallreferencestoagivennodebeprecededbya readoperation. 1.i1 2.While(i≤n[x]andk>keyi[x]) Setii+1 3.If(i<=n[x]andk=keyi[x])then {return(x,i)} 4.If(leaf[x])then returnNIL elseDisk_read(ci[x]) returnB-treesearch(ci[x],k) Algorithm toinsertakeyinB-treeisasfollows: 1. Firstsearchisdonefortheplacewherethenewrecordmustbeput. Asthekeysareinserted,theyaresortedintotheproperorder. 2. Ifthenodecanaccommodatethenewrecord,insertthenewrecord attheappropriatepointersothatnumberofpointersremainsonemorethanthe numberofrecords. 3. Ifthenodeoverflowsbecausethereisanupperboundonthesizeof anode,splittingisrequired.Thenodeissplitintothreeparts;themiddlerecordis passedupwardandinsertedintoparent,leavingtwochildrenbehind.Ifnisodd(n -1keysinfullnodeandthenew targetkey),mediankeyint(n/2)+1isplacedin parentnode,thelowern/2keysareputintheleftleafandthehighern/2keysare putintherightleaf.Ifniseven,wemayhaveleftbiasedorrightbiasedmeans onekeymaybemoreinleftchildorrightchildrespectively. 4. Splittingmaypropagateupthetreebecausetheparent,intowhich splittedrecordisadded,mayoverflowthenitmaybesplit.Iftherootisrequired tobesplit,anewrecordiscreatedwithjusttwochildren. Q.232 Giventhefollowingtree

Showhowthetreewillchangewhenthefollowingstepsareexecutedoneafteranother (6) (i) Key‘i’isdeleted (ii) Key‘v’isdeleted (iii) Key‘t’isdeleted Ans: Thegiventreeis:- (i) Key‘i’isdeleted

(ii) Key‘v’isdeleted (iii) Key‘t’isdeleted Q.233 Writeanalgorithm toreverseasinglylinkedlist. (4) Ans: Thealgorithm toreverseasinglylinklistisasfollows:- reverse(structnode**st) { structnode*p,*q,*r; p=*st; q=NULL; while(p!=NULL) {

r=q; q=p; p=plink; qlink=r; } *st=q; } Q.234 Considera2DarrayascharA[5][6]storedincontiguousmemorylocations startingfrom location1000”incolumnmajororder.Whatwouldtheaddress ofa[i][d]? (2) Ans: ConsideringthegivenchararrayA[5][6]storedincontiguousmemoryincolumn majororder;theaddressofa[i][d]wouldbecalculatedas base(a)+(d*n1+i)*size;wherebase(a)=1000(given). Sinceitisachararraysosize=1andn1isthetotalnoofrows heren1=6(0,1,2,3,4,5,)Substitutingvalueswegettheaddressof A[i][d]=1000+d*6+i Q.235 WhatarepriorityQueues?Howcanpriorityqueuesbeimplemented?Explain inbrief. (4) Ans: PriorityQueues:- Therearesomequeuesinwhichwecaninsertitemsordeleteitemsfrom any positionbasedonsomeproperty.Now,thosequeuesbasedonthepropertyof priorityofthetasktobeprocessedarereferredtoaspriorityqueues. Toimplementapriorityqueuewefirstneedtoidentifydifferentlevelsofpriority andcategorizethem astheleastprioritythroughthemostprioritylevel.After havingidentifiedthedifferentlevelsofpriorityrequired,wethenneedtoclassify eachincomingitem (job)astowhatprioritylevelshouldbeassignedtoit.While creatingthequeues,weneedtocreatenqueuesiftherearenprioritylevels definedinitially.LetsupposetherearethreeprioritylevelsidentifiedasP1,P2,and P3.InthiscasewewouldcreatethreequeuesasQ1,Q2andQ3eachrepresenting prioritylevelsP1,P2,andP3respectively.Noweveryjobwouldhaveaprioritylevel assignedtothem.JobswithprioritylevelasP1willbeinsertedinQ1.Jobswith prioritylevelP2areinsertedinQ2andsoon. Eachqueuewillfollow FIFObehaviorstrictly.Jobsarealwaysremovedfrom the frontendofanyqueue.ElementsinthequeueQ2areremovedonlywhenQ1is emptyandtheelementsofthequeueQ3areonlyremovedwhenQ2isemptyand soon. Q.236 Consideralinkedlistwithnintegers.Eachnodeofthelistisnumbered from‘1’to‘n’.Writeanalgorithm tosplitthislistinto4listssothat firstlistcontainsnodesnumbered1,5, 9,13--- secondlistcontainsnodesnumbered 2,6,10,14--- thirdlistcontainsnodesnumbered3,7,11,15--- andfourth list contains nodes numbered4,8,12,16--- (8)

Ans: Algorithm fortheabovesaidtaskisasfollows:- Letusdenotethepointertoanitem intheoriginallinkedlistasP Thenthedataandconsequentpointerswillbedenotedas P->dataandP->nextrespectively. Weassumethatthefunctionslist1.add(x),list2.add(x),list3.add(x)andlist4.add(x) is defined to insertthe “item x”into thelinked listlist1,list2,list3 and list4 respectively. start seti=1 while(P->next!=NULL) Do If(i%4=1) List1.add(P->data) Elseif(i%4=2) List2.add(P->data) Elseif(i%4=3) List3.add(P->data) Else List4.add(P->data) P=P->next//incrementPtopointtoitsnextlocation i++//incrementitocountthenextnodeinsequence. Done End Q.237 Writearecursivealgorithm tofindGreatestCommonDivisoroftwointegers withthehelpofEuclid’salgorithm,asperthefollowingformula (4) Ans: Recursivealgorithm tofindtheGCDoftwonumbersusingEuclid’salgorithm isas follows; intgcd(n,m) { if(n<m) return(gcd(m,n)); elseif(n>=m &&n%m ==0) return(m); else return(gcd(m,n%m)); } Q.238 Traversethefollowingbinarytreeininorder,preorderandpostorder. (3)

Ans: Thebinarytreetraversalisasfollows:- Preorder 1,5,7,11,9,13,15,17,188,25,27,20 Inorder 11,7,9,5,15,13,17,1,25,27,188,20 Postorder 11,9,7,15,17,13,5,27,25,20,188,1 Q.239 Definethefollowing: (i) Tree(recursivedefination) (ii) Levelofanode. (iii) Heightofatree. (iv) CompleteBinarytree. (v) InternalPathlength. (2+1+1+2+1) Ans: (i)Tree(recursivedefinition) Atreeisafinitesetofoneormorenodessuchthat. (1)Thereisaspeciallydesignatednodecalledtheroot. (2)Theremainingnodesarepartitionedinton>=0disjointsets T1,T2...Tnwhereeachofthesesetsisatree.T1,T2...Tn arecalledthesubtreeoftheroot. (ii)Levelofanode Therootisatlevel0(zero)andthelevelofanynodeis1morethanthelevelof itsparent. (iii)Heightofatree Thelengthofthelongestpathfrom roottoanynodeisknownastheheightof thetree.

(iv)CompleteBinarytree Acompletebinarytreecanbedefinedasabinarytreewhosenonleafnodes havenonemptyleftandrightsubtreeandallleavesareatthesamelevel. (v)InternalPathlength Itis defined as thenumberofnode traversed while moving through one particularnodetoanyothernodeinthetree. Q.240 WhatisanAVLtree?ExplainhowanodecanbeinsertedintoanAVLtree. (6) Ans: AVLTree AnAVLtreeisabinarytreeinwhichthedifferenceinheightsbetweentheleftand therightsubtreeisnotmorethanoneforeverynode. WecaninsertanodeintoanAVLtreebyusingtheinsertionalgorithm forbinary searchtreesinwhichwecomparethekeyofthenew nodewiththatintherootandthen insertthe newnode into the leftsubtree orrightsubtree depending on whetheritis lessthanorgreaterthanthatintheroot.Insertionmayormaynotresultinchangeinthe heightofthetree.Whileinsertingwemusttakecarethatthebalancefactorofanynode notchangestovaluesotherthan0,1and-1.Atreebecomesunbalancedifandonlyif (i)Thenewlyinsertednodeisaleftdescendantofanodethatpreviouslyhada balanceof1. (ii)Thenewlyinsertednodeisarightdescendentofanodethatpreviouslyhada balanceof-1. Ifthebalancefactorofanynodechangesduringinsertionthanoneofthesubtree isrotatedoneormoretimestoensurethatthebalancefactorisrestoredtocorrect values. Q.241DescribeKruskal’salgorithm tofindminimum spanningtrees.

ApplyKruskal’salgorithm fortheabovegraph. (10) Ans: ApplyingKruskal’sAlgorithmstartingfrom thenodea Step1: Startfrom nodea,AddtotreeT Step2: Edge(a,b) cost=6 addtoT Step3: Edge(a,c) cost=5 addtoT Step4: Edge(b,e) cost=13 addtoT Step5: Edge(e,g) cost=8 addtoT

Step6: Edge(g,f) cost=3 addtoT Step7: Edge(f,d) cost=7 addtoT

Thisistheminimum spanningtreeofthegivengraph. Q.242 Differentiatebetween (6) (i)Top-downandBottom-upprogramming? (ii)StructuredandModularprogramming. Ans: (i)Top-downandBottom upprogramming. Topdownmethodisalsoknownasstep-wiserefinement.Heretheproblem is firstdividedintomaintasks.Eachoftheseisdividedintosubtasksandsoon. Thesesubtasksshouldmorepreciselydescribehow thefinalgoalistobe reached.WhereastheBottom-upprogrammingisjusttheoppositeofthetop- downapproach.Inthistechnique,allsmallrelatedtasksaregroupedintoa majortaskandthemaintaskbecomesthemainprogram. (ii)StructuredandModularprogramming. Structuredprogrammingmeansthecollectionofprinciplesandpracticesthat aredirectedtowarddevelopingcorrectprogramswhichareeasytomaintain andeasytounderstand.Itshouldreadlikeasequencefrom beginningtoend insteadofbranchingfrom laterstatementstoearlieronesandbackagain. Whereas in modular programming themodularity of a system can be representedbyahierarchicalstructurewhichhasasinglemainmoduleatlevel 1andgivesabriefdescriptionofthesystem.Atlevel2themainmodulerefers toanumberofsubprogram modulesthegiveamoredetaileddescriptionof thesystem andso on.Animportantaspectinthishierarchicalstructuring processisthedesiretounderstandamoduleatacertainlevelindependentlyof allothermodulesatthesamelevel. Q.243 Howisrecursionhandledinternally.Explainwiththehelpofasuitableexample. (4) Ans: Internally,eachrecursivecalltoafunctionneedstostoretheintermediatevaluesof theparametersandlocalvariablesinaruntimestack.Thegeneralalgorithm forany recursiveprocedurecontainsthefollowingsteps: 1.Savetheparameters,localvariablesandreturnaddress. 2.Ifthebasecriterionhasbeenreached,thenperform thefinalcomputationandgo tostep3,otherwiseperform thepartialcomputationandgotostep1withreduced parametervalues(initiatearecursivecall). 3.Restorethemostrecentlysavedparameters,localvariablesandreturnaddress. Gotothisreturnaddress. Allparameters isaccessed bytheirpositions relative to the top ofthe stack. Wheneverasubroutine is started the variables are pushed onto the stack and wheneveritcompletesexecution,thevariablesarepoppedoffthestack.Forex. considerthefactorialfunction. Factorial(intn) { intx; ifn=0 return(1); x=n-1; return(n*factorial(x)); } lettheinitialcallisY=factorial(4) Atfirsttime,4locationsareputintheruntimestack

And on each subsequentcallsthe intermediate values ofallthese variablesare pushedtilltheconditionreacheswheren=0.andthenthecontentsarepoppedoneby oneandisreturnedtotheplaceofthepreciouscall.Thiscontinuesuntilthecontrolis backtothefirstcall. Q.244Writeanalgorithm toaddtwopolynomialsusinglinkedlist. (12) Ans: Algorithm toaddtwopolynomialsusinglinkedlistisasfollows:- Letpandqbethetwopolynomialsrepresentedbylinkedlists 1.whilepandqarenotnull,repeatstep2. 2.Ifpowersofthetwotermsateequal thenifthetermsdonotcancel theninsertthesum ofthetermsintothesum Polynomial Advancep Advanceq Elseifthepowerofthefirstpolynomial>powerofsecond Theninserttheterm fromfirstpolynomialintosum polynomial Advancep Elseinserttheterm fromsecondpolynomialintosum polynomial Advanceq 3.copytheremainingtermsfrom thenonemptypolynomialintothesum polynomial. Thethirdstepofthealgorithm istobeprocessedtilltheendofthepolynomialshas notbeenreached. Q.245 ExecuteDijkstra’salgorithm onthefollowinggraphwithverticesnumbered1to 6.Thegraphisgivenintheform ofanadjacencylist. i. :(6, 2),(4,7) ii. : (1,3),(3,4) iii. : (5,6) iv. : (2,2)(3,5),(1,5),(5,1) v. : (4,4),(6,3) vi. : (4,3) Here(3,4)invertex2’sadjacencylistmeansthatvertex2hasadirectededgeto vertex3withaweightof4.Assumingthesourcevertextobe2,findthe