程序设计题型

程序设计题型PAGE1PAGE31、输出图形(本题100分) 22、旋转数字(本题100分) 33、求和(本题100分) 54、多项式相乘 75、二叉树 106、二叉树1 147、哈夫曼树及编码（100分） 168、哈夫曼树、编码及译码（100分） 199、判定连通图（100分） 2110、LeastTime(最短时间，100分) 2411、取序号判定素数 2612、名次与分数 2813、快速排序（100分） 3214、堆排序（100分） 3315、归并排序（100分） 3516、基数排序（100分） 3717、表达式求值 4018、取数相加 4219、大整数排序 45程序设计题型全文共51页，当前为第1页。程序设计题型全文共51页，当前为第1页。1、输出图形(本题100分)(graph.cpp)【题目描述】编写程序打印n行如下图形，其中1≤n≤26。n=4输出图形如下：DDCDDCBCDDCBABCD【输入】输入文件graph.in包含1个整数。【输出】输出文件graph.out。【输入输出样例1】graph.ingraph.out4DDCDDCBCDDCBABCD#include<iostream>usingnamespacestd;intmain(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); inti,j,n; cin>>n; for(j=1;j<=n;j++) { for(i=1;i<=n-j;i++) cout<<""; for(i=1;i<=j;i++) cout<<(char)('A'+n-i); for(i=1;i<=j-1;i++) cout<<(char)('A'+n+i-j); cout<<endl; } return0;程序设计题型全文共51页，当前为第2页。}程序设计题型全文共51页，当前为第2页。2、旋转数字(本题100分)【题目描述】编写程序打印n行如下菱形图形（1≤n≤99），图形有n行n列个整数，图形从第1行的中间开始，数字分别是1，2，……n*n-1，n*n，并且顺时针向中间转入，如果1个数据项宽度不足n*n位，用0补足到n*n位。提醒：图案中没有数字的地方用空格填满，每行最后一个数字后面没有多余的空格。【输入】输入文件rotation.in包含1个整数n。【输出】输出文件rotation.out是一个菱形图形，图形从第1行的中间开始，数字分别是n*n，n*n-1，n*n-2，……1，并且顺时针向中间转入。【输入输出样例1】例如n=7，输出：01240223250322402604213941270520384842280619374749432907183646443008173545310916343210153311141213【限制】1≤n≤99【提示】 m=4 i=15;.printf("%0*d",m,i);//这里用*表示系数待定，m即为指定的宽度//上面语句输出“0015”，数据宽度为4，不足4位，前补0printf("%*c",m,‘‘);//左边语句输出“”，即输出4个空格#include"stdio.h"constintN0=2*100-1+10;inta[N0][N0]={0};structnode{ introw,col;}dir[4]={{1,1},{1,-1},{-1,-1},{-1,1}};程序设计题型全文共51页，当前为第3页。intmain()程序设计题型全文共51页，当前为第3页。{ inti,j,n; introw,col,row1,col1,d,m=0; freopen("rotation.in","r",stdin); freopen("rotation.out","w",stdout); scanf("%d",&n); row=1; col=n; d=0; intt=n*n; while(t!=0) { m++; t/=10; } for(i=1;i<=n*n;i++) { a[row][col]=i; row1=row+dir[d].row; col1=col+dir[d].col; if(row1<1||col1<1||row1>2*n-1||col1>2*n-1 ||a[row1][col1]!=0) { d=(d+1)%4; row1=row+dir[d].row; col1=col+dir[d].col; } row=row1; col=col1; } for(i=1;i<=2*n-1;i++) { for(j=1;j<=2*n-1;j++) if(a[i][j]!=0) printf("%0*d",m,a[i][j]); else if(i<=n&&j<n+i||i>n&&j<3*n-i)printf("%*c",m,''); printf("\n"); } return0;}3、求和(本题100分)（total.cpp）【问题描述】程序设计题型全文共51页，当前为第4页。有1个n×n的矩阵，从左上到右下称为主斜线（倾角135º），从右上到左下称为次斜线（倾角45º），在主斜线上最大，次斜线上最小的元素称为该矩阵的斜线鞍点，求出该矩阵所有斜线鞍点的和。程序设计题型全文共51页，当前为第4页。如5×5的矩阵：3259810441211286761457191221335633536789019次斜线主斜线元素7为上面矩阵的一个斜线鞍点,元素10和19也是上面矩阵的斜线鞍点。【输入】输入文件total.in第一行是一个整数n(（1≤n≤100）)，接下去是n行×n列的矩阵，矩阵的每个元素都是整数。【输出】输出文件total.out也只有1个整数，即该矩阵所有斜线鞍点的和（0≤和≤1010）。【输入输出样例1】otal.out5325981044121128676145719122133563353678901936#include<stdio.h>#defineNO100intmain(){ freopen("total.in","r",stdin); freopen("total.out","w",stdout); inti,j,x,y,max,min,n=0,sum=0; scanf("%d",&n); int**a=newint*[n]; i=-1; while(++i<n) { a[i]=newint[n]; j=-1; while(++j<n)scanf("%d",a[i]+j); } i=-1; while(++i<n) { j=-1;程序设计题型全文共51页，当前为第5页。 while(++j<n)程序设计题型全文共51页，当前为第5页。 { x=i,y=j; max=1,min=1; while(x>0&&y>0){x--;y--;} while(x<n&&y<n) { if(a[x][y]>a[i][j]) { max=0; break; } x++;y++; } x=i,y=j; while(x>0&&y<n-1){x--;y++;} while(x<n&&y>=0) { if(a[x][y]<a[i][j]) { min=0; break; } x++,y--; } if(!max||!min)continue; elsesum+=a[i][j]; } } printf("%d\n",sum); i=-1; while(++i<n)delete[]a[i]; delete[]a; return0;}4、多项式相乘(conv.cpp/c)【题目描述】编程实现若干个多项式相乘。多项式的输入输出格式为：系数在前，指数在后，各项按指数递增排列，每个多项式输入时以两个0结束。系数为0的项不输出。例如：1+4X3-9X5输入格式为：1001024304-9500或者1043-9500，其输出只能是：程序设计题型全文共51页，当前为第6页。1043-95程序设计题型全文共51页，当前为第6页。【输入】输入文件conv.in每行为一个多项式，多项式输入时以两个0结束。数据为若干行的多项式，例如：10110010-1100101200表示（1+x)(1-x)(1+x2)【输出】输出文件conv.out包含1行,为上述多项式相乘结果。上例的输出为：10-14表示1-x4【输入输出样例1】conv.inconv.out10110010-110010120010-14【数据限制】所有系数、指数均为整数（int类型）#include"stdio.h"typedefstructnode{ intc,e; structnode*next;}ND;ND*createLink(){ ND*head,*p; head=p=newND; intc,e; while(true) { if(scanf("%d%d",&c,&e)!=2)break; if(c==0&&e==0)break; p->next=newND; p=p->next; p->c=c; p->e=e; } p->next=NULL; returnhead;}voidprintLink(ND*head){ ND*p=head->next;程序设计题型全文共51页，当前为第7页。 while(p)程序设计题型全文共51页，当前为第7页。 { printf("%d%d",p->c,p->e); p=p->next; } printf("\n");}voidfreeLink(ND*head){ ND*p; while(head) { p=head; head=head->next; deletep; }}ND*addPoly(ND*ha,ND*hb){ ND*hc,*pc,*pa=ha->next,*pb=hb->next; hc=pc=newND; intc,e; while(pa||pb) { if(pa&&(pb==NULL||pa->e<pb->e)) { c=pa->c; e=pa->e; pa=pa->next; } elseif(pb&&(pa==NULL||pb->e<pa->e)) { c=pb->c; e=pb->e; pb=pb->next; } else { c=pa->c+pb->c; e=pa->e; pa=pa->next; pb=pb->next; } if(c) { pc->next=newND; pc=pc->next; pc->c=c; pc->e=e; }程序设计题型全文共51页，当前为第8页。 }程序设计题型全文共51页，当前为第8页。 pc->next=NULL; returnhc;}ND*oneXmulty(ND*pa,ND*hb){ ND*hc,*pc,*pb=hb->next; hc=pc=newND; while(pb) { pc->next=newND; pc=pc->next; pc->c=pa->c*pb->c; pc->e=pa->e+pb->e; pb=pb->next; } pc->next=NULL; returnhc;}ND*multyXmulty(ND*ha,ND*hb){ ND*hc,*ht,*pa=ha->next; hc=newND; hc->next=NULL; while(pa) { ht=oneXmulty(pa,hb); hc=addPoly(hc,ht); freeLink(ht); pa=pa->next; } returnhc;}intmain(){ ND*ha,*hc; freopen("conv.in","r",stdin); //freopen("conv.out","w",stdout); hc=createLink(); while(true) { ha=createLink(); if(ha->next==NULL)break; hc=multyXmulty(hc,ha); freeLink(ha); } printLink(hc);程序设计题型全文共51页，当前为第9页。 freeLink(hc);程序设计题型全文共51页，当前为第9页。 return0;}5、二叉树(bTree.cpp/c)【题目描述】已知二叉树的先序遍历序列和中序遍历序列，输出其后序遍历序列和层次序遍历序列。【输入】输入文件bTree.in有二行，分别是二叉树的先序遍历序列和中序遍历序列。【输出】输出文件bTree.out包含二行,分别是上述二叉树的后序遍历序列和层次序遍历序列。【输入输出样例1】bTree.inbTree.outabdeijfcghdijefbghcajifedhgcbaabdcegifhj【数据限制】所有序列字串长度<=100#include"stdio.h"#include"string.h"constintN0=100;structnode{ chardata; intlch,rch;}tree[N0+1];introot=1;voidcreateTree(introot,char*pri,char*mid){ char*p; intk; if(root==0||*pri=='\0'||*mid=='\0')return; tree[root].data=*pri; p=strchr(mid,*pri); *p='\0';//中序：mid(1)p+1(2) k=strlen(mid);//先序：pri+1(1),pri+k+1(2) if(k>0) { tree[root].lch=root+1; createTree(root+1,pri+1,mid); } if(strlen(p+1)>0) { tree[root].rch=root+k+1; createTree(root+k+1,pri+k+1,p+1); }程序设计题型全文共51页，当前为第10页。}程序设计题型全文共51页，当前为第10页。voidpostOrder(introot){ if(root) { postOrder(tree[root].lch); postOrder(tree[root].rch); printf("%c",tree[root].data); }}voidlayerOrder(introot){ intqu[N0+5],f=0,r=0; intt; if(root==0)return; qu[r++]=root; while(r!=f) { t=qu[f++]; printf("%c",tree[t].data); if(tree[t].lch) qu[r++]=tree[t].lch; if(tree[t].rch) qu[r++]=tree[t].rch; }}voidshowTree(introot,inttab,charch){ if(root==0)return; inti; for(i=1;i<tab;i++) printf(""); printf("%c(%c)\n",tree[root].data,ch); if(tree[root].lch) showTree(tree[root].lch,tab+6,'L'); if(tree[root].rch) showTree(tree[root].rch,tab+6,'R');}inthigh(introot){ if(root==0)return0; intlh,rh; lh=high(tree[root].lch); rh=high(tree[root].rch); return1+(lh>rh?lh:rh);}intleafNumber(introot){ if(root==0)return0;程序设计题型全文共51页，当前为第11页。 if(tree[root].lch==0&&tree[root].rch==0)程序设计题型全文共51页，当前为第11页。 return1; returnleafNumber(tree[root].lch)+leafNumber(tree[root].rch);}intmain(){ charpri[N0+1],mid[N0+1]; freopen("Btree.in","r",stdin);// freopen("Btree.out","w",stdout); gets(pri); gets(mid); createTree(root,pri,mid); postOrder(root); printf("\n"); layerOrder(root); printf("\n"); showTree(root,1,'T'); printf("%d\n",high(root)); printf("%d\n",leafNumber(root)); return0;}方法二：

