《程序设计复习》由会员分享，可在线阅读，更多相关《程序设计复习（51页珍藏版）》请在金锄头文库上搜索。
1、1、输出图形(本题100分)22、旋转数字(本题100分)33、求和(本题100分)54、多项式相乘75、二叉树106、二叉树1147、哈夫曼树及编码（100分）168、哈夫曼树、编码及译码（100分）199、判定连通图（100分）2110、Least Time (最短时间，100分)2411、取序号判定素数2612、名次与分数2813、快速排序（100分）3214、堆排序（100分）3315、归并排序（100分）3516、基数排序（100分）3717、表达式求值4018、取数相加4219、大整数排序451、输出图形(本题100分)(graph.cpp)【题目描述】 编写程序打印n行如下图形，
2、其中1n26。 n=4输出图形如下： D DCD DCBCDDCBABCD【输入】 输入文件graph.in包含1个整数。【输出】 输出文件graph.out。【输入输出样例1】 graph.in graph.out4 D DCD DCBCDDCBABCD【输入输出样例2】 graph.in graph.out7 G GFG GFEFG GFEDEFG GFEDCDEFG GFEDCBCDEFGGFEDCBABCDEFG【限制】 1n26#includeusing namespace std;int main()freopen(graph.in,r,stdin);freopen(graph.o
3、ut,w,stdout);int i,j,n;cinn;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);coutendl;return 0;2、旋转数字(本题100分)(rotation.cpp)【题目描述】 编写程序打印n行如下菱形图形（1n99），图形有n行n列个整数，图形从第1行的中间开始，数字分别是1，2，n*n-1，n*n，并且顺时针向中间转入，如果1个数据项宽度不足n*n位，用0补足到n*n位。提醒：图案中没有数字的
4、地方用空格填满，每行最后一个数字后面没有多余的空格。【输入】 输入文件rotation.in包含1个整数n。【输出】 输出文件rotation.out是一个菱形图形，图形从第1行的中间开始，数字分别是n*n， n*n-1，n*n-2，1，并且顺时针向中间转入。【输入输出样例1】 例如n=7，输出： 01 24 02 23 25 03 22 40 26 04 21 39 41 27 05 20 38 48 42 28 0619 37 47 49 43 29 07 18 36 46 44 30 08 17 35 45 31 09 16 34 32 10 15 33 11 14 12 13【限制】
5、1n99【提示】m=4i=15;.printf(%0*d, m, i);/这里用*表示系数待定，m即为指定的宽度/上面语句输出“0015”，数据宽度为4，不足4位，前补0printf(%*c, m, );/左边语句输出“ ”，即输出4个空格#include stdio.hconst int N0=2*100-1+10;int aN0N0= 0 ;struct nodeint row,col;dir4= 1,1,1,-1,-1,-1,-1,1 ;int main()int i,j,n;int row,col,row1, col1,d,m=0;freopen(rotation.in, r, std
6、in);freopen(rotation.out,w, stdout);scanf(%d, &n);row=1;col=n;d=0; int t=n*n;while( t!=0 )m+;t/=10;for( i=1; i=n*n; i+)arowcol=i;row1=row+dird.row;col1=col+dird.col;if( row11 | col12*n-1 | col12*n-1 | arow1col1!=0 ) d=(d+1)%4;row1=row+dird.row;col1=col+dird.col;row=row1;col=col1;for( i=1; i=2*n-1; i
7、+)for( j=1; j=2*n-1; j+ )if( aij!=0 )printf(%0*d, m, aij);else if( i=n & jn & j3*n-i) printf(%*c, m, );printf(n);return 0;3、求和(本题100分)（total.cpp）【问题描述】有1个nn的矩阵，从左上到右下称为主斜线（倾角135），从右上到左下称为次斜线（倾角45），在主斜线上最大，次斜线上最小的元素称为该矩阵的斜线鞍点，求出该矩阵所有斜线鞍点的和。 如55的矩阵： 3 2 5 98 10 44 12 1 12 8 67 61 45 7 19 12 21 33 56 3
8、 35 36 78 90 19 次斜线 主斜线元素7为上面矩阵的一个斜线鞍点, 元素10和19也是上面矩阵的斜线鞍点。【输入】输入文件total.in第一行是一个整数n(（1n100）)，接下去是n行n列的矩阵，矩阵的每个元素都是整数。【输出】输出文件total.out也只有1个整数，即该矩阵所有斜线鞍点的和（0和1010）。【输入输出样例1】total.intotal.out53 2 5 98 1044 12 1 12 8 67 61 45 7 1912 21 33 56 335 36 78 90 1936【输入输出样例2】total.intotal.out41 2 17 1310 15 1
9、6 918 8 19 511 7 9 100#include#define NO 100int main()freopen(total.in,r,stdin);freopen(total.out,w,stdout);int i,j,x,y,max,min,n=0,sum=0;scanf(%d,&n);int*a=new int*n;i=-1;while(+in)ai=new intn;j=-1;while(+jn)scanf(%d,ai+j);i=-1;while(+in)j=-1;while(+j0&y0)x-;y-;while(xn&yaij)max=0;break;x+;y+;x=i,y
10、=j;while(x0&yn-1)x-;y+;while(x=0)if(axyaij)min=0;break;x+,y-;if(!max|!min)continue;else sum+=aij;printf(%dn,sum);i=-1;while(+in)deleteai;deletea;return 0;4、多项式相乘 (conv.cpp/c)【题目描述】 编程实现若干个多项式相乘。多项式的输入输出格式为：系数在前，指数在后，各项按指数递增排列，每个多项式输入时以两个0结束。系数为0的项不输出。例如：1+4X3-9X5输入格式为：1 0 0 1 0 2 4 3 0 4 -9 5 0 0或者
11、1 0 4 3 -9 5 0 0，其输出只能是：1 0 4 3 -9 5【输入】 输入文件conv.in每行为一个多项式，多项式输入时以两个0结束。数据为若干行的多项式，例如：1 0 1 1 0 01 0 -1 1 0 01 0 1 2 0 0表示 （1+x)(1-x)(1+x2)【输出】 输出文件conv.out包含1行,为上述多项式相乘结果。上例的输出为：1 0 -1 4表示1-x4【输入输出样例1】 conv.in conv.out1 0 1 1 0 01 0 -1 1 0 01 0 1 2 0 01 0 -1 4【数据限制】所有系数、指数均为整数（int类型）#include stdio.htypedef struct nodeint c,e;struct node *next;ND;ND *createLink()ND *head, *p;head=p=new ND;int c,e;while( true )if( scanf(%d%d, &c, &e)!=2 ) break;if( c=0 & e=0 ) break;
