C_questions

Q.115 DefineastructuretostorethefollowinginformationaboutanemployeeName, Sex(male, female),Marital_status(single, married, divorced or widowed), age.(usingbitfields) (4) Ans: Definitionofastructuretostoreinformationofanemployee: structemployee { charname[20]; unsignedsex: 1; unsignedmartial_status: 1; unsignedage:7; }emp; Q.116 How ismultidimensionalarraysdefinedintermsofanarrayofpointer?What doeseachpointerrepresent? (6) Ans:. Anelementinamultidimensionalarrayliketwo-dimensionalarraycanberepresented bypointerexpressionasfollows: *(*(a+i)+j) Itrepresenttheelementa[i][j].Thebaseaddressofthearrayais&a[0][0]andstarting atthisaddress,thecompilerallocatescontiguousspaceforalltheelementrow-wise. Thefirstelementofsecondrowisimmediatelyafterlastelementoffirstrowandso on. Q.117 Writeaprogram toimplementthestackusinglinkedlist. (8) Ans: ACprogram toimplementthestackusinglinkedlistisgivenbelow: /*Program toimplementstackaslinkedlist*/ #include<stdio.h> #include<conio.h> #include<alloc.h> /*structurecontainingdatapartandlinkpart*/ structnode { intdata; structnode*link; }; voidpush(structnode**,int); intpop(structnode**); voiddelstack(structnode**); voiddisplay(structnode*); voidmain() { structnode*s=NULL; inti; clrscr(); push(&s,1); push(&s,2); push(&s,3); push(&s,4); push(&s,5);

push(&s,6); printf(\"Thestackcurrentlycontains\\n\"); display(s); i=pop(&s); printf(\"\\nItem popped:%d\",i); i=pop(&s); printf(\"\\nItem popped:%d\",i); i=pop(&s); printf(\"\\nItem popped:%d\",i); printf(\"Stackafterdeletingthreeitems\\n\"); display(s); delstack(&s); getch(); } /*addsanewnodetothestackaslinkedlist*/ voidpush(structnode**top,intitem ) { structnode*temp; temp=(structnode*)malloc(sizeof(structnode)); if(temp==NULL) printf(\"\\nStackisfull.\"); temp->data=item ; temp->link=*top; *top=temp; } /*popsanelementfrom thestack*/ intpop(structnode**top) { structnode*temp; intitem ; if(*top==NULL) { printf(\"\\nStackisempty.\"); returnNULL; } temp=*top; item =temp->data; *top=(*top)->link; free(temp); returnitem ; } /*displaysthecontentsofthestack*/ voiddisplay(structnode*q) { printf(\"\\n\"); /*traversetheentirestack*/ while(q!=NULL) { printf(\"%d\",q->data); q=q->link; } } /*deallocatesmemory*/ voiddelstack(structnode**top) { structnode*temp;

if(*top==NULL) return; while(*top!=NULL) { temp=*top; *top=(*top)->link; free(temp); } } Q.118 WriteaCprogram tocalculatethestandarddeviationofanarrayofvalues.The arrayelementsarereadfrom theterminal.Usefunctionstocalculatestandard deviationsandmeanStandardDeviation (10) Ans: ACprogram tocalculatemeanandstandarddeviationofanarrayofvalue: #include<math.h> #include<conio.h> #defineMAXSIZE100 voidmain() { inti,n; float value[MAXSIZE],deviation,sum,sumsqr,mean,variance,stddeviation; sum=sumsqr=n=0; clrscr(); printf(\"\\nInputvalues:input-1toend\\n\"); for(i=1;i<MAXSIZE;i++) { scanf(\"%f\",&value[i]); if(value[i]==-1) break; sum+=value[i]; n+=1; } mean=sum/(float)n; for(i=1;i<=n;i++) { deviation=value[i]-mean; sumsqr+=deviation*deviation; } variance=sumsqr/(float)n; stddeviation=sqrt(variance); printf(\"\\nNumberofitems:%d\\n\",n); printf(\" Mean:%f\\n\",mean); printf(\"StandardDeviation:%f\\n\",stddeviation); getch(); } Q.119 Afileofemployeescontainsdata(eno,nameandsalary)foreachemployeeofa company.Writeaprogram todothefollowing: (i) createthefile (ii) insertioninafile (iii) deletionfrom afile (iv) modificationinafile (12)

Ans: Aprogram toperform creation,insertion,deletionandmodificationinafile: #include<stdio.h> structrec { intempno; charname[25],add[50]; floatsalary; }e; FILE*fp1,*fp2; main() { intch; while(1) { clrscr();printf(\"\\n1.Insert a new Record\\n2.Display All\\n3.Modify One\\n4.DeleteOne\\n5.Exit\\nEnteryourchoice:->\"); scanf(\"%d\",&ch); switch(ch) { case1: insert();break; case2: display();break; case3: modify();break; case4: del();break; case5: exit(); default:printf(\"\\nOutofRange\"); } } getch(); } insert() { if(fp1==NULL) fp1=fopen(\"Employee.txt\",\"w\"); else fp1=fopen(\"Employee.txt\",\"a\"); fseek(fp1,0L,SEEK_END); printf(\"\\nEntertheEmployeeNo.:->\"); flushall(); scanf(\"%d\",&e.empno); printf(\"\\nEnternameofEmployee:->\"); flushall(); gets(e.name); printf(\"\\nEnterAddressofEmployee:->\"); flushall(); gets(e.add); printf(\"\\nEnterSalaryofEmployee:->\"); flushall(); scanf(\"%f\",&e.salary); fwrite(&e,sizeof(e),1,fp1); fclose(fp1); printf(\"\\nRecordAdded.\"); getch(); } display() {