#include<stdio.h>#include<string.h>structNode{charch;Node*lch;Node*rch;}*root;charpri[105],mid[105];Node*buildTree(char*pri,char*mid){char*pos=strchr(mid,*pri);if(pos){Node*temp=newNode;temp->ch=*pos;temp->lch=temp->rch=NULL;*pos='\0';intk=strlen(mid);if(*(pri+1))temp->lch=buildTree(pri+1,mid);程序设计题型全文共51页，当前为第12页。if(*(pos+1))程序设计题型全文共51页，当前为第12页。temp->rch=buildTree(pri+k+1,1+pos);returntemp;}returnNULL;}voidaftShowTree(Node*root){if(root!=NULL){aftShowTree(root->lch);aftShowTree(root->rch);putchar(root->ch);}}voidlevShowTree(Node*root){Node*arr[105]={0},*p;inttop=0,tail=0;arr[++tail]=root;while(tail!=top){p=arr[++top];if(p->lch)arr[++tail]=p->lch;if(p->rch)arr[++tail]=p->rch;putchar(p->ch);}}voidfree(Node*root){if(root){if(root->rch)free(root->rch);if(root->lch)free(root->lch);deleteroot;}}intmain(void){gets(pri);程序设计题型全文共51页，当前为第13页。gets(mid);程序设计题型全文共51页，当前为第13页。root=buildTree(pri,mid);aftShowTree(root);puts("");levShowTree(root);puts("");free(root);return0;}6、二叉树1(bTree1.cpp/c)【题目描述】已知一颗二叉树的先序遍历序列和中序遍历序列，输出该树的高度和该树的叶子数。【输入】输入文件bTree1.in有二行，分别是一颗二叉树的先序遍历序列和中序遍历序列。【输出】输出文件bTree1.out只有一行，包含两个整数，分别是该树的高度和叶子数，两个整数之间用一个空格隔开。【输入输出样例1】bTree1.inbTree1.outabdeijfcghdijefbghca63【数据限制】1<=所有序列字串长度<=100#include"stdio.h"#include"string.h"structTr{charda;Tr*lchild,*rchild;};Tr*Renew(char*bch,char*mch,intlen){Tr*root;intl;char*temp;if(len<=0){ root=NULL; returnNULL;}root=newTr;程序设计题型全文共51页，当前为第14页。root->da=*bch;程序设计题型全文共51页，当前为第14页。for(temp=mch;temp<mch+len;temp++){if(*temp==*bch)break;}l=strlen(mch)-strlen(temp);root->lchild=Renew(bch+1,mch,l);root->rchild=Renew(bch+1+l,temp+1,len-1-l);returnroot;}voidfreet(Tr*root){if(root->lchild!=NULL)freet(root->lchild);if(root->rchild!=NULL)freet(root->rchild);deleteroot;return;}intdepth(Tr*root){inth,lh,rh;if(root==NULL) h=0;else{lh=depth(root->lchild);rh=depth(root->rchild);if(lh>rh)h=lh+1;elseh=rh+1;}returnh;}intleaf(Tr*root){intnum=0;if(root!=NULL)if(root->lchild==NULL&&root->rchild==NULL) num++;else num=leaf(root->lchild)+leaf(root->rchild);returnnum;程序设计题型全文共51页，当前为第15页。}程序设计题型全文共51页，当前为第15页。intmain(){intlen;charbch[100],mch[100];Tr*root;freopen("Btree1.in","r",stdin);freopen("Btree1.out","w",stdout);gets(bch);gets(mch);len=strlen(bch);root=Renew(bch,mch,len);printf("%d%d",depth(root),leaf(root));freet(root);return0;}7、哈夫曼树及编码（100分）(huffman.cpp)【题目描述】给定一篇用于通信的英文电文，统计该电文中每个字符出现的频率，按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树，并编出每个字符的哈夫曼树码，输出该电文的哈夫曼码译文。【输入】输入文件huffman.in是一篇用于通信的英文电文。【输出】输出文件huffman.out输出该电文的哈夫曼码译文。【输入输出样例1】huffman.inhuffman.outaaccdddbacbcddddddd011011000011101001100010001111111【数据限制】2<=英文电文字符数<=10000000#include"stdio.h"#include"string.h"constintN0=256;constintINF=100000;structnode1{ intw,lch,rch,parent;}ht[N0+1];structnode2{ charch; charcode[N0+1];程序设计题型全文共51页，当前为第16页。 intstart;程序设计题型全文共51页，当前为第16页。}hc[N0+1];intn,root;charstr[INF];voidreadData(){ inta[N0]={0},p=0; charch; while(scanf("%c",&ch)==1) { a[ch]++;//ch='a',a[97]=1;ch='b',a[98]=1; //a[97]=3,a[98]=2,a[99]=4,a[100]=10 str[p++]=ch; } str[p]='\0'; n=0; inti; for(i=0;i<256;i++) if(a[i]) { n++; ht[n].w=a[i]; hc[n].ch=i; }}voidselectMin(intt,int*s1,int*s2){ intmin1=INF,min2=INF,i; for(i=1;i<=t;i++) if(ht[i].parent==0) if(ht[i].w<min1) { min2=min1; *s2=*s1; min1=ht[i].w; *s1=i; } elseif(ht[i].w<min2) { min2=ht[i].w; *s2=i; }}voidcreateHtHc(){ ints1,s2,w,child,parent,i; root=2*n-1; for(i=n+1;i<=root;i++) { selectMin(i-1,&s1,&s2); ht[i].w=ht[s1].w+ht[s2].w;程序设计题型全文共51页，当前为第17页。 ht[i].lch=s1;程序设计题型全文共51页，当前为第17页。 ht[i].rch=s2; ht[s1].parent=ht[s2].parent=i; } for(i=1;i<=n;i++) { child=i; parent=ht[child].parent; while(child!=root) { if(child==ht[parent].lch) hc[i].code[hc[i].start++]='0'; else hc[i].code[hc[i].start++]='1'; child=parent; parent=ht[child].parent; } }}voidstr2code(charstr[],charcode[]){ inti,j,k,p=0; for(i=0;str[i];i++) { for(j=0;j<=n;j++) if(str[i]==hc[j].ch) break; for(k=hc[j].start-1;k>=0;k--) code[p++]=hc[j].code[k]; } code[p]=0;}intmain(){ charcode[INF]; freopen("huffman.in","r",stdin); freopen("huffman.out","w",stdout); readData(); createHtHc(); str2code(str,code); puts(code); return0;}8、哈夫曼树、编码及译码（100分）(codeToTxt.cpp)【题目描述】程序设计题型全文共51页，当前为第18页。给定2个输入文件，第1个输入文件是用于通信的英文电文，统计该电文中每个字符出现的频率，按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树，并编出每个字符的哈夫曼树码；第2个输入文件是已经按第1个输入文件的英文电文编好的哈夫曼码，输出该哈夫曼码的对应的英文电文。程序设计题型全文共51页，当前为第18页。【输入】第1个输入文件为huffman.in是用于通信的英文电文,第2个输入文件codeToTxt.in是已经按第1个输入文件编好的哈夫曼码。【输出】输出文件codeToTxt.out输出codeToTxt.in文件内容的英文电文。【输入输出样例1】huffman.incodeToTxt.incodeToTxt.outaaccdddbacbcddddddd011111011000011101001100010001111adddaccdddbacbcdddd【数据限制】2<=英文电文字符数<=10000000#include"stdio.h"#include"string.h"constintN0=256;constintINF=100000;structnode1{ intw,lch,rch,parent;}ht[N0+1];structnode2{ charch; charcode[N0+1]; intstart;}hc[N0+1];intn,root;charstr[INF];voidreadData(){ inta[N0]={0},p=0; charch; while(scanf("%c",&ch)==1) { a[ch]++;//ch='a',a[97]=1;ch='b',a[98]=1; //a[97]=3,a[98]=2,a[99]=4,a[100]=10 str[p++]=ch; } str[p]='\0'; n=0; inti; for(i=0;i<256;i++) if(a[i]) { n++; ht[n].w=a[i];程序设计题型全文共51页，当前为第19页。 hc[n].ch=i;程序设计题型全文共51页，当前为第19页。 }}voidselectMin(intt,int*s1,int*s2){ intmin1=INF,min2=INF,i; for(i=1;i<=t;i++) if(ht[i].parent==0) if(ht[i].w<min1) { min2=min1; *s2=*s1; min1=ht[i].w; *s1=i; } elseif(ht[i].w<min2) { min2=ht[i].w; *s2=i; }}voidcreateHtHc(){ ints1,s2,w,child,parent,i; root=2*n-1; for(i=n+1;i<=root;i++) { selectMin(i-1,&s1,&s2); ht[i].w=ht[s1].w+ht[s2].w; ht[i].lch=s1; ht[i].rch=s2; ht[s1].parent=ht[s2].parent=i; } for(i=1;i<=n;i++) { child=i; parent=ht[child].parent; while(child!=root) { if(child==ht[parent].lch) hc[i].code[hc[i].start++]='0'; else hc[i].code[hc[i].start++]='1'; child=parent; parent=ht[child].parent; } }}voidcode2str(char*code,char*str){ char*p=code,*q=str; intr=root;程序设计题型全文共51页，当前为第20页。 while(*p)程序设计题型全文共51页，当前为第20页。 { if(*p=='0') r=ht[r].lch; else r=ht[r].rch; if(ht[r].lch==0) { *q++=hc[r].ch; r=root; } p++; } *q='\0';}intmain(){ charcode[INF]; freopen("huffman.in","r",stdin);readData(); freopen("codeToTxt.in","r",stdin); gets(code); freopen("codeToTxt.out","w",stdout); createHtHc(); code2str(code,str); puts(str); return0;}9、判定连通图（100分）(dist.cpp)【题目描述】给你一张描述n个城镇的公路表（n*n的对称矩阵A），请判定这n个城镇是否是连通的。公路表中表示了任意两个城镇的连通情况，矩阵元素a(i,j)=0表示城镇i,j不连通，a(i,j)!=0表示城镇i到城镇j的距离。【输入】输入文件dist.in的第一行为一个自然数n(1<n<=30)； 接着n行，每行n个整数，是这n个城镇的公路表（元素的值小于1000）。【输出】输出文件dist.out包括一行，如果n个城镇是连通的输出Yes，否则输出No。程序设计题型全文共51页，当前为第21页。【输入输出样例1】程序设计题型全文共51页，当前为第21页。dist.indist.out6013490109900390068490057906504008740Yes【输入输出样例2】dist.indist.out6010490100900000008490000900000008000No【数据限制】1<n<=30#include"stdio.h"constintN0=100;constintINF=100000;intmap[N0][N0];intn;voidreadData(){ inti,j,t; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&t); if(i==j) map[i][j]=0; elseif(t==0) map[i][j]=INF; elsemap[i][j]=t; }}/*voidDFS(intx){ ints[N0],top=0,mark[N0]={0},p,i; printf("%d",x); mark[x]=1; s[++top]=x;//push while(top) { p=s[top];//peak for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { printf("%d",i); mark[i]=1;程序设计题型全文共51页，当前为第22页。 s[++top]=i;程序设计题型全文共51页，当前为第22页。 break; } if(i>n) top--;//pop } printf("\n");}voidBFS(intx){ intq[N0],f=0,r=0,mark[N0]={0},p,i; printf("%d",x); mark[x]=1; q[r++]=x; while(r!=f) { p=q[f++]; for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { printf("%d",i); mark[i]=1; q[r++]=i; } } printf("\n");}*/voidcheck(intx){ ints[N0],top=0,mark[N0]={0},p,i; intnum=0; num++;//printf("%d",x); mark[x]=1; s[++top]=x;//push while(top) { p=s[top];//peak for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { num++;//printf("%d",i); mark[i]=1; s[++top]=i; break; } if(i>n) top--;//pop } if(num==n)printf("Yes\n"); elseprintf("No\n");程序设计题型全文共51页，当前为第23页。}程序设计题型全文共51页，当前为第23页。intmain(){ freopen("dist.in","r",stdin); freopen("dist.out","w",stdout); readData(); check(1); return0;}10、LeastTime(最短时间，100分)(Least.cpp/c)【Description】Youareaspy,andyouhavestolensometopsecretoftheenemy,nowyouaretofindawaywhichtakesyouleasttimetoescape.Therearesomemanycross-pointsandsomemanyroads,eventwocross-pointstherecanbemultipleroads.Youcanassumethatthecross-pointsarenumberedfrom1ton.Cross-point1isyourstartingpointandyouneedtogotocross-pointn.Allroadsarebidirectional（双向的）.【Input】Thefirstlinecontainstwointegersnandm(1≤n≤200,0≤m≤10000),numberofcross-pointsandnumberofroadsrespectively.Nextmlineshasthreeintegersi,j,k(i≠j,1≤k≤10000),indicatingthereisaroadoflengthkconnectingcross-pointitocross-pointj.【Output】Outputonenumber,theshortestdistancefromcross-point1tocorss-pointn.Ifthereisnopathexist,output-1.Noextraspacesareallowed.【SampleInput/SampleOutput1】Least.inLeast.out461251342483491210241113程序设计题型全文共51页，当前为第24页。【SampleInput/SampleOutput2】程序设计题型全文共51页，当前为第24页。Least.inLeast.out67125134248349561024116515-1#include"stdio.h"constintN0=205;constintINF=1000000;intmap[N0][N0];intn,m;voidreadData(){ inti,j,k; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) map[i][j]=INF; while(scanf("%d%d%d",&i,&j,&k)==3) {if(k<map[i][j]) {map[i][j]=k; map[j][i]=k;} }}voiddijkstra(intx){ intdist[N0],mark[N0]={0}; inti,j,k,min; mark[x]=1; for(i=1;i<=n;i++) { dist[i]=map[x][i]; } for(i=1;i<n;i++) { min=INF; for(j=1;j<=n;j++) if(mark[j]==0&&dist[j]<min) { min=dist[j]; k=j; } if(min==INF)break; mark[k]=1; for(j=1;j<=n;j++)程序设计题型全文共51页，当前为第25页。 if(mark[j]==0&&dist[j]>dist[k]+map[k][j])程序设计题型全文共51页，当前为第25页。 { dist[j]=dist[k]+map[k][j]; } } if(dist[n]!=INF)printf("%d",dist[n]); elseprintf("-1");}intmain(){ freopen("Least.in","r",stdin);freopen("Least.out","w",stdout); readData(); dijkstra(1); return0;}11、取序号判定素数(prime.cpp/c)【题目描述】一个数组a[0]到a[n-1]存放有n整数，其中2≤n≤100。求出n整数中最大数a[m1]和次最大数a[m2],并判定m1+m2是否为素数。【输入】输入文件prime.in包含n个整数。【输出】输出文件prime.out包含两行第1行是m1和m2，第2行若m1+m2为素数则输出Yes否则输出No。【输入输出样例1】prime.inprime.out235158-2-152Yes【输入输出样例2】prime.inprime.out12345678933333777543219999904No【限制】10-10≤整数a[i]≤10+10，2≤n≤100#include"stdio.h"constintMAX=100;voidprime(inta[],intl){inti,m1,m2,flag=0;程序设计题型全文共51页，当前为第26页。m1=m2=0;程序设计题型全文共51页，当前为第26页。for(i=1;i<l;i++){if(a[i]>a[m1]) { m1=i; }}if(m1==0)m2=1;for(i=1;i<l;i++){if(i!=m1) { if(a[i]>a[m2]) m2=i; }}printf("%d%d\n",m1,m2);for(i=1;i<=m1+m2;i++){ if((m1+m2)%i==0){flag++;}}if(flag<=2)printf("Yes");elseprintf("No");}intmain(){ freopen("prime.in","r",stdin); freopen("prime.out","w",stdout);inta[MAX],len=0,i=0;while(true){if(scanf("%d",&a[i])!=1)break;i++;len++;}prime(a,len);return0;}12、名次与分数(score.cpp/c)【问题描述】程序设计题型全文共51页，当前为第27页。输入数据是我校ACM集训队参加某次ACM网络联赛的成绩和账号，数据分上下两部分，数据上半部分第1列为名次，第2列为账号，第3列为AC（完成的）题目数。数据下半部分为我校ACM集训队队员的姓名和账号。任务1：将我校ACM集训队队员的成绩排序，即做一个队内排名。任务2：计算每个队员的成绩。成绩计算方法：程序设计题型全文共51页，当前为第27页。①没有参加网赛，成绩=0②有参加网赛，网赛AC0题，成绩=10③网赛AC题数≥1，成绩=101-队内名次*sqrt(队内名次)【注:sqrt为平方根】例如李饶立同学队内名次=1，则其成绩=101-1*sqrt(1)=100.000再如林哲斌同学队内名次=2,则其成绩=101-2*sqrt(2)=98.172。输出结果为两列：姓名和成绩，成绩保留3位小数，第4位四舍五入，按成绩由高到低排列。【输入】输入文件score.in为ACM网络联赛的成绩和帐号。【输出】输出文件score.out结果为按成绩由高到低排序的两列：姓名和成绩，成绩保留3位小数，第4位四舍五入。程序设计题型全文共51页，当前为第28页。程序设计题型全文共51页，当前为第28页。score.in score.out1 SZU2011_FM1_002 42 ZHBIT2011_FM1_001 33 SZU2011_FM1_014 34 FJUT2011_FM1_001 35 SZU2011_FM1_004 36 SZU2011_FM1_013 37 FJAU2011_FM1_002 38 SZU2011_FM1_010 39 FJUT2011_FM1_004 310 FJUT2011_FM1_009 311 FJUT2011_FM1_002 312 ZHBIT2011_FM1_002 313 FJAU2011_FM1_007 214 SZU2011_FM1_008 215 FJAU2011_FM1_018 216 FJAU2011_FM1_005 217 SZU2011_FM1_001 218 SZU2011_FM1_009 219 SZU2011_FM1_007 220 FJAU2011_FM1_022 221 FJAU2011_FM1_011 222 ZHBIT2011_FM1_003 223 FJUT2011_FM1_011 224 FJAU2011_FM1_015 225 FJAU2011_FM1_006 226 FJAU2011_FM1_008 227 FJUT2011_FM1_010 228 SZU2011_FM1_018 229 FJNU2011_FM1_010 230 SZU2011_FM1_015 231 FJAU2011_FM1_014 232 FJAU2011_FM1_020 233 FJAU2011_FM1_009 234 FJUT2011_FM1_006 135 SZU2011_FM1_011 136 SZU2011_FM1_005 137 FJUT2011_FM1_012 138 FJAU2011_FM1_025 139 FJUT2011_FM1_007 140 FJAU2011_FM1_001 141 FJUT2011_FM1_008 142 FJAU2011_FM1_023 143 FJUT2011_FM1_013 144 FJNU2011_FM1_009 145 FJUT2011_FM1_005 146 FJAU2011_FM1_024 147 FJNU2011_FM1_020 048 FJAU2011_FM1_012 049 FJAU2011_FM1_017 050 SZU2011_FM1_016 0 姓名 账号 朱智佳 FJAU2011_FM1_001 李饶立 FJAU2011_FM1_002 彭秦中 FJAU2011_FM1_003 陈竞郴 FJAU2011_FM1_004 林剑辉 FJAU2011_FM1_005 李光泽 FJAU2011_FM1_006 程序设计题型全文共51页，当前为第29页。林哲斌 FJAU2011_FM1_007 程序设计题型全文共51页，当前为第29页。程千兴 FJAU2011_FM1_008 黄艳丽 FJAU2011_FM1_009 吴胜杰 FJAU2011_FM1_010 谢荣祥 FJAU2011_FM1_011 杨少群 FJAU2011_FM1_012 郑志强 FJAU2011_FM1_013 沈炬 FJAU2011_FM1_014 罗雄飞 FJAU2011_FM1_015 邱一潮 FJAU2011_FM1_016 卢丽娜 FJAU2011_FM1_017 李绍江 FJAU2011_FM1_018 林雪勇 FJAU2011_FM1_019 李华均 FJAU2011_FM1_020 吴灿南 FJAU2011_FM1_021 李福彬 FJAU2011_FM1_022 苏桂明 FJAU2011_FM1_023 魏述文 FJAU2011_FM1_024 陈贻劲 FJAU2011_FM1_025 李饶立100.000林哲斌98.172李绍江95.804林剑辉93.000李福彬89.820谢荣祥86.303罗雄飞82.480李光泽78.373程千兴74.000沈炬69.377李华均64.517黄艳丽59.431陈贻劲54.128朱智佳48.617苏桂明42.905魏述文37.000杨少群10.000卢丽娜10.000彭秦中0.000陈竞郴0.000吴胜杰0.000郑志强0.000邱一潮0.000林雪勇0.000吴灿南0.000#include"stdio.h"#include"math.h"#include"string.h"constintN0=1000;structnode{ intmc; charname[15],num[30]; intac; doublescore;}student[N0+1];intn=0,totalNumber=0;voidreadData(){ chars[1000]; booldata1=true; while(gets(s)!=NULL) { if(strcmp(s,"")==0)continue; if(strstr(s,"姓名")!=NULL&&strstr(s,"账号")!=NULL) { data1=false; continue; } if(data1&&strstr(s,"FJAU")!=NULL)程序设计题型全文共51页，当前为第30页。 { intt;程序设计题型全文共51页，当前为第30页。 n++; totalNumber++; student[n].mc=n; sscanf(s,"%d%s%d",&t,student[n].num,&student[n].ac); if(student[n].ac==0) student[n].score=10; else student[n].score=101-n*sqrt(n); } if(!data1) { inti; charname1[15],num[30]; sscanf(s,"%s%s",name1,num); for(i=1;i<=n;i++) if(strcmp(num,student[i].num)==0) { strcpy(student[i].name,name1); break; } if(i>n) { totalNumber++; strcpy(student[totalNumber].name,name1); student[totalNumber].score=0; } } }}voidprintData(){ inti; for(i=1;i<=totalNumber;i++) printf("%s%.3f\n",student[i].name,student[i].score);}intmain(){ freopen("score.in","r",stdin);// freopen("score.out","w",stdout); readData(); printData(); return0;}13、快速排序（100分）(quickSort.cpp)程序设计题型全文共51页，当前为第31页。【题目描述】程序设计题型全文共51页，当前为第31页。 给定n个整数作从小到大快速排序，每次分组以本组的左边第1个数作标准元素，用两个指针向中间移动的分组策略，完成快速排序，输出分组次数。【输入】输入文件quickSort.in的第一行为一个自然数n(1<n≤30000), 接着若干行共有n个整数，每个整数之间用空格隔开。【输出】输出文件quickSort.out包括一个整数，完成快速排序整个过程的分组次数。【输入输出样例1】quickSort.inquickSort.out456122【输入输出样例2】quickSort.inquickSort.out416253【数据限制】1<n≤30000#include"stdio.h"constintN0=30005;intn,a[N0];intnum;intdivider(inta[],ints,intt){ inti,j; intc,temp; i=s;j=n; temp=a[s]; do {while((a[j]>=temp)&&(i<j)) j--; if(i<j) { a[i]=a[j]; i++; } while((a[i]<=temp)&&(i<j)) i++; if(i<j) { a[j]=a[i]; j--; }程序设计题型全文共51页，当前为第32页。 }while(i<j);程序设计题型全文共51页，当前为第32页。 a[i]=temp; returni;}voidQuicksort(inta[],ints,intt){ inti; if(s<t) { i=divider(a,s,t); num++; Quicksort(a,s,i-1); Quicksort(a,i+1,t); }}intmain(){ ints=1,t,i; freopen("quickSort.in","r",stdin); freopen("quickSort.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); t=n; Quicksort(a,s,t); printf("%d",num); return0;}14、堆排序（100分）(heapSort.cpp)【题目描述】 给定n个整数作从小到大堆排序，输出第二趟堆排序的结果。【输入】输入文件heapSort.in的第一行为一个自然数n(10≤n≤30000)，接着若干行共有n个整数，每个整数之间用空格隔开。【输出】输出文件heapSort.out包括n个整数，是第二趟堆排序完成后的结果，每输出10个整数换行一次，各整数之间用一个空格隔开。【输入输出样例1】heapSort.inheapSort.out10293817158393323336153629338173323839程序设计题型全文共51页，当前为第33页。程序设计题型全文共51页，当前为第33页。10≤n≤30000#include"stdio.h"constintN0=30005;inta[N0];intn;voidheapone(inta[],ints,intt){ inti,j; inttemp; temp=a[s]; i=s; j=2*i; while(j<=t) { if((j<t)&&(a[j]<a[j+1])) j++; if(temp<a[j]) { a[i]=a[j]; i=j; j=2*i; } else j=t+1; } a[i]=temp;}voidHeapsort(inta[],intn){ inti; inttemp; for(i=n/2;i>=1;i--) heapone(a,i,n); for(i=n;i>n-1;i--) { temp=a[1]; a[1]=a[i]; a[i]=temp; heapone(a,1,i-1); } temp=a[1]; a[1]=a[i];程序设计题型全文共51页，当前为第34页。 a[i]=temp;程序设计题型全文共51页，当前为第34页。}intmain(){ inti; freopen("heapSort.in","r",stdin); freopen("heapSort.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); Heapsort(a,n); for(i=1;i<=n;i++) { printf("%d",a[i]); if(i%10==0)printf("\n"); } return0;}15、归并排序（100分）(mergeSort.cpp)【题目描述】 给定n个整数作从小到大归并排序，输出第