北大数据结构上机考题总结(1).doc

1.编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B的一串整数（以-9999为结束标记，整数个数小于1000），计算并以从小到大的次序输出A-B的所有元素(为A或B输入时，同一个数可能出现多次，而A与B的差集中同一个数不能出现多次)。（注：程序的可执行文件名必须是e1.exe）（注：程序的可执行文件名必须是e4.exe）*/#includevoidBubbleSort(intr,intn)/冒泡排序(有小到大)inti,j,k;intexchange;for(i=0;i=i;j-)if(rj+1rj)k=rj+1;rj+1=rj;rj=k;exchange=1;if(!exchange)break;intDisaSameYs(intr,intn)/消除数组r中的重复元素,并返回消除后数组剩余的元素个数intw,x,y;for(w=0;w=n;w+)for(x=w+1;x=n;x+)if(rw=rx)n-;for(y=x;y=n;y+)ry=ry+1;/endforx-;/endif/endfor/endforreturnn;intcha(intm,intn,intl,intCountaa,intCountbb)/求差集inti=0,j=0,k=0;intexch;while(i=Countaa)exch=0;/交换变量为0for(j=0;j=Countbb;j+)/用集合的第一个元素分别和另一个集合的各元素相比较/然后再用第二个元素(直到最后一个元素)和另一个集合的各元素相比较if(mi=nj)/如果相同，交换变量变为1exch=1;break;/endif/endforif(!exch)/如果没有相同的就保存mi到l中lk=mi;k+;i+;/endwhilereturnk;/*voidtestds(intr,intn)/测试消除数组中的重复元素的效果用下列循环输出intz;for(z=0;z=n;z+)printf(%d,rz);printf(n);*/voidmain()inta1000,b1000,c2000;intexchange=0;inti,j,k,CountA,CountB,CountC;printf(inputan);for(i=0;i=1000;i+)scanf(%d,&ai);if(ai=-9999)break;CountA=i-1;BubbleSort(a,CountA);CountA=DisaSameYs(a,CountA);/testds(a,CountA);printf(ninputbn);for(i=0;i=1000;i+)scanf(%d,&bi);if(bi=-9999)break;CountB=i-1;BubbleSort(b,CountB);CountB=DisaSameYs(b,CountB);/testds(b,CountB);CountC=cha(a,b,c,CountA,CountB);printf(nn);for(i=0;i=CountC-1;i+)printf(%d,ci);printf(n);模式匹配#include#includetypedefstruct/intch2000;charch2000;intlength;SeqString;intNaiveStrMatch(SeqStringT,SeqStringP)inti,j,k;intm=P.length;intn=T.length;for(i=0;i=n-m;i+)j=0;k=i;while(jm&T.chk=P.chj)k+;j+;if(j=m)returni;/endforreturn-1;/NaiveStrMatchSeqStringCreatStr(SeqStringR)inti;printf(inputdatan);for(i=0;i2000;i+)/scanf(%d,&R.chi);/if(R.chi=-9999)scanf(%s,&R.chi);if(!(strcmp(&R.chi,-9999)break;R.length=i-1;returnR;voidmain()intn;SeqStringStr1;Str1=CreatStr(Str1);SeqStringStr2;Str2=CreatStr(Str2);n=NaiveStrMatch(Str1,Str2);printf(%dn,n); 2、编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B的一串整数（以-9999为结束标记，整数个数小于1000），计算出A与B的交集，并以由小到大的次序输出A与B的交集中的所有整数（输入整数时，相邻的两个用空格隔开。为A或B输入时，同一个数可能出现多次，而A与B的交集中同一个数不能出现多次）。（注：程序的可执行文件名必须是e2.exe）/注意调试程序时要多输入重复数据调试；本程序是根据青龙提供的程序改编，消除了重复数据的错误！；#include#includevoidBuCountbbleSort(intr,intn)/冒泡排序inti,j,k;intexchange;for(i=0;i=i;j-)if(rj+1rj)k=rj+1;rj+1=rj;rj=k;exchange=1;if(!exchange)break;intBingJi(intm,intn,intl,intCountaa,intCountbb)/求集合的并集inti=0,j=0,k=0;while(i=Countaa&j=Countbb)if(minj)/如果minj)/如果minj则取小的值nj,然后j+;lk=nj;k+;j+;/endelseifelse/如果mi=nj,可以任取一个值，然后i+;j+;lk=mi;k+;i+;j+;/endelse/endwhileif(iCountaa)/如果iCountaa,即数组mi中的元数个数较少，/则把nj中的剩余元素，都付给l。while(jCountbb)/如果jCountbb,即数组ni中的元数个数较少，/则把mj中的剩余元素，都付给l。while(i=Countaa)lk=mi;i+;k+;/endwhile/endifreturnk;/返回生成的数组的元数个数/endBuCountbbleSortintJiaoJi(intm,intn,intl,intCountaa,intCountbb)/求集合的交集/消除数组m中的重复元素intw,x,y;for(w=0;w=Countaa;w+)for(x=w+1;x=Countaa;x+)if(mw=mx)Countaa-;for(y=x;y=Countaa;y+)my=my+1;/endforx-;/endif/endfor/endfor/*/测试消除数组中的重复元素的效果用下列循环输出intz;for(z=0;z=Countaa;z+)printf(%d,mz);printf(n);*/消除结束/求交集inti=0,j=0,k=0;while(i=Countaa)for(j=0;j=Countbb;j+)/用集合的第一个元素分别和另一个集合的各元素相比较/然后再用第二个元素(直到最后一个元素)和另一个集合的各元素相比较if(mi=nj)/如果有相同的就保存到l中，这样同时消掉了n中的重复元素lk=mi;k+;break;/endif/endfori+;/endwhile/求交集结束/returnk;voidmain()inta1000,b1000,c2000;intexchange=0;inti,CountA,CountB,CountC;printf(inputan);for(i=0;i=1000;i+)scanf(%d,&ai);if(ai=-9999)break;/endforCountA=i-1;BuCountbbleSort(a,CountA);/先将集合A排序printf(ninputbn);for(i=0;i=1000;i+)scanf(%d,&bi);if(bi=-9999)break;/endforCountB=i-1;BuCountbbleSort(b,CountB);/集合B排序/CountC=BingJi(a,b,c,CountA,CountB);CountC=JiaoJi(a,b,c,CountA,CountB);printf(nn);for(i=0;i=0且n0。（注：程序的可执行文件名必须是e3.exe）#includetypedefenumFalse,TrueBoolean;intG100100;intn;voidCreatG()/*建立图的邻接矩阵G*/inti,j;printf(Inputthenumberofthenode:);scanf(%d,&n);printf(n);for(i=0;in;i+)for(j=0;jn;j+)Gij=0;doscanf(%d%d,&i,&j);Gij=1;while(i!=-1)&(j!=-1);voidTopSort()/*拓扑排序,输出拓扑序列*/inti,j;intdegree100;/*按照无前驱顶点优先思想,degree存放个节点的入度.*/Booleanvisited100,flag=True;printf(TheTopolgicalOrderasfollow:);for(i=0;in;i+)degreei=0;visitedi=False;printf(n);while(flag=True)for(i=0;in;i+)for(j=0;jn;j+)degreei=Gji+degreei;i=0;while(in)&(degreei!=0)|visitedi=True)i+;/*最先输出入度为0的顶点.*/if(in)/*所有节点均已输出结束,否则说明存在环,无拓扑序列*/printf(%d,i);visitedi=True;for(j=0;jn;j+)Gij=0;degreej=0;elseflag=False;main()CreatG();TopSort(); .编一C程序，它能读入一串整数（以-9999为结束标记）并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数2000）。（注：程序的可执行文件名必须是e4.exe）#includevoidmain()inta2000,i,j,k=0,CountA;printf(inputdatan);for(i=1;i=2001;i+)scanf(%d,&ai);if(ai=-9999)break;CountA=i-1;for(i=2;i=CountA;i+)if(aiai-1)a0=ai;j=i-1;doaj+1=aj;j-;k+;while(a0aj);aj+1=a0;printf(n);for(i=1;in0，其余的值都=0且n,输出图G的拓扑序列。（注：程序的可执行文件名必须是e5.exe） 6.编一C程序，它能读入一串整数（不多于2000，并以-9999为结束标记）及另一整数n，判断n是否在那一串数中，若是，则输出yes及该数在那串整数中的序号（序号从0开始），否则输出no。(输入整数时，相邻的两个用空格隔开)。（注：程序的可执行文件名必须是e6.exe）#includetypedefstructintdata2000;intlength;SeqList;voidmain()inti,k=0,num;SeqLista;printf(inputdatan);for(i=0;i2000;i+)scanf(%d,&a.datai);if(a.datai=-9999)break;a.length=i-1;printf(inputthenumbern);scanf(%d,