inti=1; fp1=fopen(\"Employee.txt\",\"r\"); if(fp1==NULL) { printf(\"\\nUnabletoopenfile\"); getch(); return; } printf(\"\\nEmp.No\\tName\\tAddress\\tSalary\\n\"); while(1) { i=fread(&e,sizeof(e),1,fp1); if(i==0)break; printf(\"\\n%d\\t%s\\t%s\\t%f\",e.empno,e.name,e.add,e.salary); } fclose(fp1); printf(\"\\nThanks\"); getch(); } del() { charname[25]; intflag=0,i=0,sz=0,count=0; fp1=fopen(\"Employee.txt\",\"r\"); fp2=fopen(\"Temp.Tmp\",\"w\"); if(fp2==NULL) { printf(\"\\nMemoryAllocationnotpossible\"); getch(); return; } if(fp1==NULL) { printf(\"\\nUnabletoopenfile\"); getch(); return; } printf(\"\\nEnterNameofEmployee:->\"); flushall(); gets(name); i=0; while(1) { flag=0; i=fread(&e,sizeof(e),1,fp1); if(i==0) break; if(strcmp(e.name,name)==0) { flag=1; printf(\"\\nThisisthedatauwanttomodify\\n\"); printf(\"%d\\t%s\\t%s\\t%f\\n\",e.empno,e.name,e.add,e.salary); } else { fwrite(&e,sizeof(e),1,fp2);

} } fclose(fp1); fclose(fp2); rename(fp2,fp1); getch(); } modify() { charname[25]; intflag=0,i=0,sz=0,count=0; fp1=fopen(\"Employee.txt\",\"r\"); fp2=fopen(\"Temp.Tmp\",\"w\"); if(fp2==NULL) { printf(\"\\nMemoryAllocationnotpossible\"); getch(); return; } if(fp1==NULL) { printf(\"\\nUnabletoopenfile\"); getch(); return; } printf(\"\\nEnterNameofEmployee:->\"); flushall(); gets(name); i=0; while(1) { flag=0; i=fread(&e,sizeof(e),1,fp1); if(i==0) break; if(strcmp(e.name,name)==0) { flag=1; printf(\"\\nThisisthedatauselectedforchange\\n\"); printf(\"%d\\t%s\\t%s\\t%f\\n\",e.empno,e.name,e.add,e.salary); printf(\"\\nEnternewdata\\n\"); printf(\"\\nEntertheEmployeeNo.:->\"); flushall(); scanf(\"%d\",&e.empno); printf(\"\\nEnternameofEmployee:->\"); flushall(); gets(e.name); printf(\"\\nEnterAddressofEmployee:->\"); flushall(); gets(e.add); printf(\"\\nEnterSalaryofEmployee:->\"); flushall(); scanf(\"%f\",&e.salary); fwrite(&e,sizeof(e),1,fp2); printf(\"\\nRecordModified\");

} else { fwrite(&e,sizeof(e),1,fp2); } } fclose(fp1); fclose(fp2); rename(fp2,fp1); getch(); } Q.120 Whatisinsertion sort? Write a program to sortthe given listofintegers usinginsertionsort. (4) Ans: Insertion Sort:One of the simplest sorting algorithms is the insertion sort.Insertionsortconsistsofn-1passes.Forpassp=2throughn,insertionsort ensuresthattheelementsinpositions1throughpareinsortedorder.Insertion sortmakesuseofthefactthoseelementsinpositions1throughp-1arealready knowntobeinsortedorder.Toinsertarecord,wemustfindtheproperplace whereinsertionistobemade. ACprogram tosortintegersusinginsertionsortisgivenbelow: #include<stdio.h> #include<conio.h> voidmain() { inta[20],i,j,n,val; clrscr(); printf(\"howmanynumbersuwanttoenter:\\n\"); scanf(\"%d\",&n); printf(\"\\nenterthenumbers:\\n\"); for(i=0;i<n;i++) scanf(\"%d\",&a[i]); for(i=1;i<n;i++) { intval=a[i]; for(j=i-1;j>=0&&val<a[j];j--) a[j+1]=a[j]; a[j+1]=val; printf(\"sortedelements:\\n\"); for(i=0;i<n;i++) printf(\"%d\\t\",a[i]); printf(\"\\n\"); getch(); } Q.121 Defineamacro.Writeanestedmacrothatgivestheminimum ofthreevalues. (5) Ans: Macrois a preprocessordirective,also known as macro definition takes the followinggeneralform: #defineidentifierstring Thepre-processordirectivereplaceseveryoccurrenceoftheidentifierinthesource

codebythestring.Thepreprocessordirectivedefinitionisnotterminatedbya semicolon.Forexample #defineCOUNT100willreplacealloccurrencesofCOUNTwith100inthewhole programbeforecompilation. Anestedmacrothatgivesminimum ofthreevaluesislistedbelow: #include<stdio.h> #include<conio.h> #definemin(a,b)((a>b)?b:a) #defineminthree(a,b,c)(min(min(a,b),c)) voidmain() { intx,y,z,w; clrscr(); printf(\"enterthreenumbers:\\n\"); scanf(\"%d%d%d\",&x,&y,&w); z=minthree(x,y,w); printf(\"Minimumofthreevalueis%d\",z); getch(); } Q.122 Writeaprogram tocheckwhetheraboxiscube,rectangleorsemi-rectangle. Prepareatestproceduretotestthisprogram. (5) Ans: ACprogram tocheckifaboxiscube,rectangleorsemi-rectangleis: #include<stdio.h> #include<conio.h> voidmain() { floatlength,width,height; clrscr(); printf(\"enterthedimensionofbox\\n\"); printf(\"Length=\"); scanf(\"%f\",&length); printf(\"width=\"); scanf(\"%f\",&width); printf(\"height=\"); scanf(\"%f\",&height); if(length==width) {if(length==height) printf(\"\\nTheboxisacube\\n\"); else printf(\"\\nTheboxisarectangle\\n\"); } if(width==(0.5*length)) printf(\"\\nTheboxisasemirectangle\\n\"); getch(); } Q.123 A program has been compiled andlinked successfully.When you run this program youfaceoneormoreofthefollowingsituations (i)Program executed,butnooutput (ii)Itproducesincorrectanswers (iii)Itdoesnotstoprunning.

