《信息学竞赛指导》参考答案

PAGEPAGE59《信息学竞赛指导》参考答案信息技术基础计算机与信息社会选择题：1、B2、C3、D4、B5、B6、D7、C计算机系统组成原理一、选择题：1、A2、A3、B4、C5、D6、C7、D8、B9、C10、A11、D12、B13、A14、D15、C16、B17、B18、D19、BDE20、AD21、B22、A23、ACDE24、C25、ACD二、思考题1、计算机系统由硬件和软件两大部分的组成。2、CAD是“计算机辅助设计”（Computer

Aided

Design）CAI是“计算机辅助教学”（ComputerAssistedInstructing）CAT是“计算机辅助翻译”（ComputerAidedTranslation）CAM是“计算机辅助制造”（computerAidedManufacturing)CMOS是“互补金属氧化物半导体（complementarymetal-oxicle-semiconductor）一种大规模应用于集成电路芯片制造的原料是微机主板上的一块可读写的RAM芯

片，用来保存当前系统的硬件配置和用户对某些参数的设定。第三节信息的表示一、选择题：1、C2、C3、A4、C5、A6、C7、D8、C9、BD10、D11、A12、C13、B第四节网络常识选择题：1、C2、B3、C4、C5、D6、A7、D8、C9、D10、A11、C12、A13、B14、C15、B16、C第五节操作系统选择题：1、E2、A3、软件系统和硬件系统4、任务栏、开始、时钟、系统已经启动了的程序5、B6、C7、D8、C9、B10、B11、CD第二章组合数学解析第一节加法原理与乘法原理思考与练习1、求1000！的末尾其有多少个零？1000\5+1000\25+1000\125+1000\625=249。2、在所有的七位数中，至少有连续四个1的数据其有多少个？分只有4个连续1、只有5个连续1、只有6个连续1、只有7个连续1函数进行讨论。3、求比1000小的正整数中含有数字1的数的个数。分仅含1个1、仅含2个1、仅含3个1等三种情况进行讨论。4、有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组数据的最大数，问有多少种方案？设取的第一组数有a个，第二组有b个，而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b)，从大到小取a个作为第一组,剩余的为第二组。此时方案数为C(n，m)。从m个数中取第一组数共有m-1种取法。

总的方案数为第二节排列与组合思考与练习1、在24名选手中进行淘汰赛，最后产生一个冠军，问一共要举行多少场比赛？23场显然。2、在一个凸n边形中，没有任意三条对角线在其内部共点，求其全部对角线在其内部的交点数。根据题意,每4个顶点可得到两条对角线,1个对角线交点，从n个顶点任取4个的方案有。3、若一个凸十二边形，无三条对角线在其内部其点。这些对角线被它们的交点其分成多少条线段？根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有9个度，可以得到（4*+12*9）/2条边。4、求n个完全相同的骰子能掷出多少种不同的方案？相当于把n个小球放入6个不同的盒子里，为可重组合，即共有种方案，即种方案。5、正整数n的一个k拆分就是把n表示为k个正整数的和。如果拆分不仅与各项的数值相关，也与各项的次序相关，这样的拆分叫做有序拆分，否则叫做无序拆分。例如4=2+1+1=1+2+1=1+1+2是4的所有3个有序3拆分。试求正整数n的k拆分的个数。F（n，k）=F（n-k，k）+F（n-1，k-1）。6、在2n个球中有n个相同，求从这2n个球中选取n个球的方案数。相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。共有方案：++…+=2n种。7、求从点（0，0）到点（n，n）的不穿过直线y=x的非降路径数。为格路问题(弱领先条件)，即从(0，0)到(n，n)，只能从对角线上方走，可以碰到对角线，故方案数为-。8、排列的生成算法有序数法、字典排序法和邻位互换掭算法等，用这些不同的方法写出前5个自然数的全排列。略。第三节递推关系思考与练习1、求n位十进制中出现偶数个5的数的个数。从分析n位十进制数出现偶数个5的数的结构入手，p1p1...pn-1是n-1位十进制数，若含有偶数个5，则pn取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若p1p1...pn-1只有奇数个5，则取pn=5，使p1p1...pn-1pn成为出现偶数个5的十进制数。令an位十进制数中出现5的数的个数，bn位十进制数中出现奇数个5的数的个数。故有：

