计算机 编程大赛本科完整版.doc

决赛c 本科考生须知：考试时间为5小时。本试卷包含两种题型：“代码填空”与“程序设计”。总计100分。其中代码填空：9+14 = 23 分程序设计：19+28+30 = 77分填空题要求参赛选手在弄清给定代码工作原理的基础上填写缺失的部分，使得程序逻辑正确、完整。所填写的代码不超过一条语句（即不能出现分号）。把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。编程题要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果的时候才有机会得分。注意：在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。对每个题目，要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。1. 代码填空 （满分9分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读和调试题目提供的源代码，根据要求填写缺失的代码部分。int JC = 1,1,2,6,24,120,720,5040,40320,362880;int i;for(i=100; i1000; i+)int sum = 0;int x = i;while(_)sum += JCx%10;x /= 10;if(i=sum) printf(%dn, i);注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。2. 代码填空 （满分14分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读和调试题目提供的源代码，根据要求填写缺失的代码部分。加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。下面的代码演示了如何实现该功能。请仔细阅读，填写空缺的代码（下划线部分）。注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。void f(char* buf, unsigned char* uckey, int n)int i;for(i=0; in; i+)bufi = bufi uckeyi;int main(int argc, char* argv)char p = abcd中国人123; / 待加密串char* key = 11001100010001110; /以串的形式表达的密匙，运算时要转换为按位存储的形式。int np = strlen(p);int nk = strlen(key);unsigned char* uckey = (unsigned char*)malloc(np); / 密匙串需要按位的形式循环拼入 uckey中int i;for(i=0; inp*8; i+)if(keyi%nk=1)_; / 填空1else_; / 填空2f(p, uckey, strlen(p);f(p, uckey, strlen(p);printf(%sn, p);free(uckey);return 0;注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。3. 程序设计（满分19分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读题目要求，根据题意编写调试代码。为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。我们希望寻找到能除尽1至n的的每个数字的最小整数。不要小看这个数字，它可能十分大，比如n=100, 则该数为：69720375229712477164533808935312303556800请编写程序，实现对用户输入的 n （n100）求出1n的最小公倍数。例如：用户输入：6程序输出：60用户输入：10程序输出：2520要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。4. 程序设计（满分28分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读题目要求，根据题意编写调试代码。为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。线1苹果园古城路八角游乐园八宝山玉泉路五棵松万寿路公主坟军事博物馆木樨地南礼士路复兴门西单天安门西天安门东王府井东单建国门永安里国贸大望路四惠四惠东线2西直门车公庄阜成门复兴门长椿街宣武门和平门前 门崇文门北京站建国门朝阳门东四十条东直门雍和宫安定门鼓楼大街积水潭线4公益西桥角门西马家堡北京南站陶然亭菜市口宣武门西单灵境胡同西四平安里新街口西直门动物园国家图书馆魏公村人民大学海淀黄庄中关村北京大学东门圆明园西苑北宫门安河桥北线5天通苑北天通苑天通苑南立水桥立水桥南北苑路北大屯路东惠新西街北口惠新西街南口和平西桥和平里北街雍和宫北新桥张自忠路东四灯市口东单崇文门磁器口天坛东门蒲黄榆刘家窑宋家庄线8森林公园南门奥林匹克公园奥体中心北土城线10巴沟苏州街海淀黄庄知春里知春路西土城牡丹园健德门北土城安贞门惠新西街南口芍药居太阳宫三元桥亮马桥农业展览馆团结湖呼家楼金台夕照国贸双井劲松线13西直门大钟寺知春路五道口上地西二旗龙泽回龙观霍营立水桥北苑望京西芍药居光熙门柳芳东直门其中第一行数据为地铁线名，接下来是该线的站名。当遇到空行时，本线路站名结束。下一行开始又是一条新线.直到数据结束。如果多条线拥有同一个站名，表明：这些线间可以在该站换车。为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：1. 每条线路可以单独购票，票价不等。2. 允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。单线票价和联合票价如 price.txt 所示。线1 180线2 250线4 160线5 270线8 175线10 226线13 114线1,线2 350线1,线10 390线1,线5 410线1,线4 330线10,线13 310线2,线5 390线4,线10 370线4,线13 260每行数据表示一种票价线名与票价间用空格分开。如果是联票，线名间用逗号分开。联票只能包含两条可换乘的线路。现在的问题是：根据这些已知的数据，计算从A站到B站最小花费和可行的换乘方案。比如，对于本题目给出的示例数据如果用户输入：五棵松,奥体中心程序应该输出：-(线1,线10)-线8 = 565如果用户输入：五棵松,霍营程序应该输出：-线1-(线4,线13) = 440可以看出，用户输入的数据是：起始站，终到站，用逗号分开。程序输出了购票方案，在括号中的表示联票，短横线(-)用来分开乘车次序。等号后输出的是该方案的花费数值。请编程解决上述问题。注意：1. 我们测试您的程序时，所用数据与题目中的示例数据不同，但格式完全一样。2. 当多个方案有相同的最小花费，输出任意一个方案即可。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。5. 程序设计（满分30分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读题目要求，根据题意编写调试代码。BMP是常见的图像存储格式。如果用来存黑白图像（颜色深度=1），则其信息比较容易读取。与之相关的数据：（以下偏移均是从文件头开始）偏移：10字节, 长度4字节： 图像数据真正开始的位置。偏移：18字节, 长度4字节： 位图的宽度，单位是像素。偏移：22字节, 长度4字节： 位图的高度，单位是像素。从图像数据开始处，每个像素用1个二进制位表示。从图片的底行开始，一行一行向上存储。Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数，不足的位均以 0 填充。例如，图片宽度为45像素，实际上每行会占用8个字节。可以通过Windows自带的画图工具生成和编辑二进制图像。需要在“属性”中选择“黑白”，指定为二值图像。可能需要通过 查看 | 缩放 | 自定义. 把图像变大比例一些，更易于操作。图像的左下角为图像数据的开始位置。白色对应1，黑色对应0我们可以定义：两个点距离如果小于2个像素，则认为这两个点连通。也就是说：以一个点为中心的九宫格中，围绕它的8个点与它都是连通的。如：t1.bmp 所示，左下角的点组成一个连通的群体；而右上角的点都是孤立的。程序的目标是：根据给定的黑白位图，分析出所有独立连通的群体，输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。输入数据固定存在in.bmp中。如示例的in.bmp,程序应该输出：128152133该输出表示：共有4个连通群体。输出的连通体面积间的顺序可以随意。请编程解决上述问题。我们测试程序的时候，会使用不同的in.bmp文件。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答