Whatarethepossiblecausesineachcaseandwhatstepswouldyoutaketo correctthem? (6) Ans: Aprogram hasbeencompiledandlinkedsuccessfully. (i) Program executed,butnooutput:thisusuallyhappensduetoruntimeerrorsin theprogram likereferencinganout-of-rangearrayelementormismatchofdata types. (ii)Itproducesincorrectanswers:Thentheremaybelogicalerrorsintheprogram likefailure to considera particularcondition orincorrecttranslation ofthe algorithm intotheprogram orincorrectorderofevaluationofstatementsetc. (iii) Itdoesnotstoprunning:Thishappenswhenwemakeuseofcorrectsyntax statementbutincorrectlogiclike if(code=1)count++; Instead ofusing comparisonoperatorweareusing assignmentwhichis syntacticallycorrectsocount++isalwaysexecutedresultingininfiniteloop. Similarmistakesmayoccurinothercontrolstatements,suchasforandwhile loopthatcausesinfiniteloopsanddoesnotstoprunning. Q.124 Designanalgorithm togeneratenthmemberoftheFibonaccisequence. (8) Ans: Analgorithm togeneratenthmemberofFibonaccisequenceis: 1.start 2.Scanthenumber‘n’uptowhichtheseriestobegenerated. 3.InitializeSum=0,x=0,y=1andi=3. 4.Printxandyasthepartofseries. 5.Repeata-euntili<=n a. CalculateSum=x+y b. PrintSum aspartofseries. c. Assignytox d. Assignsum toy e. i=i+1 6.Stop. Q.125 Writeanalgorithm tosortanarraysofintegersusingbubblesorttechnique. (8) Ans: ACalgorithm tosortanarrayusingbubblesorttechnique: voidmain() { inta[20],i,j,n,c,flag; printf(\"howmanynumbersuwanttoenter:\\n\"); scanf(\"%d\",&n); printf(\"\\nenterthenumbers:\\n\"); for(i=0;i<n;i++) scanf(\"%d\",&a[i]); for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) {

c=a[j]; a[j]=a[j+1]; a[j+1]=c; flag=0; } } if(flag) break; else flag=1; } printf(\"sortedelements:\\n\"); for(i=0;i<n;i++) printf(\"%d\\t\",a[i]); printf(\"\\n\"); } Q.126 Inacompanyanemployeeispaidasunder: (i)HRA=10%ofBasicsalaryandDA=55%ofBasicsalary. (ii)IfhisBasicsalaryisgreaterthan1500thenHRA=500/-andDA=60%ofBasic Salary. WriteaCprogram tofindGrosssalaryoftheemployee. (8) Ans: ACprogram tofindgrosssalaryofanemployeeislistedbelow: voidmain() { floatbasic,hra,da,gross; clrscr(); printf(\"\\nEnterthebasicsalaryoftheemployee:Rs.\"); scanf(\"%f\",&basic); if(basic>1500) { hra=500; da=(60.00/100.00)*basic; } else { hra=(10.00/100.00)*basic; da=(55.00/100.00)*basic; } gross=basic+hra+da; printf(\"\\nTheGrossSalaryis:Rs.%f\",gross); getch(); } Q.127 Whatislooping? (5) Ans:Loopisacontrolstructureusedtoperform repetitiveoperation.Some programsinvolverepeatingasetofinstructioneitheraspecifiednumberof timesoruntilaparticularconditionismet.Thisisdoneusingaloopcontrol

structure.Aprogram loopconsistsoftwoparts:Bodyoftheloopandcontrol statement.The controlstatementtests certain conditions and then decides repeatedexecutionorterminationofstatements.Mostrealprogramscontain someconstructthatloopswithintheprogram,performingrepetitiveactionsona stream ofdataoraregionofmemory. Q.128WhatareMultidimensionalArrays?Usingmultidimensionalarray,writeaprogram in Ctosortalistofnamesinalphabeticalorder. (11) Ans: Multidimensionalarray:Multidimensionalarrayscanbedescribedas\"arraysofarrays\". Forexample,abidimensionalarraycanbeimaginedasabidimensionaltablemadeof elements,allofthem ofasameuniform datatype. intarr[3][5];representsabidimensionalarrayof3per5elementsoftypeint. Similarlyathreedimensionalarraylikeintarr[3][4][2];representanouter arrayof threeelements,eachofwhichisatwodimensionalarrayoffourrows,eachof whichisaonedimensionalarrayoffiveelements. Multidimensionalarraysarenotlimitedtotwoorthreeindices(i.e.,twodimensional orthreedimensional).Theycancontainasmanyindicesasneeded.Howeverthe amountofmemoryneededforanarrayrapidlyincreaseswitheachdimension.For example: chararr[100][365][24][60][60];declarationwouldconsumemorethan3gigabytesof memory. Memorydoesnotcontainrowsandcolumns,sowhetheritisaonedimensionalarray ortwodimensionalarrays,thearrayelementsarestoredlinearlyinonecontinuous chain.Forexample,themultidimensionalarrayisstoredinmemoryjustlikeanone- dimensionalarrayshownbelow: intarr[3][4][2]={ {{1,2},{3,4},{5,6},{7,8}}, {{9,1},{1,2},{3,7},{4,7}}, {{6,1},{18,19},{20,21},{22,23}}, }; 123456789112374761112222 890123 101 117 133 Multidimensionalarraysarejustanabstractionforprogrammers,sincewecan obtainthesameresultswithasimplearrayjustbyputtingafactorbetweenits indices. ACprogram tosortalistofnamesinalphabeticalorder: #include<stdio.h> #include<conio.h> voidmain() { inti,j,n; chara[10][20],b[20]; clrscr(); printf(\"hownamynamesuwanttoenter\"); scanf(\"%d\",&n); printf(\"enternames:\\n\"); for(i=0;i<n;i++) scanf(\"%s\",a[i]); for(i=0;i<=n-2;i++) {

for(j=0;j<n-i-1;j++) { if(cmp(a[j],a[j+1])>0) { cpy(b,a[j]); cpy(a[j],a[j+1]); cpy(a[j+1],b); } } } for(i=0;i<n;i++) printf(\"\\n%s\\n\",a[i]); getch(); } voidcpy(char*b,char*a) { inti=0; while(a[i]!='\\0') { b[i]=a[i]; i++; } b[i]='\\0'; } intcmp(char*a,char*b) { inti=0; while(a[i]!='\\0'||b[i]!='\\0') { if(a[i]>b[i]) break; if(b[i]>a[i]) break; else { i++; } } if(a[i]>b[i]) return(1); if(b[i]>a[i]) return(-1); } Q.129 Whatdoyouunderstandbyscope,lifetimeandvisibilityofthevariables? (6) Ans: Scope,VisibilityandLifetimeofvariables: Thescope ofa variabledeterminestheregion ofthe program in which itis known.Anidentifier's\"visibility\"determinestheportionsoftheprograminwhichit canbereferenced—its\"scope.\"Anidentifierisvisibleonlyinportionsofaprogram encompassedbyits\"scope,\"whichmaybelimitedtothefile,functionorblockin whichitappears. Filescope:Thevariablesandfunctionswithfilescopeappearoutsideanyblockor

listofparametersandisaccessiblefrom anyplaceinthetranslationunitafterits declaration.Identifiernameswithfilescopeareoftencalled\"global\"or\"external.\" Thescopeofaglobalidentifierbeginsatthepointofitsdefinitionordeclaration andterminatesattheendofthetranslationunit.Afunctionhasfilescope. Functionscope:Alabelistheonlykindofidentifierthathasfunctionscope.Alabel isdeclaredimplicitlybyitsuseinastatement.Labelnamesmustbeuniquewithin afunctionhoweveralabelhavingthesamenameintwodifferentfunctionsis allowed. Blockscope:Thevariableswithblockscopeappearinsideablockorwithinthelist offormalparameterdeclarationsinafunctiondefinition.Itisvisibleonlyfrom the pointofits declarationordefinition to the end ofthe block containing its declarationordefinition. Q.130 Whatisthesmallestvalueofnsuchthatanalgorithm whoserunningtimeis runsfasterthananalgorithm whoserunningtimeis onthesame machine?Justifyyouranswer. (6) Ans: Therunningtimeofanalgorithm dependsuponvariouscharacteristicsandslight variationinthecharacteristicsvariestherunningtime.Thealgorithm efficiencyand performanceincomparisontoalternatealgorithm isbestdescribedbytheorderof growthoftherunningtimeofanalgorithm.Supposeonealgorithm foraproblem has timecomplexityasc3n2andanotheralgorithm hasc1n3+c2n2thenitcanbeeasily observed thatthe algorithmwith complexity c3n2willbe fasterthan the one withcomplexityc1n3+c2n2forsufficientlylargervaluesofn.Whateverbethevalueof c1,c2andc3therewillbean‘n’beyondwhichthealgorithm withcomplexityc3n2is fasterthanalgorithm withcomplexityc1n3+c2n2,wereferthisnasbreakevenpoint. Hererunningtimeofalgorithmsare50*n3and3n,ifwecomparebothasshowninthe followingtable,wefindthat10isthesmallestvalueofn(9.8)forwhich50*n3willrun fasterthan3n. n 50*n3 3n 2 400 9 4 3200 81 5 6250 243 9 36450 19683 10 50000 59049 Q.131 Defineasparsematrix.Explainanefficientwayofstoringsparsematrixinthe memoryofacomputer.Writeanalgorithm tofindthetransposeofsparse matrixusingthisrepresentation. (10) Ans: SparseMatrixDefinition:-Amatrixinwhichnumberofzeroentriesaremuchhigher thanthenumberofnonzeroentriesiscalledsparsematrix. Anefficientwayofstoringsparsematrix Thenaturalmethodofrepresentingmatricesinmemoryastwo-dimensionalarrays maynotbesuitableforsparsematrices.Onemaysavespacebystoringonlynonzero entries.ForexamplematrixA(4*4matrix)representedbelow 0 0 0 15 0000

0900 0040 Herethememoryrequiredis16elementsx2bytes=32bytes Theabovematrixcanbewritteninsparsematrixform as: 443 0 3 15 219 324 Herethememoryrequiredis12elementsx2bytes=24bytes wherefirstrowrepresentthedimensionofmatrixandlastcolumntellsthenumberof nonzerovalues;secondrow onwardsitisgivingthepositionandvalueofnonzero number. Analgorithm tofindtransposeofasparsematrixisasbelow: voidtranspose(x,r,y) intx[3][3],y[3][3],r; { inti,j,k,m,n,t,p,q,col; m=x[0][0]; n=x[0][1]; t=x[0][2]; y[0][0]=n; y[0][1]=m; y[0][2]=t; if(t>0) { q=1; for(col=0;col<=n;col++) for(p=1;p<=t;p++) if(x[p][1]==col) { y[q][0]=x[p][1]; y[q][1]=x[p][0]; y[q][2]=x[p][2]; q++; } } return; } Q.132 Whatdoyouunderstandbyrow-majororderandcolumn-majororderofarrays? Derivetheirformulaeforcalculatingtheaddressofanarrayelementintermsof therow-number,column-numberandbaseaddressofarray. (8) Ans: Atwodimensionalarrayisdeclaredsimilartothewaywedeclareaone-dimensional arrayexceptthatwe specifythe numberofelements in both dimensions.For example, intgrades[3][4];

Thefirstbracket([3])tellsthecompilerthatwearedeclaring3pointers,eachpointing toanarray.Wearenottalkingaboutapointervariableorpointerarray.Instead,weare sayingthateachelementofthefirstdimensionofatwodimensionalarrayreference acorrespondingseconddimension.Inthisexample,allthearrayspointedtobythe firstindexare ofthe same size.The second indexcanbe ofvariable size.For example,thepreviousstatementdeclaresatwo-dimensionalarraywherethereare3 elementsinthefirstdimensionand4elementsintheseconddimension. Two-dimensionalarrayisrepresentedinmemoryinfollowingtwoways: 1. Rowmajorrepresentation:Toachievethislinearrepresentation,thefirstrow ofthearrayisstoredinthefirstmemorylocationsreservedforthearray,then thesecondrowandsoon. 2. Columnmajorrepresentation:Herealltheelementsofthecolumnarestored nexttooneanother. Inrowmajorrepresentation,theaddressiscalculatedinatwodimensionalarray asperthefollowingformula Theaddressofa[i][j]=base(a)+(i*m+j)*size wherebase(a)istheaddressofa[0][0],misseconddimensionofarrayaand sizerepresentsizeofthedatatype. Similarlyinacolumnmajorrepresentation,theaddressoftwodimensionalarray iscalculatedasperthefollowingformula Theaddressofa[i][j]=base(a)+(j*n+i)*size Wherebase(a)istheaddressofa[0][0],nisthefirstdimensionofarrayaand sizerepresentsthesizeofthedatatype. Q.133Usingstacks,writeanalgorithm todeterminewhetheraninfixexpressionhas balancedparenthesisornot. (8) Ans: Thealgorithm todeterminewhetheraninfixexpressionhasabalancedparenthesis ornot. Matching=TRUE Clearthestack; Readasymbolfrom inputstring Whilenotendofinputstringandmatchingdo { if(symbol=‘(‘orsymbol=‘{’orsymbol=‘[’) push(symbol,stack) else(ifsymbol=‘)’orsymbol=‘}’orsymbol=‘]’ ) ifstackisempty matching=FALSE write(“morerightparenthesisthanleftparentheses”) else c=pop(stack) matchcandtheinputsymbol ifnotmatched { matching=FALSE write(“error,mismatchedparentheses”) } readthenextinputsymbol } ifstackisemptythen

write(“parenthesesarebalancedproperly”) else write(“moreleftparenthesesthenrightparentheses”) Q.134 Howwillyourepresentamax-heapsequentially?Explainwithanexample.Writean algorithm toinsertanelementtoamax-heapthatisrepresentedsequentially. (8) Ans: Heap: Abinaryheap(Minheap)isacompletebinarytreeinwhicheachnodeotherthanrootis smallerthanits parent.AMaxheapisacompletebinarytreeinwhicheachnodeother thanrootisbiggerthenitsparent. Heapexample:(Maxheap) HeapRepresentation: AHeapcanbe efficientlyrepresentedasanarrayTherootis storedatthefirstplace,i.e. a[1].Thechildrenof thenodeiarelocatedat2*iand2*i+1.Inotherwords, theparentofa nodestoredinithlocationisat[i/2]floor.Thearray representationofaheapisgiveninthe figurebelow. Thisishow max-heapisrepresentedsequentially.Analgorithm tocreateaheapof sizeibyinsertingakeytoaheapofsizei-1wherei>=1isasfollows: s=i; /*findtheparentnodeofiinthearray*/ parent=sdiv2; key[s]=newkey; while(s<>0&&key[parent]<=key[s]) { /*interchangeparentandchild*/ temp=key[parent]; key[parent]=key[s]; key[s]=temp; /*advanceonelevelupinthetree*/ s=parent; parent=sdiv2; } Q.135 Constructanexpressiontreefortheexpression .Show

allthe stepsand give pre-order,in-orderand post-ordertraversals ofthe expressiontreesoformed. (8) Ans: Theexpressiontreeforthegivenformulaisasfollows ThePre-ordertraversalofthetreeis /+*-b^-^b2*4*ac0.5*2a TheInordertraversalofthetreeis -*b+b^2-4*a*c^0.5/2*a ThePost-ordertraversalofthetreeis -b*b2*4ac**/0.5^+2a*/ Q.136 Writeanalgorithm tofindsolutiontotheTowersofHanoiproblem.Explain theworkingofyouralgorithm (with3disks)withdiagrams. (10) Ans: Theaim ofthetowerofHanoiproblem istomovetheinitialndifferentsizeddisks from needleAtoneedleCusingatemporaryneedleB.Theruleisthatnolargerdisk istobeplacedabovethesmallerdiskinanyoftheneedlewhilemovingoratany time,andonlythetopofthediskistobemovedatatimefrom anyneedletoany needle. Wecouldformulatearecursivealgorithm tosolvetheproblem ofHanoitomoven disksfrom AtoCusingBasauxiliary. Step1:Ifn=1,movethesinglediskfrom AtoCandreturn, Step2:Ifn>1,movethetopn-1disksfrom AtoBusingCastemporary. Step3:Movetheremainingdiskfrom AtoC.

Step4:Movethen-1diskdisksfrom BtoC,usingAastemporary. Ifweinplementthisalgorithm inaClanguageprogram,itwouldbelike-- voidhanoi(intn,charinitial,charfinal,chartemp) { if(n==1) { printf(“movedisk1from needle%cto%c\\n”,intial,final); return; } hanoi(n-1,initial,temp,final); printf(“”novediak%dfrom %cto%c“,n,initial,final); hanoi(n-1,temp,final,initial); } voidmain() { intn; printf(“enternoofdisks=“); scanf(“%d”,&n); hanoi(n,‘A’,‘B’,‘C’); } Nowletusworkouttheoutputwhenn=3 Theoutputwillbeasfollows:- Movedisk1from needleAtoneedleC Movedisk2from needleAtoneedleB Movedisk1from needleCtoneedleB Movedisk3from needleAtoneedleC Movedisk1from needleBtoneedleA Movedisk2from needleBtoneedleC Movedisk1from needleAtoneedleC InitiallythediskisatneedleA Movedisk1fromneedleAtoneedleC Movedisk2from needleAtoneedleB

Movedisk1from needleCtoneedleB Movedisk3from needleAtoneedleC Movedisk1from needleBtoneedleA Movedisk2from needleBtoneedleC Movedisk1from needleAtoneedleC

Thusfinallyallthethreedisksisintherequiredpositionafterthecompletionofthe algorithm forn=3asshownabove. Q.137 Whatisrecursion?Arecursiveprocedureshouldhavetwoproperties. Whatarethey?Whattypeofrecursiveprocedurecanbeconvertedintoiterative procedurewithoutusingstack?Explainwithexample. (6) Ans: Recursion:-Recursionisdefinedasatechniqueofdefiningasetoraprocessin termsofitself. There are twoimportantconditions thatmustbe satisfied by anyrecursive procedure.Theyare:- 1.Asmallest,basecasethatisprocessedwithoutrecursionandactsasdecision criterionforstoppingtheprocessofcomputationand 2.Ageneralmethodthatmakesaparticularcasetoreachnearerinsomesenseto thebasecase. Foregtheproblem offindingafactorialofagivennumberbyrecursioncan bewrittenas Factorial(intn) { intx; ifn=0 return(1); x=n-1; return(n*factorial(x)); } inthiscasethecontentsofstackfornandxas[n,x]whenfirstpopoperationis carriedoutisasfollows [4,3] [3,2] [2,1] [1,0] [0,-] topofstack Heretherelationissimpleenoughtoberepresentedinaniterativeloop,and moreoveritcanbedonewithouttakingthehelpofstack.Sosuchkindofrecursive procedurescanalwaysbeconvertedintoaniterativeprocedure. Theiterativesolutionfortheaboveproblem wouldbe Factorial(intn) { intx,fact=1; for(x=1;x<=n;x++) fact=fact*x; returnfact; } Iftherearenostatementsaftertherecursioncall,thatrecursioncanbeconverted toiterativeprogrammeveryeasily.forexample: voidfff(parameters) {

if(condition) { step1 step2 step3 . . fff(parameter) } } whereas,iftherearestatementsafterarecursivecall,auserstackwillberequiredto convertthem intoiterativeprogramme.forexample: voidfff(parameters) { if(condition) { step1 step2 fff(parameters) step3 step4 fff(parameter) } } Q.138 Givean timenon-recursiveprocedurethatreversesasinglylinkedlistofn nodes.Theprocedureshouldnotusemorethanconstantstoragebeyondthatneededforthe listitself. (8) Ans: TheO (n)timenon-recursiveprocedurethatreversesasinglylinkedlistofn nodesisasfollows. 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.139 Devicearepresentationforalistwhereinsertionsanddeletionscanbemade ateitherend.Such a structure is called aDeque (Double Ended Queue). Writefunctionsforinsertinganddeletingateitherend. (8) Ans: Dequeue

ADequeuecanberepresentedasfollows LetthetotalsizeofelementsbeninthisDequeuerepresentedasanarray intarray[n]; Then front=indexofthefirstelement Rear=indexofthelastelement Iffront=rearthenwesupposethattheDequeueisempty TheDequeuegrowsfrom frontsidetilltheindexofthefrontbecomes0and fromrearsidetilltheindexoftherearequalsthearraysize(n-1). NowthefunctionsforinsertingatthefrontendoftheDequeueis:- Insert_front(intdata) { if(front==0) printf(“Dequeueisfullfrom thefrontend”); else { front--; array[front]=data; } } Insertingfrom therearendis:- insert_rear(intdata) { if(rear==n-1) printf(“Dequeueisfullfrom rearend”); else { rear++; array[rear]=data; } } Deletingfrom thefrontend:- intdelete_front() { if(front==rear) printf(“theDequeueisempty”); else return(array[front++]); } Deletingfrom therearend:- intdelete_rear() { if(front==rear) printf(“theDequeueisempty”); else return(array[rear--]);

} Q.140 Theheightofatreeisthelengthofthelongestpathinthetreefrom rootto anyleaf.Writeanalgorithmicfunction,whichtakesthevalueofapointertothe rootofthetree,thencomputesandprintstheheightofthetreeandapathof thatlength. (8) Ans 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.141 TwoBinarytreesaresimilariftheyarebothemptyoriftheyarebothnon-empty andleftandrightsubtreesaresimilar.Writeanalgorithmtodetermineiftwo binarytreesaresimilar. (8) Ans: Weassumetwotreesastree1andtree2.Thealgorithm twodetermineiftwoBinary treesaresimilarornotisasfollows: similar(*tree1,*tree2) { while((tree1!=null)&&(tree2!=null)) { if((tree1->root)==(tree2->root)) similar(tree1->left,tree2->left); similar(tree1->right,tree2->right); } } Q.142 Writean algorithm forBinarysearch.Whatarethe conditionsunderwhich sequentialsearchofalistispreferredoverbinarysearch? (7) Ans: AlgorithmforBinarySearch:- Assumingthata[]isthearrayofitemstobesearched,nisthenumberofitemsinthe arraya,andtargetisthevalueoftheitem thatistobesearched. intbinsearch(inttarget,inta[],intn) { intlow=0; inthigh=1; intmid; while(low<=high) { mid=(low+high)/2; if(target==a[mid]) return(mid); if(target<a[mid]) high=mid-1; else

low=mid+1; } return(-1); } Sequentialsearchispreferredoverbinarysearchinthefollowingconditions:- i).Ifthelistisshortsequentialsearchiseasytowriteandefficientthanbinary search. ii)Ifthelistisunsortedthenbinarysearchcannotbeused,inthatcasewehaveto usesequentialsearch. iii)Ifthelistisunorderedandhaphazardlyconstructed,thelinearsearchmaybethe onlywaytofindanythinginit. Q.143 WorkthroughBinarySearchalgorithm onanorderedfilewiththefollowing keys{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Determine the number of key comparisonsmadewhilesearchingforkeys2,10and15. (9) Ans: Thegivenlistis1,2,3,4,5,6,7,8,9,10,11,12,13,14,15. wheren=14 initiallylow=0, high=14, mid=(low+high)/2=7 Searchingfor2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high) Comparison1: 2<a[mid] sohigh=mid-1=6 andmid=(0+6)/2=3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high) Comparison2: 2<a[mid] sohigh=mid-1=2 andmid=(0+2)/2=1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low)(mid)(high) comparison3: 2=a[mid] Sobythethirdcomparison,wefindtheelementinthelist. Searchingfor10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high) Comparison1: 10>a[mid] solow=mid+1=8andmid=(8+14)/2=11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high) Comparison2: 10<a[mid] sohigh=mid-1=10 andmid=(8+10)/2=9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low)(mid)(high) comparison3: 10=a[mid] Sobythethirdcomparison,wefindtheelementinthelist. Searchingfor15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high) Comparison1: 15>a[mid] solow=mid+1=8andmid=(8+14)/2=11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low) (mid) (high)