an=9an-1+bn-1，bn=9bn-1+an-1，a1=8，b1=1。2、平面上有n条直线，任意两条直线相交于不同的点，求这n条直线将平面分成的区域数f（n）。an=an-1+2（n-1），a1=2。3、平面上有n条直线，任意两条直线相交于不同的点，求这n条直线的交点数f（n）。A(n)=a(n-1)+n-1，a1=0。4、N个不同的自然数顺序进栈，问有多少种不同的出栈方式？B(n)=。5、求n位二进制数中最后三位数为010的数的个数。an+an-2=2n-3，n≥5，a3=1，a4=2。6．什么是常系数线性齐次方程和非齐次方程，其求解方法各是什么，请整理成一篇文章。略。第四节生成函数思考与练习1、求序列5，6，7，……，n+5，……的生成函数。G(X)=5+6x+7x2+8x3+……(n+5)xn+……=5(1+x+x2+x3+……)+（x+2x2+3x3+……）=5/（1-x）+x/（1-x）22、求用1角、2角和5角邮票贴出不同邮费的方案数。G(x)=（1+x+x2+x3+……）（1+x2+x4++x6……）（1+x5+x10++x15……），展开。3、若有1克砝码2枚，2克砝码1枚，3克砝码2枚，4克砝码2枚，各能称出哪些重量？分别有多少种方案？（1+x+x2）(1+x2)(1+x3+x6)(1+x4+x8)，展开，项数即为可称出的方案数，系数即为各重量的方案数。4、求不定方程x1+2x2=10的非负整数解的个数。相当于将10个相同的球放入两个不同的盒子。G（x）=（1+x+x2+x3+……x10）（1+x+x2+x3+……x5）展开后指数为10的项的系数。5、求S={2•a，3•b}的4可重排列数。G(x)=（1+x/1！+x2/2！）（1+x/1！+x2/2！+x3/3！），展开后系数为4的项。6、求n位二进制数中只有最后三位为010的不同三进制数的数目。An=cos(n)-sin(n)+2n，n≥3。第五节组合问题设计思考与练习1、夫妇入座问题，n对夫妇出席宴会，围圆桌而坐，要求同一对夫妇不能相邻，问有多少种不同的入席方法？先女人定位，园排列n!/n=(n-1)!；再男人定位，即二重圆错排问题；两数相乘2、砝码问题，1624年，法国数学家德.梅齐里亚克（Meziriac，1581-1638）提出了著名的砝码问题。即一位商人有一个重40磅的砝码，一不小心跌落在地上摔成四块，称得每一小块砝码的重都是整磅数，且用这四块小砝码可以称出1到40磅之间任意重量的物品，问这四块小砝码的重量各为多少？1，3，9，27。3、骨牌连环阵，正方形的骨牌上刻有1到6个点，也有一种骨牌是空白的，即骨牌面上的点数有七种。对于这样两个点数相异的骨牌联在一起形成一个长2宽1的长方形骨牌对，称为多米诺骨牌对儿。如果把多米诺骨牌对儿摆成一圈，使得任意两个相相邻的骨牌对儿的两个靠近的骨牌有相同的点数，则称此圈为一个骨牌连环阵。如何才能构造一个最大的骨牌连环阵。略。4、三对夫妻同时来到一个渡口，都欲渡过河去。但渡口只有一条最多能载两人的小船，妻子在其丈夫不在场时也不能和另外的男子在一起，如何安排渡河方案才能使六人最快地渡到河的对岸去？略。5、某人给六人各写了一封信，当最后将这六封信分别放进六个信封时，结果都放错的可能有多少种？略。6、甲乙丙三人，甲能看到乙和丙，乙能看到丙，丙谁也看不到。有人在甲乙丙三人身后贴纸条，纸条是由三张白色的和两张红色的组成，他问甲身后贴的是什么颜色的纸条，甲不知。又问乙，乙也不知。最后又问丙，丙知道。丙为什么知道？丙身后贴的是什么颜色的纸条？略。第六节逻辑代数初步思考与练习1、证明反演律。列出真值表，逐项验证即可。2、化简A++D+C+BD。A++D+C+BD=A++C+D+C+BD=+C+D+C+BD=+C+D+BD3、化简A+C+BC+D。A+C+BC+D=AC+A+BC+C+ABC+BC+D =C+BC+A+BC+D=C+A+D第三章程序设计第一节概述思考与练习：1、C语言的程序一般由哪些部分组成？C语言一般由若干个源文件组成，一个源文件由若干个函数组成，而主函数有且只有一个。2、在什么情况下程序要加上头函数？当函数中包含有库函数时，应该调用头文件3、如何编译、运行一个C程序？当源程序写好后，应该对其进行编译操作(ALT+F9)，以便找出其中的语法错误；当编译通过后，应该对其进行连接操作(Compile→Linkexefile)，以便将其他库函数“嵌入”到程序中，最后执行该程序(CTRL+F9)。第二节数据类型思考与练习1、什么是常量？什么是变量？常量就是在程序执行过程中固定不变的数据。变量就是在程序执行过程中，可以根据程序的要求而随时发生改变的数据存储单元。2、整形变量和实型变量的取值范围各是多少？整形变量可以再细分成多种类型，最大的取值范围是-2147483648—2147483647，实型变量中单精度类型的取值范围是3.4E-38—3.4E38，双精度类型变量的取值范围是1.7E-308—1.7E+3083、常见有哪些运算符？常见有算术运算符、关系运算符、逻辑运算符、位操作运算符、赋值运算符、条件运算符、逗号运算符、指针运算符、求字节运算符、分量运算符、下标运算符等。4、C语言有哪些算术运算？常见的算术运算有反运算；自加、自减运算；正、负号运算5、输入和输出函数各有何特点？在C语言中，输入和输出函数较多，比较常用的输入函数是scanf，它从键盘中接受数据，然后将其存放到变量中。常用的输出函数是prinft，是向标准输出设备：显示器输出内存单元中的数据。第三节思考与练习3、写出以下程序的执行结果x=5x=5x=3x=7z=0x=3z=1第六节指针思考与练习：1、输入两个字符串，将它们拼接起来，放在一个新的数组中。#include"stdio.h"main(){staticcharst1[20]="abcdefg",st2[]="hijklmn",*p1,*p2;p1=st1;p2=st2;while(*p1!='\0')p1++;while(*p2!='\0'){*p1=*p2;p1++;p2++;}printf("%s",st1);}2、输入一个字符串，统计出其中数字的个数和e到k之间的字母的个数。#include"stdio.h"main(){staticcharst1[30]="abcde29fgsadf232332dx",*p1,*p2;inta=0,b=0;p1=st1;while(*p1!='\0'){if(*p1>='0'&&*p1<='9')a++;if(*p1>='e'&&*p1<='k')b++;p1++;}printf("a=%d,b=%d",a,b);}3、输入一个字符串，将其中的每一个连续的数字序列看作一个整数，将这些整数检索出来后依次放入一个longint型数组中。#include"stdio.h"main(){staticcharst1[30]="332ds435dfsf322dd",*p1;intstate=0,a,b=0;p1=st1;while(*p1!='\0'){if(*p1>='0'&&*p1<='9'){a=*p1-'0';b=b*10+a;state=1;}elseif(state==1){printf("%d\n",b);b=0;state=0;}//elseifp1++;}//whileif(state==1)printf("%d\n",b);}你只需要定义一个longint型数组,然后把输出语句改为赋值语句就可.4、输入8个整数，使用指针以折半插入法对其进行排序（从小到大）。本题你可以参照书上第十一章来完成.5、输入一个2*3的整数矩阵和一个3*2的整数矩阵，请使用指针数组实现这两个矩阵的相乘。a11aa11a12a13a21a22a23b11b12×b21b22=b31b32a11*b11+a12*b21+a13*b31a11*b12+a12*b22+a13*b32a21*b11+a22*b21+a23*b31a21*b12+a22*b22+a23*b32本题主要是看你对指针的掌握情况,但如果用数组来做又简单又能反应数组的特点,用指针来做会比较繁杂,如果你有时间,可以按题目要求来完成。下面程序是其核心部份。For(i=1;i<=2;i++)For(j=1;j<=2;j++)For(k=1;k<=3;k++)c[i][j]=a[i][k]*b[k][j]+c[i][j];6、以字符串的形式一次输入若干个变量标志符存入一个字符数组中，各标志符之间以空格隔开，输出其中非法标志符的个数。#include"stdio.h"main(){staticcharst1[30]="1eq_3F32_ds435'dfDSf322",*p1;intstate=0,a=0,x=1,i;p1=st1;while(*p1!='\0'){if((*p1>='a'&&*p1<='z')||(*p1>='A'&&*p1<='Z')||(*p1=='_')){while(*p1!=''&&*p1!='\0'){if((*p1>='a'&&*p1<='z')||(*p1>='0'&&*p1<='9')||(*p1>='A'&&*p1<='Z')||(*p1=='_'))state=1;elsex=0;p1++;}//while(*p1!='')if(state==1&&x==1)a=a+1;x=1;}elsewhile(*p1!=''&&*p1!='\0')p1++;p1++;}printf("%d",a);}第七节结构体与共用体思考与练习：1、使用两个结构体变量，分别存入用户输入的两个日期（包括年、月、日），然后计算两日期之间相隔多少天。#include"stdio.h"main(){structrain{longinty,m,d;}a,b,c;longintad,bd;a.y=2006;a.m=2;a.d=6;b.y=2006;b.m=6;b.d=8;if(b.y*400+b.m*32+b.d<a.y*400+a.m*32+a.d){c=a;a=b;b=c;}switch(a.m){case1:ad=a.d;break;case2:ad=a.d+31;break;case3:ad=a.d+59;break;case4:ad=a.d+90;break;case5:ad=a.d+120;break;case6:ad=a.d+151;break;case7:ad=a.d+181;break;case8:ad=a.d+212;break;case9:ad=a.d+243;break;case10:ad=a.d+273;break;case11:ad=a.d+304;break;case12:ad=a.d+334;break;}if(((a.y%4==0)&&(a.y%100!=0))||(a.y%400==0)){if(a.m>2)ad=ad+1;}switch(b.m){case1:bd=b.d;break;case2:bd=b.d+31;break;case3:bd=b.d+59;break;case4:bd=b.d+90;break;case5:bd=b.d+120;break;case6:bd=b.d+151;break;case7:bd=b.d+181;break;case8:bd=b.d+212;break;case9:bd=b.d+243;break;case10:bd=b.d+273;break;case11:bd=b.d+304;break;case12:bd=b.d+334;break;}if(((b.y%4==0)&&(b.y%100!=0))||(b.y%400==0)){if(b.m>2)bd=bd+1;}bd=bd-ad;ad=0;while(a.y<b.y){if(((b.y%4==0)&&(b.y%100!=0))||(b.y%400==0))bd=bd+366;elsebd=bd+365;a.y=a.y+1;}printf("%ld",bd);}2、用户输入12个0~100之间的整数，统计出小于60、60~79、80~100三个范围的整数各有多少个，将统计的结果存放在一个结构体变量中，最后将此结构体变量传递给一个函数，此函数负责打印出结果。3、用户输入两个字符串，分别统计出字符串的长度、空格个数、字母的个数和数字的个数并放入两个结构体变量中，然后调用一个函数，比较这两个结构体变量，判断4个统计项目中哪些相同哪些不同，输出判断的结果。#include"stdio.h"main(){staticstructrain{longintl,space,num,abc;}a1,a2;chara[30]="dsa234322d",b[30]="2343dsad2422";inti,m,n,e,k;a1.space=a1.num=a1.abc=0;a2=a1;a1.l=strlen(a);for(i=0;i<=a1.l;i++){if(a[i]>='0'&&a[i]<='9')a1.num=a1.num+1;if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z'))a1.abc=a1.abc+1;if(a[i]=='')a1.space=a1.space+1;}a2.l=strlen(b);for(i=0;i<=a2.l;i++){if(b[i]>='0'&&b[i]<='9')a2.num=a2.num+1;if((b[i]>='a'&&b[i]<='z')||(b[i]>='A'&&b[i]<='Z'))a2.abc=a2.abc+1;if(b[i]=='')a2.space=a2.space+1;}if(a1.l==a2.l)printf("thelengthissame\n");elseprintf("thenumberofthelengthisNO\n");if(a1.num==a2.num)printf("thenumberofthenumberissame\n");elseprintf("thenumberofthenumberisNO\n");if(a1.abc==a2.abc)printf("thenumberoftheletterissame\n");elseprintf("thenumberoftheletterisNO\n");if(a1.space==a2.space)printf("thenumberofthespaceissame\n");elseprintf("thenumberofthespaceisNO\n");}第八节文件思考与练习：1、将三个学生的数据（学号、姓名、年龄）从键盘输入，存入到一个新建的文本文件中去。#include"stdio.h"#include"stdlib.h"main(){charname[20];longintID;intage;inti;FILE*fp;if((fp=fopen("test.txt","w"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}for(i=1;i<=3;i++){scanf("%ld%s%d",&ID,name,&age);fprintf(fp,"%ld%s%4d\n",ID,name,age);}fclose(fp);}2、有一文本文件，以‘\n’字符作为分行的标志，请编定程序指出其中第几行是最长的行，此行有多少个字符。#include"stdio.h"#include"stdlib.h"main(){intline=0,number=0,temp=0,x=0;charch;FILE*fp;if((fp=fopen("test.txt","r"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}ch=fgetc(fp);while(ch!=EOF){line=line+1;while(ch!='\n'&&ch!=EOF){temp=temp+1;ch=fgetc(fp);}if(temp>number){number=temp;x=line;}if(ch!=EOF)ch=fgetc(fp);temp=0;}printf("number=%dline=%d\n",number,x);fclose(fp);}3、10个实型数据以二进制的形式存放在一个文件中，将它们逆序读出，取三位小数后以字符形式存入一个新的文件中。例2.txt1001111例2.txt10011111101111111111111111例1.txt1111.0011111.0111111.1111111.1#include"stdio.h"#include"stdlib.h"main(){charaa[40],a;intline,i,number=0;FILE*fp_1,*fp_2;if((fp_1=fopen("1.txt","r"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}if((fp_2=fopen("2.txt","w"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}fscanf(fp_1,"%s",aa);while(a!=EOF){line=strlen(aa);for(i=line-1;i>=0;i--){if(aa[i]!='.'){fputc(aa[i],fp_2);number=number+1;}if(number==3){fputc('',fp_2);number=0;}}fputc('\n',fp_2);number=0;a=fgetc(fp_1);fscanf(fp_1,"%s",aa);}fclose(fp_1);fclose(fp_2);}注:本其实是一道变化很多的题，比如把逆序读出二进制数每八位转换成一个ASCII码来存储高位不足补零等。4、将用输入的5个学生的学号和成绩以结构体的形式存入新建的文件，然后读取该文件，将成绩在80分段（大于等于80而小于90）的学生的学号和相应的成绩打印出来。本题其实是第1题与前一节第2题的综合，是一道基本的语法练习题，请读者自行完成。第四章数据结构第一节线性表结构1、[题目]一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是多少？[解答]第一个元素占地址100和101，依此类推第5个占地址108和109，所以答案为1082、[题目]已知一维数组a[4]的地址为1000，二维数组b[3,2]的地址为2000，数组只存储的数据类型为integer,问数组a[15]和b[5,3](按行方式储存,二维数组为5行5列)的地址各为多少?[解答]一个integer数据(-32768~32767)需要16位二进制存储，所以a[15]的地址为1022。3、[题目]采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度是多少？[解答]查找第一个元素的查找长度为1，第二个的长度为2…第n个的长度为n,所以总共长度为，平均长度为。4、[题目]设有一个栈，元素进栈的次序为A,B,C,D,E。试问能否得到出栈序列：

