北京大学数据结构与算法上机考试

北京大学地球与空间科学学院刘证源1北京大学数据结构与算法模拟上机考试1、出栈序列统计#includestdio.hintN;intStack(intn,intm)//n:待进栈元素个数;m:栈中元素个数{if(n==0)return1;//只能全部出栈if(m==0)returnStack(n-1,m+1);//只能继续进栈returnStack(n-1,m+1)+Stack(n,m-1);}intmain(){intN;scanf(%d,&N);printf(%d\n,Stack(N,0));return0;}2、倒排索引查询#includestdio.h#includestring.hstructList{intdata[102];intrear;}list[2005];intr[2005];voidAdd(intl,intw){list[l].data[++list[l].rear]=w;}intSearch(intl,intw){inti;for(i=0;i=list[l].rear;i++)if(list[l].data[i]==w)return1;return-1;}intmain(){北京大学地球与空间科学学院刘证源2freopen(input.txt,r,stdin);intN,C,c,M,i,j,t,k,s;scanf(%d,&N);for(i=1;i=N;i++)list[i].rear=-1;for(i=1;i=N;i++){scanf(%d,&C);for(j=1;j=C;j++){scanf(%d,&c);Add(c,i);}}scanf(%d,&M);for(i=1;i=M;i++){memset(r,0,sizeof(r));s=0;for(j=1;j=N;j++){scanf(%d,&t);for(k=1;k=2000;k++){if(t==1&&Search(k,j)!=1)r[k]=-1;if(t==-1&&Search(k,j)!=-1)r[k]=-1;}}for(j=1;j=2000;j++)if(r[j]==0)if(s==0){printf(%d,j);s=1;}elseprintf(%d,j);if(s==0)printf(NOTFOUND);printf(\n);}return0;北京大学地球与空间科学学院刘证源3}3、数据筛选#includestdio.hint*heap;intrear=-1;voidswap(int&x,int&y){intt;t=x;x=y;y=t;}voidAdd(intn){intp;heap[++rear]=n;p=rear;while(p0)if(heap[p]heap[(p-1)/2]){swap(heap[p],heap[(p-1)/2]);p=(p-1)/2;}elsebreak;}voidTrans(intn){intp=0;heap[0]=n;while(2*p+1=rear){if(2*p+1==rear&&heap[p]heap[2*p+1])swap(heap[p],heap[2*p+1]);if(heap[p]heap[2*p+1]&&heap[p]heap[2*p+2])if(heap[2*p+1]heap[2*p+2]){swap(heap[p],heap[2*p+1]);p=2*p+1;}else{swap(heap[p],heap[2*p+2]);北京大学地球与空间科学学院刘证源4p=2*p+2;}elseif(heap[p]heap[2*p+1]){swap(heap[p],heap[2*p+1]);p=2*p+1;}elseif(heap[p]heap[2*p+2]){swap(heap[p],heap[2*p+2]);p=2*p+2;}elsebreak;}}intmain(){freopen(input.txt,r,stdin);intn,k,i,a;scanf(%d%d,&n,&k);heap=newint[k+1];for(i=1;i=k;i++){scanf(%d,&a);Add(a);}for(i=k+1;i=n;i++){scanf(%d,&a);if(aheap[0])Trans(a);}printf(%d\n,heap[0]);return0;}4、字符串插入#includestdio.hintmain(){chars[100005],sub[100005];inti,max=0,j;scanf(%s%s,s,sub);北京大学地球与空间科学学院刘证源5for(i=0;s[i]!='\0';i++)if(s[i]max){max=s[i];j=i;}for(i=0;i=j;i++)printf(%c,s[i]);printf(%s,sub);for(i=j+1;s[i]!='\0';i++)printf(%c,s[i]);printf(\n);return0;}5、树的镜面映射#includestdio.hstructTreeNode{chardata;intleft,right,parent;}node[10005];intrear=-1;intN,count=0;intque[10005];intfront=0,tail=-1,tail0;voidPut(inti){que[++tail]=i;}voidNewNode(charc,intp){node[++rear].data=c;node[rear].left=-1;node[rear].parent=p;node[rear].right=-1;}voidCreatTree(intp,ints){charc;intt,i;if(count==N)return;scanf(%c%d,&c,&t);北京大学地球与空间科学学院刘证源6NewNode(c,p);count++;i=rear;if(s==-1)node[p].left=i;elseif(s==1)node[p].right=i;if(t==1)return;CreatTree(i,-1);CreatTree(i,1);}voidBTS(){intp,i;//printf(%c,node[0].data);Put(0);while(front=tail){tail0=tail;for(i=front;i=tail0;i++)if(node[que[i]].data!='$'){p=node[que[i]].left;while(p!=-1){Put(p);p=node[p].right;}}for(i=tail0;i=front;i--)if(node[que[i]].data!='$')if(que[i]==0)printf(%c,node[0].data);elseprintf(%c,node[que[i]].data);front=tail0+1;}printf(\n);}intmain(){freopen(input.txt,r,stdin);inti;北京大学地球与空间科学学院刘证源7scanf(%d\n,&N);CreatTree(-1,0);//for(i=0;i=rear;i++)//{////scanf(%c%d,&c,&t);//printf(%d%c%d%d\n,node[i].left,node[i].data,node[i].parent,node[i].right);//}BTS();return0;}6、丛林中的路#includestdio.hintam[30][30];structEdge{intstart,end,w;}edge[100],min;intrear=-1;intmark[30]={0};constintINF=10000;voidPrim(intn){ints=0,i=0,j,count=1;mark[0]=1;while(countn){for(j=0;jn;j++)if(mark[j]!=1&&am[i][j]!=INF){edge[++rear].start=i;edge[rear].end=j;edge[rear].w=am[i][j];}min.w=INF;for(j=0;j=rear;j++)if(mark[edge[j].end]!=1&&edge[j].wmin.w)min=edge[j];mark[min.end]=1;i=min.end;s+=min.w;count++;}printf(%d\n,s);北京大学地球与空间科学学院刘证源8}intmain(){freopen(input.txt,r,stdin);intn,i,j,k;charu,v;intw;scanf(%d\n,&n);for(i=0;in;i++)for(j=0;jn;j++)if(i==j)am[i][j]=0;elseam[i][j]=INF;for(i=0;in-1;i++){scanf(%c%d,&u,&k);printf(%c,u);for(j=0;jk;j++){scanf(%c%d,&v,&w);printf(%c%d\n,v,w);am[v-'A'][u-'A']=am[u-'A'][v-'A']=w;}}for(i=0;in;i++){for(j=0;jn;j++)printf(%5d,am[i][j]);printf(\n);}Prim(n);return0;}