Comparison2: 15>a[mid] andmid=(12+14)/2=13 solow=mid+1=12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (low)(mid)(high) comparison3: 15>a[mid] solow=mid+1=14 andmid=(14+14)/2=14 comparison4: 15=a[mid] Sobythefourthcomparison,wefindtheelementinthelist. Q.144 Considerthefollowingundirectedgraph: (i) Findtheadjacencylistrepresentationofthegraph. (ii) Findadepth-firstspanningtreestartingatA. (iii) Findabreadth-firstspanningtreestartingatA. (iv) Findaminimum costspanningtreebyKruskal’salgorithm. (4x3= 12) Ans: (i)Theadjacencylistrepresentationoftheabovegraphis

(ii)Thedepth-firstspanningtreestartingatAis (iii)Thebreadth-firstspanningtreestartingatAis (iv)Theminimum costspanningtreeusingKruskal’sAlgois:-

Q.145 Supposethatagraphhasaminimum spanningtreealreadycomputed.How quicklycantheminimum spanning treebeupdated ifa new vertexand incidentedgesareaddedtoG?(4) Ans:IfthenewvertexandthenewedgesarenotformingacycleontheMST,pickupthe smallestedgefrom thesetofnewedges.Ifthenewvertexandthecorresponding edgesareformingcycleontheMSTbreakthecyclebyremovingtheedgewith largestweight.Thiswillupdatetheminimum spanningtree. Q.146 Writecodetoimplementaqueueusingarraysinwhichinsertionsanddeletions canbemadefrom eitherendofthestructure(suchaqueueiscalleddeque).Your codeshouldbeabletoperform thefollowingoperations (i) Insertelementinadeque (ii) Removeelementfrom adeque (iii) Checkifdequeisempty (iv) Checkifitisfull (v) Initializeit (12) Ans:Herethereare4operations 1.qinsertfront 2.qinsertrear 3.qdeletefront 4.qdeleterear whenfront=rear=-1,queueisemptywhen(rear+1)modsizeofqueue=front queueisfull.Herethequeueistobeusedcircularly. (1)qinsertfront if(front==rear==-1) thenfront=rear=0 q(front)=item elseif(rear+1)modsizeofq=front qisfull,insertionnotpossible elsefront=(front+sizeofq-1)modsizeofq (2)qinsertrear if(front==rear==-1) front=rear=0 q(rear)=item elseif(rear+1)modsizeofqueue+front queueisfull,insertionnotpossible elserear=(rear+1)modesizeofqueue q(rear)=item (3)qdeletefront if(front==rear==-1)