1)C,E,A,B,D2)C,B,A,D,E3)D,C,A,B,E4)A,C,B,E,D5)A,B,C,D,E[解答]‘<’代表进栈，‘>’代表出栈,下同1)不能

2)可以按<,<,<,>,>,>,<,<,>,>的顺序

3)不能

4)可以按<,>,<,<,>,>,<,<,>,>的顺序

5)可以按<，>，<，>，<，>，<，>，<，>的顺序5、[题目]设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少?[解答]根据栈先进后出以及队列先进先出的特征，可知进出栈的顺序为<,<,>,<,<,>,>,<,<,>,>,>。某一时刻，栈中最多有3个元素，所以栈S的容量至少为36、[题目]设将整数1.2.3.4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序加入其中，请回答下述问题：

(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),

Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)？

(2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。(3)请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。[解答](1)1,3,2,4

(2)按照<,>,<,<,<,>的顺序可以得到1,4的输出，此时栈中还有2,3。接着只能输出3,2而不能输出2,3。

(3)经过观察可以得到如下结论：1.一旦栈中输出了元素n，那么1…n-1这些元素要么已经出栈，要么还按从小到大的顺序存在栈中；2.输出元素n后，比n小的未输出元素只能按从大到小的先后顺序输出。不难得出，可以输出以下序列：(4,3,2,1)(3,4,2,1)(3,2,4,1)(2,4,3,1)(2,3,4,1)(2,1,4,3)(1,4,3,2)(1,3,4,2)(1,3,2,4)(1,2,4,3)(1,2,3,4)7、[题目]回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。[解答]根据提示不难完成。源程序：huiwen.pas,huiwen.exe输入：huiwen.in输出：huiwen.out输入为一行待判断字符，若有数字仍按字符形式判断8、[题目]线性表用顺序储存，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表(a1,a2,…am,b1,2b,…bn)改变为：(b1,b2,…bn,a1,a2,…am)。[解答]以字符串形式进行操作，直接交换。源程序：huhuan.pas,huhuan.exe输入：huhuan.in输出：huhuan.out输入为一行待判断字符，若有数字仍按字符形式判断9、[题目]写出下列中缀表达式的后缀形式：

(1)A*B*C(2)-A+B-C+D(3)A*B+C(4)(A+B)*D+E/(F+A*D)+C[解答](1)AB*C*

(2)A–B+C–D+

(3)AB*C+

(4)AB+D*EAD*F+/+第二节树和二叉树1、[题目]对于三个结点A、B、C，有多少种不同的树？[解答]如图，直线型的树由于根结点中间结点和末结点的不同可以有3*2=6种不同的树如图，满二叉树型由于根结点不同可以有3种不同的树(此处没有考虑左右孩子结点的不同)。2、[题目]如果一棵树有n1个度为1的结点，由n2个度为2的结点，…，nm个度为m的结点，则该树共有多少个终端结点？[解答]经过观察，可得该树共有3、[题目]如下图所示，指出该树的叶结点、分支结点，各个结点的层次和树的高度，从结点A到结点H的路径长度是多少，有多少条长度为2的路径。[解答]结点ABCDEFGH叶结点NNNNYYYY分支YYYYNNNN层次12233334度22210000树的高度4，从A到H的路径长度是3，有8条长度为2的路径4、[题目]对如下一棵二叉树，其中序遍历的序列是什么?[解答]树的遍历规则：先序中左右；中序左中右；后序左右中；答案：DGBACEF5、[题目]已知一棵二叉树的前序遍历结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。[解答]由树的遍历特征求得，答案如图6、[题目]将下图所示的树转化为二叉树。将转化得到的二叉树，按前序、中序、后序进行遍历，写出遍历的结点序列。[解答]根据树的转换规则(P155)可得如图

前序遍历：GHKILEBCDFJA

中序遍历：KHLIGEDJFCBA

后序遍历：KLIHGEJFDCAB7、[题目]写出一个将二叉树左右孩子交换的算法程序。[解答]解法一用顺序结构(P153,以层顺序)读取和储存二叉树，‘0’代表空结点，交换后以顺序结构输出。输入输出文件均为一行带空格的大写字母序列。

源程序：Programchangetree(input,output);varff:text;tree:array[1..100]ofchar;c:char;k,m,n:integer;Procedureinit;beginassign(ff,'changetree.in');reset(ff);fillchar(tree,sizeof(tree),'0');n:=0;k:=0;whilenot(eoln(ff))dobegininc(k);read(ff,tree[k],c);iftree[k]<>'0'theninc(n);end;close(ff);end;Procedurechange(i:integer);varj:integer;l:char;beginj:=i*2;fork:=ito(i*3div2-1)dobegindec(j);l:=tree[k];tree[k]:=tree[j];tree[j]:=l;end;ifi*2<=nthenchange(i*2);end;Proceduremain;beginchange(2);assign(ff,'changetree.out');rewrite(ff);m:=0;k:=1;repeatbeginwrite(ff,tree[k],'');iftree[k]<>'0'theninc(m);inc(k);enduntilm>=n;close(ff);end;begininit;main;end.解法二用指针形式储存二叉树后，利用循环使每个分支结点的左右指针交换。Typepoint=^node;

node=record

c：char

;left,right：point

;end

;Varhead:point;//head头指针Procedurechange(p:point);

var

q,r:point;

begin

q:=p;r:=q^.left;

q^.left:=q^.right;q^.right:=r;if(r^.left<>nil)or(r^.right<>nil)

thenchange(r);

r:=q^.left;

if(r^.left<>nil)or(r^.right<>nil)

thenchange(r);

end;

…begin

…

change(head);

…

end.8、[题目]什么是哈夫曼树？用给出的一组权值{4,2,3,5,7,8}，建立一棵哈夫曼树。[解答]哈夫曼树的定义：带权路径长度最短的树哈夫曼树的建立规则：

现将数组从小到大排序，再将它们依次填充到哈夫曼树的叶结点上，而且越小的数深度约大。

源程序：Programbuild(input,output);varff:text;i,j,m,n:integer;tree:array[1..100,1..2]ofinteger;Procedureinit;beginassign(ff,'build.in');reset(ff);n:=0;whilenot(eoln(ff))dobegininc(n);read(ff,tree[n,1]);end;close(ff);fori:=1ton-1doforj:=i+1tondoiftree[i,1]>tree[j,1]thenbeginm:=tree[i,1];tree[i,1]:=tree[j,1];tree[j,1]:=m;end;end;Proceduremain;beginfori:=2tondobegintree[i-1,2]:=tree[i,1];inc(tree[i,1],tree[i-1,1]);end;assign(ff,'build.out');rewrite(ff);write(ff,tree[n,1],'');fori:=n-1downto1dowrite(ff,tree[i,2],'',tree[i,1],'');close(ff);end;begininit;main;end.第三节图1、[题目]已知图的邻接矩阵表示，请画出它所对应的图。[解答]2、[题目]对如下图所示的有向图，请写出该图的邻接矩阵。[解答]

0代表没有距离

1代表有通路

代表没有通路3、[题目]写出如下带权无向图的邻接矩阵，并求出其最小生成树。[解答]4、[题目]对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为多少；所有邻接表中的结点总数是多少？[解答]由于每一个连接表结点数是其边数的二倍减一，所以所有邻接表中的结点总数是2e-n。5、[题目]画出1个顶点2个顶点3个顶点4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。[解答]n个顶点两两连接，任意选出两个顶点形成一条不同的边。所以边的总数是6、[题目]对如下所示的图中，分别写出按深度优先搜索法和广度优先搜索法，从A点出发遍历的结果序列。[解答]深度优先：ABCDFEGH广度优先：ABEFHCDG7、[题目]设无向图G如图所示，试给出

(1)图的邻接矩阵

(2)该图的邻接表

(3)该图的多重邻接表

(4)从V0出发的“深度优先”遍历序列

(5)从V0出发的“广度优先”遍历序列(1)[解答](2)(3)略

(4)V0V1V3V2V4V6V5

(5)V0V1V2V3V4V5V6第四节查找1、[题目]对线性表进行二分查找时，要求线性表必须是：

A.以顺序方式存储

B.以链接方式存储

C.以顺序方式存储，且结点按关键字有序排序

D.以链接方式存储，且结点按关键字有序排序[解答]答案：C2、[题目]有一个有序表为{1,3,9,12,32,41,45,62,75,82,88,95,100}，当二分查找值为82的结点时，多少次比较后查找成功？[解答]根据二分查找的过程，比较的次序是：4582所以经过2次比较3、[题目]设哈希表长m=14，哈希函数H(key)=key%11,表中已有4个结点。

addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空

如果用二次探测再散列处理冲突，关键字为49的结点的地址是多少？[解答]哈希表如下，见P169开放定址法。答案：8123456789101112131415386184494、[题目]设哈希长度为10，哈希函数为H(K)=Kmod7,关键字集合为{15,10,12,20,25,35,31,15},请给出开放地址方法和拉链方法所构造得到的哈希表结构。[解答]地址0123456789开放法35153110251220拉连法3515(10,31)2512205、[题目]试设计递归二分(折半)查找算法。[解答]见P169，用开放地址法处理冲突。通过mod函数的运用，将longint型数据转换成相应的初始地址，再用一个过程来解决冲突。算法如下：Varn:longint;Hash:array[1..999]oflongint;Functionfind(i:longint):integer;

varj:string;

k,l,m:integer;beginstr(i,j);k:=length(j);l:=0;

whilek>0dobeginval(copy(j,1,3),m);inc(l,m);

k:=k-3;end;l:=lmod1000;find:=l;end;Proceduresearch(i,t:integer;j:longint);

varp:integer;beginifHash[i]=jthenwriteln(i)

elsebeginp:=(i+t)mod999;

search(p,t+1,j);end;end;beginreadln(n);search(find(n),1,n);end;递归二分（折半）查找算法。intBserach(elemtypea[],elemtypex,intlow,inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;if(x==a[mid])returnmid;if(x<a[mid])return(Bserach(a,x,low,mid-1));elsereturn(Bserach(a,x,mid+1,high));}第五节、排序1、什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；

在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若相同关键字元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

直接插入排序、冒泡排序、归并排序是稳定的排序方法；而简单选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。2、希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。3、已知序列{17,18,60,40,7,35,73,65,85},请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。参照例4.18进行排序4、已知序列{10,18,4,3,6,12,1,9,18,8},请给出采用希尔排序法对该序列作升序排序时的每一趟的结果(增量为5,2,1)。参照例4.17进行排序5、已知序列{10,18,4,3,6,12,1,9,18,8},请给出采用归并排序法对该序列作升序排序时的每一趟的结果。参照例4.22进行排序6、设待排序的排序码序列为{17,18,60,40,7,35,73,65,85},试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

(1)直接插入排序(2)折半半插入排序(3)快速排序

(4)直接选择排序(5)堆排序参照教材中示例7、判定下列序列是否为堆。如果不是，则请把它们调整为堆。（1）{100，86，48，73，35，39，42，57，66，21}（2）{12，70，33，65，24，56，48，92，86，33}略8、对于冒泡排序算法，什么样的输入数据使得算法的执行时间最长？若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。9、试写出折半排序的算法。基本思想设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。折半插入排序的算法：typedefintSortData;voidBinInsSort(SortDataV[],intn){SortDatatemp;intLeft,Right;for(inti=1;i<n;i++){Left=0;Right=i-1;temp=V[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<V[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)V[k+1]=V[k];//记录后移V[Left]=temp;//插入}}第五章常用算法第一节算法评估思考与练习P179：1、O(log2n)，O(nlog2n)2、O(nlog2n),O(n2)3、O(n2),O(n2),O(n2),O(nlog2n),O(nlog2n),O(nlog2n)第二节枚举法思考与练习P182：1、算法分析：本题可以枚举123到329之间的所有三位i，如果i、2*i、3*i这三个数中包含的9个数字刚好是1到9则输出i、2*i、3*i。为了记录1到9这9个数字在i、2*i、3*i中是否出现过，程序中用一个一维数组a。a[d]=1表示数字d在i、2*i、3*i这三个数中出现过，a[d]=0则表示未出现。2、提示：如果采取逐条路线枚举的方法去试探，那么由于本题中的展室数目并不大，所以是可以行得通的。第三节递推算法思考与练习P185：1、楼梯有N级台阶,上楼可以一步上一阶,也可以一步上二阶。试编程序计算共有多少种不同走法?算法分析：到第N级台阶时问题在第N-1级楼梯处上一级台阶或在第N-2级台阶楼梯处上两级台阶，由此可得出递推表达式a(n)=a(n-1)+a(n-2)。程序代码：#include<stdio.h>main(){longf3,f2,f1;inti,n;printf("pleaseinputthesteps:");scanf("%d",&n);f1=1;f2=2;for(i=3;i<=n;i++){f3=f1+f2;f1=f2;f2=f3;}printf("%ld\n",f3);}2、宰相的麦子：相传古印度宰相达依尔，是国际象棋的发明者。有一次，国王因为他的贡献要奖励他，问他想要什么。达依尔说：“只要在国际象棋棋盘上（共64格）摆上这么些麦子就行了：第一格一粒，第二格两粒，……，后面一格的麦子总是前一格麦子数的两倍，摆满整个棋盘，我就感恩不尽了。”国王一想，这还不容易，刚想答应，如果你这时在国王旁边站着，你会不会劝国王别答应，为什么？请输出棋盘上摆放的麦子总数。假如一万颗麦子有一斤重，请问共有多少吨麦子？算法分析：国际象棋棋盘每一格子上的麦子粒数都是上一格麦子粒数的两倍，递推式为a=2*a，总的麦子数为264-1粒，简单算出其结果为20位的数值，可用高精度加法来递推算出结果。3、阶乘计算(用递推)：写一个程序，对给定的n（n≤100），计算并输出n的阶乘n！的全部有效数字。算法分析：用递推法求解阶乘函数的思路是：先求fac(1)，再求fac(2)，…,直到求出fac(n)，其程序代码可参考第四节高精度计算中思考练习的第2题。4、一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升，显然卡车装一次油是过不了沙漠的，因此司机必须设法在沿途建立几个储油点，使卡车顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油才能使卡车以消耗最少汽油代价通过沙漠？算法分析：可用倒推法解决该问题，最后一个贮油点应离终点500公里，贮油量为500公升，这样卡车可以顺利到达终点，建立离终点的第二个贮油点时要为下一个贮油点往返运送500公升油，因此第二个贮油点应贮存1000公升油，有500公升油消耗在送油的路途中，第二个贮油点离终点的距离为S=500+500/3，如此得出离终点第N个贮油点的递推式S(N)=S(N-1)+500/(2N-1)，如此倒推下去一直到起点。#include<stdio.h>main(){intk;/*贮油点位置序号*/floatd,d1;/*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/floatoil[10],dis[10];inti;printf("NO.distance(k.m.)\toil(l.)\n");k=1;d=500;/*从i=1处开始向始点倒推*/dis[1]=500;oil[1]=500;do{k=k+1;d=d+500/(2*k-1);dis[k]=d;oil[k]=oil[k-1]+500;}while(!(d>=1000));dis[k]=1000;/*置始点至终点的距离值*/d1=1000-dis[k-1];/*求i=n处至始点的距离*/oil[k]=d1*(2*k+1)+oil[k-1];/*求始点藏油量*/for(i=0;iprintf("%d\t%f\t%f\t\n",i,1000-dis[k-i],oil[k-i]);}5、有一堆桃子和8只猴子，第1只猴子把桃子平均分成3堆后，还剩1个，它吃了剩下的一个，并拿走一堆。第2、3只猴子和第1只一样。第4只猴子把桃子平均分成5堆后，还剩1个，它吃了剩下的一个，并拿走一堆。5、6、7、8和第4只一样。问：至少还剩多少个桃子？原来至少有多少个桃子？算法分析：可采用枚举尝试与倒推的方法来解决该问题。从最后一只猴子起倒推能够分成5堆且还剩一个的桃子数，每次以5个递增枚举满足条件的桃子数直到第一只猴子能够分成3堆还剩一个桃子为止。第四节高精度计算思考与练习P189：1、用高精度算法求菲波那契数列的前2000项。算法分析：该题采用递推算法，因为要求到前2000项，具体计算时要用高精度加法实现。#include<stdio.h>main(){inta1[500],a2[500],a3[500];intjw,he,i,j,k;for(i=1;i<=500;i++){a1[i]=a2[i]=a3[i]=0;}a2[1]=1;jw=0;printf("%d\n",0);printf("%d\n",1);for(i=3;i<=2000;i++){for(j=1;j<=500;j++){he=a1[j]+a2[j]+jw;jw=he/10;a3[j]=he%10;}j=500;while(a3[j]==0)j--;for(k=j;k>=1;k--)printf("%d",a3[k]);printf("\n");for(j=1;j<=500;j++){a1[j]=a2[j];a2[j]=a3[j];}}}2、求1!+2!+3!+……+n!之和。(n≤500)算法分析：该题可以用高精度乘法来实现，也可以用高精度加法来实现，下面的程序代码采用高精度加法来实现。#include<stdio.h>main(){ints[1200],a[1200],b[1200];intjw,he,i,j,k,n;scanf("%d",&n);for(i=1;i<=1200;i++){s[i]=a[i]=b[i]=0;}a[1]=1;for(i=1;i<=n;i++){for(j=1;j<=1200;j++)b[j]=0;for(j=1;j<=i;j++){jw=0;for(k=1;k<=1200;k++){he=a[k]+b[k]+jw;jw=he/10;b[k]=he%10;}}for(k=1;k<=1200;k++)a[k]=b[k];jw=0;for(k=1;k<=1200;k++){he=s[k]+b[k]+jw;jw=he/10;s[k]=he%10;}}j=1200;while(s[j]==0)j--;for(k=j;k>=1;k--)printf("%d",s[k]);printf("\n");}3、求数列1+1/2+1/3+…+1/n之和。(n≤500，和的值精确到小数点后500位)算法分析：本题采用高精度加法和两个单精度数的除法(结果采用高精度存储)来实现。#include<stdio.h>main(){inta[601],b[601];intn,i,j,g,s;scanf("%d",&n);for(i=0;i<=600;i++){a[i]=b[i]=0;}for(i=1;i<=n;i++){a[0]=1/i;g=1%i;for(j=1;j<=600;j++){s=g*10;g=s%i;a[j]=s/i;}s=g=0;for(j=600;j>=0;j--){s=a[j]+b[j]+g;g=s/10;b[j]=s%10;}}printf("%d.",b[0]);for(j=1;j<=500;j++){printf("%d",b[j]);}printf("\n");}4、试根据以下公式来设计程序求圆周率n，结果精确到小数点后指定的m位。算法分析：这道题目涉及到高精度加法，高精度乘法与两个高精度数的除法运算，大家可以借助前面所列出的知识点来解决，代码较长，略去。第五节模拟法思考与练习P190：1、机场检票进站口进一个人的时间至少为12秒钟，至多为30秒钟，某个航班有n个乘客，试求这n个人进站所需要的进站时间，如要求排队的n个乘客在30分钟内全部进站，则一般需要安排多少个检票口。(要求模拟m次，输出m次各自所需时间和需要安排的检票口数)算法分析：用计算机可以模拟很多事件处理的过程。该题用随机函数产生n个12-30之间的随机数12+random(19)，累加起来即为所需要的进站时间。再根据时间来安排检票口的数量即可。2、玩扑克牌是人们最为喜爱的文娱活动之一。玩扑克牌有许多种不同的玩法，常见的有桥牌、升级等。请设计程序模拟升级时扑克牌的发牌过程，把含大小王在内的54张牌随机分发给4家，每家12张，底牌留6张。算法提示：可以简单模拟产生1~54之间的随机数，依次放到集合里面并用一个对应的数组来存储，如遇重复产生的数则跳过直到54个数全部产生为止，然后再根据要求分配这些数即可。第六节分治算法思考与练习P1941、算法描述：…e0<-1e-38函数f｛f<-exp(x*ln(2))+exp(x*ln(3))-exp(x*ln(4))}{a<-1b<-2repeatx<-(a+b)/2fa<-f(a)fx<-f(x)iffa*fx<0thenb<-x/*在A、X内有解*/elsea<-xuntil(abs(b-a)<e0)｝…2、分析：我们可以先把比赛时间表看作一个2m*2A=A1BCD当规模减半到只有两个选手时，矩阵为：1221由于各种情况性质一致，只是规模不同，参照这一矩阵，可知A1与A的关系：A1BBA1当有4个选手参加比赛时，由于A、A1的关系可以得出下列矩阵：1221344334431221由于有这一规律，于是可以得到一种比赛顺序。也就是将（2k*2k）矩阵分成了四块，每块是（2k－1*2k－1）的矩阵，它是对称的（如A1与A1，B与B）。然后分别把A1、B分成四块，一直划分到（2*2）矩阵为止，这时就可定出每个元素的值，再按对称关系构成比赛表。问题就被简化成了设计一个对称矩阵。第七节回溯算法思考与练习P198：1、有n个0和n个1排成一个数列，要求从该数列的第一个位置到数列的任意一个位置时数字0的个数总是大于或等于数字1的个数，求所有可能的排列。算法分析：该题与书中排除买票问题类似，可以用数组a来存储数列的排队情况。先将a数组的各元素值赋为-1。从a[1]的值加1开始试探、搜索。试探时b[0]用于存储0的个数，b[1]用于存储1的个数。某个元素a[i]的值是否符合要求需满足以下条件：①(a[i]=0)&&(b[0]<n)/*如果第i个元素值为0，而队列中0的个数不到n个时表示可以放入*/②(a[i]=1)&&(b[1]<b[0])/*如果第i个元素值为1，而队列中1的个数小于0的个数时表示可以放入*/如果满足条件，则将条件判断变量pd的值设为真。Pd值为真后将该元素加入，然后判断i的值是否为总的人数，如等于则输出这组排列，如否则将i值加1后继续判断下一个人的情况。如果不满足条件，则a[i]的值加1后继续试探，如果0,1两个值均不符合要求，则回溯，返回上一个元素a[i-1]，将其值加1后继续尝试。样例程序如下：#include<stdio.h>main(){inti,j,n,pd,a[100],b[2];scanf("%d",&n);n=n/2;i=1;for(i=1;i<=2*n;i++)a[i]=-1;/*先将a数组各元素的值全部置为-1，用-1来表示未放数的初始状态*/i=1;b[0]=0;b[1]=0;/*将计零和计1个数的计数器b[0]、b[1]清零，i表示数组a的当前元素位置*/do{do{ pd=0;/*能否放数的判断变量*/ a[i]++;/*数组a的当前元素值加1，开始试探*/ if(a[i]==0&&b[0]<n)/*元素值为零时能不能放的判定条件*/ {b[0]++;pd=1;} if(a[i]==1&&b[1]<b[0])/*元素值为1时能不能放的判定条件*/ {b[1]++;pd=1;} }while((pd!=1)&&(a[i]!=2));if(pd==1)/*pd值为1时表示能放*/ if(i==2*n)/*如果已经放到最后一个数了，则输出这一组排列*/ {for(j=1;j<=2*n;j++) printf("%2d",a[j]); printf("\n"); } elsei++;/*继续放下一个位置*/else/*a[i]为2时表示已经试探了0,1后均不成立，此时回溯*/{b[1]--;/*回溯时假设a[i]的值从1变为2时试探的1已经被计数*/ a[i]=-1;/*将当前元素还原为未放值时的初始状态*/ i--;/*回到上一个位置*/ if(a[i]==0)/*上一个位置值为0时的处理*/ {b[0]--; if(b[1]==b[0])b[1]++; }}}while(i!=0);}注意回溯时上一位会进行加1计算，因此不管上一位是0还是1，对应的计数器都应减少1，即有i--,b[a[i]]--。如果上一位的值为0，在加1时会有这样一种情况，这个1在b[1]=b[0]时不会被计数而直接又加1后向前回溯，回溯时的dec(b[1])语句会导致b[1]被多减一次。为避免这种情况，在此处加一判断，(a[i]=0)&&(b[1]=b[0])时b[1]++。2、用L型骨牌去覆盖一个m×n个方格所组成的长方形，请问怎样覆盖才能使长方形上留下的方格数最少？算法分析：采用回溯搜索的方法来处理该问题。总是存在一种最优的布局，使得每一块骨牌至少有两条边与其他骨牌的边或者棋盘的边相邻，处理时可先设初始状态时的棋盘为空；再取棋盘的左上角，放第一张骨牌，使骨牌的一个顶点与棋盘的角的顶点重和。第一张骨牌有横放和竖放两种情况，因此得到两个初始状态的子结点；对于当前的状态，已经放置的骨牌的围成一个多边形（其中可能有空隙），该多边形的边和棋盘的边又将棋盘中的空地围成一个多边形，下面只要在这个多边形内部贴着边放置一个骨牌就可以了。3、有一个由n×n个方格组成的迷宫，入口和出口分别在迷宫的左上角和右上角。用迷宫格子中的0表示此路可通，1表示此路不通。走迷宫时，从某点出发可沿8个方向前进，请找出给出迷宫中从入口到出口的通路。算法分析：给出从某点出发沿4个方向前进的提示，8个方向与之类似。在二维迷宫里面，从出发点开始，每个点按四邻域算，按照右，上，左，下的顺序搜索下一落脚点，有路则进，无路即退，前点再从下一个方向搜索，即可构成一有序模型。下表为10×10迷宫{1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1}从出发点开始