queueisempty elseif(front==rear) k=q(front),front=rear=-1 return(k) elsek=q(front) front=(front+1)modsizeofqueue return(k) (4)qdeleterear if(front==rear==-1) queueisempty elseif(front==rear) k=q(rear),front=rear=-1 return(k) else k=q(rear) rear=(rear+sizeofqueue-1)modsizeofq return(k) Q.147 Whatarestacks?List6differentapplicationsofstacksinacomputersystem. (4) Ans: Astackisanabstractdatatypeinwhichitemsareaddedtoandremovedonly from oneendcalledTOP.Forexample,considerthepileofpapersonyourdesk. Supposeyouaddpapersonlytothetopofthepileorremovethem onlyfrom the topofthepile.Atanypointintime,theonlypaperthatisvisibleistheoneonthe top.This structure is called stack.The six various application ofstack incomputerapplicationare: 1. Conversionofinfixtopostfixnotationandviceversa. 2. Evaluationofarithmeticexpression. 3. Problemsinvolvingrecursionaresolvedefficientlybymakinguseof stack.Forexample-TowerofHanoiproblem 4. Stackisusedtomaintainthereturnaddresswhenevercontrolpasses from onepointtoanotherinaprogram. 5. Tocheckifanexpressionhasbalancednumberofparenthesisornot. 6. Toreversestring. Q.148Writearecursivecodetocomputethesumofsquaresasshownintheseries Ans: m2+(m+1)2+….+n2form,nintegers (8) Arecursivecodetocomputesum ofsquaresfrom m ton. Makeintnaglobalvariablesothatitisnotpassedineveryrecursivecell. intn; voidmain() { intm,sum; clrscr(); printf(\"Valueofm :\"); scanf(\"%d\",&m); printf(\"Valueofn:\"); scanf(\"%d\",&n); sum=sum_recursive(m); printf(\"\\n\\n\\n\\n%d\",sum);

} intsum_recursive(intm) { intsum; if(m==n) return(n*n); else sum=(m*m)+sum_recursive(m+1); printf(\"\\t%d\",sum); returnsum; } Q.149 GivemathematicalrecursivedefinitionofanAVLtree. (4) Ans: AVLtreedefinition: 1.AnemptybinarytreeaisanAVLtree 2.If‘Bt’isthenon-emptybinarytreewith‘BtL’and‘BtR’asitsleftandright-subtrees, then‘Bt’isanAVLtreeifonlyif: · ‘BtL’and‘BtR’areAVLtreesand · hL-hR1wherehLandhRaretheheightsof‘BtL’and‘BtR’respectively. hL-hRiscalledbalancefactorofanode,itsvaluecanbe{-1,0,1} Q.150 Giventhefollowingrecursivecode.Pointoutthepossibleerrorsinthecode. (4) //num isapositiveinteger intfac(intnum) { if(num≤1) return1; else{ returnnum*fac(num+1); } } Ans:Thereisnomisplacedelse.Tworoundbracketsaremissingforthereturn statements.itshouldhavebeen return(1) return(num*fac(num-1)) Note:-itisnot(num+1)but(num-1) Q.151 Whatarethepropertiesofaheap?Distinguishbetweenamaxheapandaminheap. ) Ans: A complete binary tree,each of whose elements contains avalue thatis greaterthanorequaltothevalueofeachofitschildreniscalledaHeap Forexample,aboveisaheapofsize12.Becauseoftheorderpropertyofheap,the

rootnodealwayscontainsthelargestvalueintheheap.Whenwerefertosucha heap,itiscalleda\"maximum heap(maxheap),\"becausetherootnodecontains themaximum valueinthestructure.Similarlywecanalsocreatea\"minimum heap,\" eachofwhoseelementscontainsavaluethatislessthanorequaltothevalueof eachofitschildren Q.152 Transformthearray2861101531211intoaheapwithabottom upmethod (8) Ans: Givenarrayis2,8,6,1,10,15,3,12,11



Finalheap Q.153Whatarethreadedbinarytrees?Explaininorderthreadingusinganexample. (4) Ans: ThreadedBinaryTree:Ifanodeinabinarytreeisnothavingleftorrightchildoritis aleafnodethenthatabsenceofchildnodeisrepresentedbythenullpointers.The spaceoccupiedbythesenullentriescanbeutilizedtostoresomekindofvaluable information.Onepossiblewaytoutilizethisspaceistohavespecialpointerthat pointtonodeshigherin thetreethatisancestors.Thesespecialpointersare calledthreadsandthebinarytreehavingsuchpointersiscalledthreadedbinarytree. Therearemanywaystothreadabinarytreeeachofthesewayseithercorrespond eitherin-orderorpre-ordertraversalofT.AThreadedBinaryTreeisabinarytreein whicheverynodethatdoesnothavearightchildhasaTHREAD(inactualsense,a link)to itsINORDER successor.Bydoingthisthreadingweavoidtherecursive methodoftraversingaTree,whichmakesuseofstacksandconsumesalotof memoryandtime.

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. Q.154 Writeanalgorithm toimplementDepth-firstsearch?How isDepth-firstsearch differentfrom Breadth-firstsearch? (10) Ans: DepthFirstSearchAlgorithm Analgorithm thatdoesdepthfirstsearchisgivenbelow: structnode { intdata; structnode*next; }; intvisited[MAX]; voiddfs(intv,structnode**p) { structnode*q; visited[v-1]=TRUE; printf(\"%d\\t\",v); q=*(p+v-1); while(q!=NULL) { if(visited[q->data-1]==FALSE) dfs(q->data,p); else q=q->next; }

} Depth-firstsearchisdifferentfrom Breadth-firstsearchinthefollowingways: Adepthsearchtraversaltechniquegoestothedeepestlevelofthetreefirstandthen worksup while a breadth-firstsearch looks atallpossible paths atthe same depthbeforeitgoestoadeeperlevel.Whenwecometoadeadendinadepth- firstsearch,webackupaslittleaspossible.Wetryanotherroutefrom arecentvertex- therouteontopofourstack.Inabreadth-firstsearch,wewanttobackupasfaras possibletofindarouteoriginatingfromtheearliestvertices.Sothestackisnotan appropriatestructureforfindinganearlyroutebecauseitkeepstrackofthingsinthe orderoppositeoftheiroccurrence-thelatestrouteisontop.Tokeeptrackofthings intheorderinwhichtheyhappened,weuseaFIFOqueue.Therouteatthefrontofthe queueisaroutefrom anearliervertex;therouteatthebackofthequeueisfrom a latervertex. Q.155Representthefollowinggraphas (i)Adjacencylist (ii)Adjacencymatrix (iii)Incidencematrix (6) Ans: Thegivengraphis– Therepresentationoftheabovegraphisasfollows:- (i) AdjacencyList:- g

(ii) AdjacencyMatrix:- (iii) IncidenceMatrix:-Thisistheincidencematrixforanundirectedgroup. Fordirectedgraphs,thevertexfromwhereanedgeisoriginatingwillhave+1 andthevertexwheretheedgeisreachingwillhaveavalue-1. Restoftheentriesarezero.

Q.156 DefineB-treeoforderm?WhenisitpreferredtouseB-trees? (4) Ans: A B-TreeoforderM iseithertheemptytreeoritisanM-waysearchtreeTwith thefollowingproperties: (i) TherootofThasatleasttwosubtreesandatmostM subtrees. (ii) AllinternalnodesofT(otherthanitsroot)havebetween[M /2]and M subtrees. (iii)AllexternalnodesofTareatthesamelevel. JustasAVLtreesarebalancedbinarysearchtrees,B-treesarebalancedM-way search trees.Byimposing a balancecondition,theshape ofan AVL tree is constrainedinawaywhichguaranteesthatthesearch,insertion,andwithdrawal operationsareallO(logn),wherenisthenumberofitemsinthetree.Theshapes ofB-Treesareconstrainedforthesamereasonsandwiththesameeffect. Q.157Writeanalgorithm tosearchakeyinaB-tree?Whatistheworstcaseofsearchingin aB-tree?ListthepossiblesituationsthatcanoccurwhileinsertingakeyinaB-tree? (8) Ans: B-treesearchmakesann-waychoice.Byperformingthelinearsearchinanode, correctchildCiofthatnodeischosen.Oncethevalueisgreaterthanorequalto thedesiredvalueisobtained,thechildpointertotheimmediateleftofthevalue isfollowed.Otherwise rightmostchild pointerisfollowed.Ifdesired value is obtained,thesearchisterminated. B-treesearch(x,k)/*Thisfunctionsearchesthekeyfrom thegivenB-tree*/ The Disk_Readoperation indicates thatallreferences to a given node be precededbyareadoperation. 1. Seti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) TheworstcaseofsearchingiswhenaB-treehasthesmallestallowable numberofpointerspernon-rootmade,q=[m/2],thesearchhastoreacha leaf(eitherforasuccessfuloranunsuccessfulsearch) Therearethreecommonsimilaritiesthatareencounteredwheninsertinga keyinaB-tree. 1) Akeyisplacedinaleafthatstillhassomeroom. 2) Theleafinwhichthekeyshouldbeplacedisfull.Inthiscase,theleafis split,creatinganewleafandhalfofthekeysaremovedfrom thefullleafto thenew leaf.Butthenew leafhastobeincorporatedintotheB-tree.The lastkeyoftheoldleafismovedtotheparentandapointertothenewleafis placedintheparentaswell.Thesameprocedurecanberepeatedforeach internalnodeoftheB-tree.Suchasplitensuresthateachleafneverhasless than[m/2]-1keys. 3) AspecialcasearisesiftherootoftheB-treeisfull.Inthiscase,anewroot andanewsiblingoftheexistingroothastobecreated.Thissplitresultsin

twonewnodesintheB-tree. Q.158 Whatisthecomplexityofthefollowingcode? (4) intcounter=0; for(i=0;i<n;i++) for(j=0;j<n*n;j++) counter++; Ans: ThecomplexityofgivencodeisO(n2). Q.159Showunderwhatorderofinput,theinsertionsortwillhaveworst-caseandbest- casesituationsforsortingtheset{142,543,123,65,453,879,572,434}. (8) Ans: 543 123 65 453 879 572 Thegivenlistis 142 Asweknow thatinsertionsortisbasedontheideaofinsertingrecordsinto anexisting sorted file.To inserta record,we mustfind the properplace for therecordtobeinsertedandthisrequiressearchingthelist. Aninsertionsortwillhavetheworst-casewhenthelistisreverselysortedi.e.ina decreasingorder.Sofortheabovegivenlisttheinsertionsortexhibitsitsworse casewhenthelistisinfollowingorder 879 572 543 453 434 142 123 65 Againsinceitisthepropertyoftheinsertion sortthatitsearchesforthe correctpositioninthelistforanelement,so thistechniqueexhibitsitsbest casecomputingwhenthelistisalreadysortedinascendingorderasgivenbelow. 65 123 142 434 453 543 572 879 Q.160 Explainhow MergeSortsortsthefollowingsequenceofnumbersusinga diagram {142,543,123,65,453,879,572,434}. (8) Ans: SortingusingMergeSort Thegivensequenceofnumbersis:- Original [142] [543] [123] [65] [453] [879] [572] Sequence [142 543] [65 123] [453 879] [434 [434] [65 123 142 543] [434 453 572 Passone [65 123 142 434 453 543 572 [572 Passtwo 879] Passthree

[879 Thisnumbersequenceissortedinthreepassesusingmergesort. Q.161 Givenastacksandaqueueq,show thecontentsofeachaftertheindicated operations.Thestartingcontentsofsandqareshown.Ifanoperationwould resultinanerror,write“error”andassumethecontentsofsandqdonotchange. Ifthereisnochangeotherwise,leavethecellblankorusedittomarks(”). (8) Operation Contentsofstacks Contentsofqueueq Start Top bottom front rear s.pop() empty 2,4 s.push(3) q.add(5) s.push(q.peek()) q.add(s.peek()) q.add(s.pop()) s.push(s.pop()) q.add(q.remove()) Ans: pop():Removinganelementfromtopofthesatck push(element):insertingelementonthetopofstack add(element):insertingelementfrom rearofthequeue remove():removingelementfrom frontofthequeue peek():readingfrom thefrontofthequeue. Wehaveleftthecellsblankwherethereisnochangefrom thepreviousstate. Operation ContentsofStack Contentofqueueq Top bottom Front rear start empty 2,4 s.pop() error -do- s.push(3) 3 -do- q.add(5) -do- 2,4,5 s.push(q.peek()) 2,3 -do- q.add(s.peek()) -do- 2,4,5,2 q.add(s.pop()) 3 2,4,5,2,2 s.push(s.pop()) -do- -do- q.add(q.remove()) -do- 4,5,2,2,2 Q.162 Ifxisapointertoanodeinadoublylinkedlist,thenx->previsthepointertothe nodebeforeitandx->nextisthepointertothenodeafterit. Whatdoesthispairofstatements,executedinorder,do? (x->next)->prev=x->prev; (x->prev)->next=x->next; Ifwethenexecutethispairofstatements(afterexecutingthefirstpairofstatements), whathappens? (x->next)->prev=x; (x->prev)->next=x; (4)

Ans: Intheabovegivencondition,ifthefollowing (x->next)->prev=x->prev; (x->prev)-next=x->next; statementsareexecutedthentheresultinglinkedlistwillnolongerhavexasoneof itselementsi.e.theelementxgetsdeletedfrom thedoublylinkedlist. Now,afterexecutingtheabovepairofstatements;ifweexecutethefollowingpair i.e.- (x->next)->prev=x; (x->prev)->next=x; thenthiscausestheelementxtobecomeapartofthelinkedlistagain(i.e.itgets insertedagain)andatthesamepositionasbefore. Q.163 Consideraninsertionofthekey=222into thehashtableshowninthe figure.Calculateandindicatethesequenceoftableentriesthatwouldbe probedandthefinallocationoftheinsertionforthekeyforlinearprobing (8) andquadraticprobingmethod.Thehashfunctionish(y)=ymod10,sofor thekey=222,h(x)=2mod10.Inbothcasesstartwiththesameinitial table.Examplecalculationgivenatindex2 0 1 2 152 h(222)=2mod10 3 53 4 5 75 6 136 7 27 8 9 999 Ans: LinearProbing: i. Initiallyalllocationsmarked‘empty’ ii. Whennewitemsarestored,filledlocationsmarked‘full’ iii. Incaseofcollisions,newcomersarestoredatthenextavailable location,foundviaprobingbyincrementingthepointer(modn)untileitheran

emptylocationisfoundorstartingpointisreached. Sointhegivencasewehave222mod10=2,index2isprobed.Sinceitis alreadyfilledsonewcomerwillgotothenextavailablelocationthatisindex4. Rehashing: i.Thecollisionkeyismovetotheconsiderabledistancefromthe initialcollisionwhen thehashingfunctioncomputethevaluethenthe quadraticprobingworkasfollows (Hashvalue+12)modtablesize ii.Ifthereisacollision,takethesecondhashfunctionas (Hashvalue+22)modtablesizeandsoon. iii.The probability that two key values will map to the sameaddresswithtwodifferent hashfunctionsisverylow. Sointhegivencase,wesee222+12mod10=3thereiscollision;Usenext hashfunction. 222+22mod10=222+4=226mod10=6,thereiscollision 222+32mod10=222+9=231mod10=1sonewcomercanbe insertedat index1. Q.164 UsingDijkstra’smethodfindaspanningtreeofthefollowinggraph. (8) abcefdg65913167831512 Ans: Disjkstraalgorithm MethodisneverusedforfindingMinimum-spanningtree Minimum-spanning tree tree=null; edges=anunsortedsequenceofalledgesofgraph; forj=1toE addejtotree; Ifthereiscycleintree Removeanedgewithmaximum weightfrom thisonlycycle. Thespanningtreeforgivengraphisgivenbelow: Step1

Step2 Step3 Step4 Step5 Step6

Sincetheaboverepresentationcreatesacyclesowedeletetheedgehavingthe highestweightinthecycleandthenewrepresentationwouldbeasfollows:- Step7 Step8 Step9

Theaboverepresentationcreatescyclesowe’lldeletetheedgehavingthehighest weightasshownbelow. Step10 Q.165 Whatare the three differentways ofrepresenting a polynomialusing arrays?Representthefollowingpolynomialsusinganythreedifferentmethods andcomparetheiradvantagesanddisadvantages. (i) (ii) (8) Ans: AgeneralpolynomialA(x)canbewrittenasanxn+an-1xn-1+…+a1x+a0where an0thenwecanrepresentA(x) 1.Asanorderedlistofcoefficientsusingaonedimensionalarrayoflengthn+2, A=(n,an,an-1,…,a1,a0),the firstelementis thedegree ofA followed byn+1 coefficientsin orderofdecreasing exponent.So the given polynomialcan be representedas i. (5,7,-8,5,1,2,15) ii. (100,3,0,0,0,0…(45times),-5,0,0,0…(55times),-10) Advantage of this method is simplealgorithms for addition and multiplicationaswehaveavoidedtheneedtoexplicitlystoretheexponentofeach

term.Howeverthereisamajordisadvantageofthismethodandthatiswastageof memoryforcertainpolynomiallikeexample(ii)becausewearestoringmorezero valuesthannon-zerovalues. 2. Asan ordered listwherewe keep onlynon-zero coefficientalong with their exponentlike(m,em-1,bm-1,em-2,bm-2,…,e0,b0)wherefirstentryisthenumberof nonzeroterms,thenforeachterm therearetwoentriesrepresentinganexponent- coefficientpair.Sothegivenpolynomialcanberepresentedas i.(6,5,7,4,-8,3,5,2,1,1,2,0,15) ii.(3,100,3,55,-5,0,-10) Thismethod issolvesourproblem ofwasted memorylikewhathappened in example2. Q.166 Writean algorithm to evaluate the following polynomial.The numberof additionsand multiplicationstakenshouldbe5. (8) Ans: ThegivenpolynomialcanbeevaluatedusingHormer’sruleas 9x5-10x4+6x3+5x2-10x+15 ≡x4[9x-10]+6x3+5x2-10x+15 ≡x3[x[9x-10]+6x]+5x2-10x+15 ≡x2[x[x[9x-10]+6]+5]-10x+15 ≡x[x[x[x[9x-10]+6]+5]-10x+15 ≡x[x[x[x][9x-10]+6]+5]-10]+15 ≡0[5] Q.167 LetPbeapointertoacircularlylinkedlist.Showhowthislistmaybeusedas aqueue.Thatis,writealgorithmstoaddanddeleteelements.Specifythe valueforPwhenthequeueisempty. (10) Ans:Externalpointershould alwayspointto thelastnode ofthe circularlylinked list.Thenboththeinsertionanddeletionfrom thequeuecanbedoneinO(1)time. Toaddanewnodex(insertanewelementinthequeue) x next=P next P next=x P=x Todeleteanode(Deletingfrontelementfrom queue) x=P next P next=x next return(x)

Q.168 Giveanalgorithm forasinglylinkedlist,whichreversesthedirectionofthe links. (6) Ans: Thealgorithm toreversethedirectionofasinglylinklistisasfollows: 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.169 Supposethatwehavenumbersbetween1and1000inaBinarySearchTreeand wanttosearchforthenumber363.Whichofthefollowingsequencescouldnot bethesequenceofnodesexamined?Explainyouranswer. (i) 2,252,401,398,330,344,397,363 (ii) 924,220,911,244,898,258,362,363 (iii) 925,202,911,240,912,245,363 (iv) 2,399,387,219,266,382,381,278,363 (v) 935,278,347,621,299,392,358,363 (10) Ans: (i)Thisisavalidrepresentationofsequence. (ii)Thisisalsoavalidrepresentationofsequence. (iii)Thiscouldnotbethesequencesince240isencounteredafter911soitmustbe itsleftchild,andanyothernodehenceforthmustbelessthan911(parent).But thenode 912 breaksthissequence,which is greaterthan 911 and lieson the leftsubtreeof911,whichviolatesthebasicruleofaBinarySearchTree. (iv)Thisisalsoavalidrepresentationofsequence. (v)Thiscouldnotbeavalidsequencesince621isencounteredafter347so621 mustbe its rightchild,and anyothernode henceforth mustbe greaterthan 347(parent).Butthissequenceisbrokenbythenode299<347andliesontheright subtreeof347whichviolatesthebasicruleofaBinarySearchTree. Q.170 ProfessorBanyan thinks he has discovered a remarkable propertyofbinary searchtrees.SupposethatthesearchforkeykinaBSTendsupinleaf.Consider threesets(1)setA,thekeystotheleftofthesearchpath,(2)setBthekeyson thesearch path and (3)setC,the keys on the rightofthe search path. ProfessorBanyan claims thatany three keys must satisy .Is his claim true?Otherwise give a counterexample to theprofessor’sclaim. (3) Ans: ProfessorBanyanclaim iscompletelywrong.

Theclaim ofprofessorBanyaniswrong.Counterexampleisgivenbelow. Letthekeytobesearchedis70then: (3) SetA={45,55},B={40,50,60,70}andC={} Hereisveryclearthat45≤40OR 55≤50 Q.171 DrawBSTsofheight2and3onthesetofkeys{1,4,5,10,16,17,21}. Ans: TheBSTofheight2is: TheBSTofheight3is: Q.172 Whydon’tweallowaminimum degreeoft=1foraB-tree? (2) Ans: AccordingtothedefinitionofB-Tree,aB-Treeofordernmeansthateachnodein thetreehasamaximum ofn-1keysandnsubtrees.ThusaB-Treeoforder1will havemaximum 0keys,i.e.nonodecanhaveanykeyssosuchatreeisnotpossible andhencewecan’tallowaminimum degreeoft=1foraB-Tree. Q.173 ShowalllegalB-Treesofminimum degree3thatrepresent{1,2,3,4,5,6}. (4)

Ans: B-Treesofminimum degree3areasfollows: [1] [2] [3] Q.174 Showtheresultofinsertingthekeys4,19,17,11,3,12,8,20,22,23,13,18,14, 16,1,2,24,25,26,5inorderintoanemptyB-Treeofdegree3.Onlydrawtheconfigurations ofthetreejustbeforesomenodemustsplit,andalsodrawthefinalconfiguration. (10) Ans: 4,19 17,11 3,12

8,20 22,23,13,18 14,16,1 2

24,25 26 Finally5isinserted Theaboveisthefinaltreeformedafterinsertingalltheelementsgiveninthequestion. Q.175 Writedownthealgorithm forquicksort. (8) Ans: Thealgorithm forquicksortisasfollows: voidquicksort(inta[],intlower,intupper) { inti;

if(upper>lower) { i=split(a,lower,upper); quicksort(a,lower,i-1); quicksort(a,i+1,upper); } } intsplit(inta[],intlower,intupper) { inti,p,q,t; p=lower+1; q=upper; i=a[lower]; while(q>=p) { while(a[p]<i) p++; while(a[q]>i) q--; if(q>p) { t=a[p]; a[p]=a[q]; a[q]=t; } } t=a[lower]; a[lower]=a[q]; a[q]=t; returnq; } Q.176 Showhowquicksortsortsthefollowingsequencesofkeys: (7) 5,5,8,3,4,3,2 Ans: Thegivendataelementtobesortedusingquicksortis 5 5 83 4 32 Choosingpivot5(Pass1) (2)58343(5) 25(5)343(8) 25(3)34(5)8 choosing2aspivot(pass2) (2)5334(58) choosing5aspivot(pass3) (2)(3345)(58) Pass(4),(5)and(6)willnotchangethesublist Q.177 Onwhich inputdata does the algorithm quick sortexhibitits worst- casebehaviour? (1) Ans: TheQuickSorttechniqueexhibitsitsworst-casebehaviorwhentheinputdatais “AlreadyCompletelySorted”.