中科大计算机考研2006-2012机试试题

王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！中科大计算机考研2012复试机试试（感谢王道论坛“林影清风”版主）本次机试两个半小时，共5题。1.字符串处理：从string.in文件里读入两个字符串，字符串除了数字还可能包括'—'、'E'、'e'、'．'，相加之后输出到文件string.out中，如果是浮点型，用科学计数法示（最多包含10个有效数字）。SampleInput:SampleOutput:34.562.7956e22.45e22.最大公约数：从number.in文件中读入n个数，求出这n个数的最小值、最大值以及它们两的最大公约数，输出到文件number.out中。number.in中第一行为n，接下来为n个大于零的整数。SampleInput:SampleOutput:34844863.任务调度：从task.in文件中读入任务调度序列，输出n个任务适合的一种调度方式到task.out中。每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后继任务。SampleInput:SampleOutput:Task0(Task1,Task2)Task0Task1Task3Task2Task1(Task3)Task2(NULL)Task3(NULL)4.火车票订购：火车经过X站，火车最大载客人数为m，有n个订票请求，请求订购从a站到b站的k张票，若能满足订购要求则输出1，否则输出0。数据从ticket.in中输入，第一行有四个数，分别为n，m。接下来有n行，每行三个数分别为a，b，k。结果输出到文件ticket.out中。SampleInput:SampleOutput:510141090812218121114208030300155.最短路径：有n个城市m条道路（n<1000,m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离，并且输出经过的城市的名，如果有多条，输出字典序最小的那条；若从s到t没有路径，则输出“can'tarrive”。从road.in中读入数据，第一行有四个数，分别为n，m，s，t。接下来m行，每行三个数，分别为两个城市名和距离。输出结果到road.out中。王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！SampleInput:SampleOutput:33132133123121231============================================================================测试数据不完全一样，但题目意思是差不多的。这次机试，整体感觉难度一般，其中第1题有简单的做法，但是要熟悉scanf/printf的输入输出参数，如果真的当成字符串进行处理的话将会非常麻烦；第2题属于简单的题，主要是考辗转相除法求最大公约数；第3、5题是关于图的拓扑排序以及Dijkstra算法求最短路径问题，如果平时没写过相关的程序的话，这两题很难在考试的时候写出完整的程序；第4题将题目意思看懂也是一个简单的题。我拿到题目，先做第一题，当然第一想法是字符串处理，将输入的两个字符串先转化成double型数，写着发现很复杂，有正负、有小数点、有e，这要用编译原理里面的正则式来做多复杂啊....直接跳过去，发现第2题简单，先用了不到5分钟给敲完测试完了。扫了一下第5题，发现这是最短路径的问题，这题有信心可以搞定，与之前写的还是有区别，这题要考虑没有路径的情况以及还要打印路径。写完之后测试了几组数据，包括没有路径的，感觉差不多应该可以了。接着看第3题，看完题目明白是拓扑排序的题，但得提取出字符串中的数字作为图的顶点，写的还算比较顺的。又回到第一题，感觉应该第一题不应该会很难的，想到C语言输入/输出有相应的参数可以处理浮点数，但无奈却不记得了。使劲按F1试图找到MSDN，发现没有装。没办法，还是自己写字符串处理吧...写着发现没有信心把这个程序写完整，再次搁置。还有第4题，开始题目意思理解错了，写出来测试发现错了，又仔细读了一遍，OK,很简单的一个题，用一个数组保存每个站已经载的人数，对于每个请求，看看从a~b的区间中加上k是否有超载的即可。第三次回到第1题，想到有个atof（）的函数可以将字符串转化为double型，果断用了，但输出怎么办，总是输出不了题目要求的那种格式。最后没办法自己写个函数将double型的m输出为科学计数法...用了一个log10()求出指数e,然后num/pow(10,e)得到有效部分，再追加输出一个字符e，以及指数的值，看着挺像的。真是折腾人，本来最简单的一个题，弄得最复杂了。中科大计算机考研2011复试机试试题（感谢王道论坛“lven”、“水东流”和“loujian_1989”道友）1．给两个十进制数，先异或，然后输出其二进制形式；2．一共有十二个球，其颜色有红、黄、黑三种，红黄黑分别有想x，y，k个，现在从其中取出八个球，共有多少种取法，输出到文件中？（x，y，k是从键盘输入，痛颜色的球不区分）输出格式;这有种取法：1.种红球，黄球，黑球；……3．是一个字符串匹配的问题，读入文件input.txt，看是否匹配一个格式（具体什么格式我不记得了，但这题有点难，我没做出来）。王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！本题“水东流”道友的描述：在文件（相对地址）3.txt中查看是否有模式abcde。若有，输出“找到abc*d?e匹配”；若无，则输出“没有找到abc*d?e匹配”。本题“loujian_1989”道友的描述：给你一个文本，里面有各种字符串标点啥的，问你是不是有符合ab*d?e（*表示多个任意字符，？表示一个任意字符）的匹配，本质上是一个NFA，化成DFA就出来了。其中*代表任意个数。？代表一个或零个。（即正则表达式）4．从文件中读入一个二叉树，然后后序遍历该二叉树。4//表示节点个数124//2是节点1的左孩子，4为右孩子203//0表示没有左孩子300400本题“loujian_1989”道友的描述：给你一个二叉树，每个节点有编号，给你一个序列，每个节点给了左孩子和右孩子的编号，让你输出这个二叉树的后序遍历结果。我的做法是加一个父亲节点域，用来找到父亲节点，然后写一个后续遍历的递归程序。第3题“水东流”道友的代码如下：我画出了该模式的DFA图，然后写出了一下代码。可知，只要适当修改move数组，可匹配任意模式。1.#include"iostream"2.usingnamespacestd;3.4.intInitiaMove(intmove[5][5]){5.for(inti=0;i<5;i++)6.{7.for(intj=0;j<5;j++)8.{9.move[j]=1;10.}11.}12.move[1][0]=2;13.move[2][1]=3;14.move[3][2]=3;15.move[3][3]=4;16.move[3][4]=5;17.move[4][4]=5;18.return0;19.}20.21.intmain()22.{23.FILE*fp;24.fp=fopen("3.txt","r+");25.charfile_c;王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！26.ints;27.intmove[5][5];28.29.InitiaMove(move);30.31.s=1;32.while((!feof(fp))&&(s!=5))33.{34.file_c=fgetc(fp);35.if(('a'<=file_c)&&(file_c<='e'))36.{37.s=move[file_c-'a'];38.}39.else40.s=1;41.}42.43.if(s==5)44.{45.printf("找到abc*d?e匹配\n");46.}47.else48.{49.printf("没有找到abc*d?e匹配\n");50.}51.52.return0;53.}中科大计算机考研2010复试机试试题（感谢王道论坛“lowtec”和“baisy”道友）第一题：input.txt文件里面有一段文章，由字符串和一些特殊字符构成。先把input文件中的内容读入缓冲区，在从缓冲区中取字符，进行如下操作：1.如果是字符，空格，输出2.如果是'!'，删除前面一个字符3.如果是'*'，删除前面1行字符串4.如果是'>'，讲前面一个单词的首字符，进行大小写转化5.如果是数字，则不作任何操作第二题：从键盘输入N，建立N*N矩阵，每个元素是一个字符串，为每个元素赋值。然后求出按字典序排列最大的元素所在的行列。王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！第三题：已知二叉排序树用二叉链表存储，结点的关键字为1正整数。从键盘输入结点的关键字（以0表示结束）建立一棵二叉排序树，并输出其后序遍历序列。例如输入：402060700输出：20706040中科大计算机考研2009复试机试试题（感谢王道论坛“lowtec”和“baisy”道友）机试一小时,共三题机试分三组进行,每组又有A、B卷,共六套卷第一组试卷A（共分3组，每组又分A/B卷，很抱歉只能提供这一组的试题，别的没搞到）1.输入：0~65535的十进制数处理：比如输入4，转化为16位二进制数0000000000000100，4个一组，相异或，变为0001，然后把0001转化为十进制的1输出输出:12.键盘输入n个数处理:将n个数由小到大排序，如果n是奇数，输出正中间的数；如果n是偶数，输出正中间的两个数3.输入：文件读入类ABC00DE00...的二叉树先序序列，0表示叶子输出：中序输出深度<=depth/2的节点，其中depth是你所建立的树的深度中科大计算机考研2008复试机试试题08复试上机题上午组1./////////////一个十进制正整数转换成二进制有多少个12.////////////////约瑟夫环问题3.///////////////////从文件读入2个矩阵，输出矩阵相乘后的矩阵4.///////////字符串问题。从文件中读入几行英文句子。输出单词，行号，并按单词字典索引。08上午////////1.输入一个十进制数，输出二进制0，1串中1的个数王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！//////2，fib函数求出n，然后就是n个小孩喊m出圈的问题3，//////////一个文件中的两个矩阵相乘输出到另一个文件上，abc.in232312121112233一个文件中的两个矩阵相乘输出到另一个文件上，第一行是三个整数mnl，输入2，3，2//矩阵下标312121112233输出221111//////4，字典索引的建立，一个文件第一行是行数如输入4iam王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！astudentformchinaam输出i1am1a2student2from2china3am408下午组1./////////输入十进制正整数将其转换成任意的进制2.///////从文件读入2个矩阵，转置后相加再输出3.//////字符串问题，给几个字符串集合，每个集合中有若干的单词，找出每个集合中都有的单词4.//////////////////给一个先序(中序)遍历序列，按层次输出该树的结点08下午//////1。一个10进制m转成n进制，输出//////2.一个m*n矩阵先转置，再和一个n*m矩阵相加///////3，读入一个文件，第一行是字符串集合个数，第二行到第五行是这四个集合，从中找到，字符串集合中出现两次的字符串然后标识出第几个集合（行数），输出到一个文件如4Iamastdudentfromchina王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！amnot运行am14，////////////一个二叉树的先序序列，按层遍历?中科大计算机考研2007复试机试试题07上午上机题目（2小时）1.////////////编写程序，判断回文数，如输入：121，输出：Y，出入：234，输出：N，最大位数为13；（本人注：用char类型数组实现之较方便，但是主要非字符的判断）2.///////////////队列的循环报数问题3./////////////图的最小生成树；4.后序中序得先序07年下午（王道论坛分享）://////////1.输入字符串，倒序输出，例如：输入IcomefromChina.输出ChinafromcomeI.（单词不需倒序，只是句子倒了）///////2.输入一个数判断是不是完数，是输出yes，不是输出no//////////3.文件读取一个文件，做无向图的广度遍历输出，文件的第一行是图的节点个数，后面是边的信息，00表示结束例如文件：41214232434王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！00最后输出1243到文件上///////////////4.没有括号只有加减乘除的表达式求值，表达式从文件读入，计算的结果输出到文件上。中科大计算机考研2006复试机试试题上机题目（3小时）///求矩阵的转置；////写一程序，用来判断C语言中的变量命名是否合法；编写一程序，求逆波兰式（含括号情况），如：a-b*(c+d)转换成：abcd+*-；?????????????给定两个数m,n，实现如下功能：如m=3,n=4时，输出：123124134234////////////5．给定一无向图的矩阵存储，求其最大连通分量；////////////6．给顶一系列整数，求连续位置的数的最大和，如：23，-12，22，33，2；最大和为22+33+2=57；（好象是这个题目，也许是关于质数的其他数论相关的题目，记不清楚了）////////7．给定一年月，判断该月有多少天；06年:上午（王道论坛分享）////////第一道,读int矩阵文件,将之转置后输出.简单./////////第二道,给出四个[年,月],判断此月有多少天.题目给出了闰年判断的伪代码./////////第三道,给出一些标识符,判断合法标识符有多少个.(与C语言中标识符定义一致.)///////////////第四道,给出无向图连接矩阵,求各个连同分量./////////第五道,给出一个整数分解成尽可能多的连续整数的和.例如///////////////第六道,给出带括号的四则运算表达式,要求给出逆波兰式??????????第七道,递归列出的所有条目.例如m=3,n=4时,结果为王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！4,3,24,3,14,2,13,2,106下午（王道论坛分享）//////////第一题，统计一个字符串当中有多少字母、数字、空格和其它字符；/////////第二题，给你一个10进制数，要你输出8进制数；/////////第三题，给你一个数，要求你求出这个数与其反序数的和相加多少次才可以得到回文字，比方说给你5656+65=121，是回文字，所以输出1；给你15681568+8651=10219，不是回文字，继续，10219+91201=101410，不是回文字，继续，101410+014101=115511，是回文字，结束，输出3；///////////////第四题，给你一个数列，求出最大子序列之和；???????第五题，给你几个整数，求出最大的组合数，比如:12345678最大的组合是:78456123；////////////////////第六题，关于图的最大连通分量/////////////////////第七题，利用二叉树，给你先序和中序遍历，输出后续遍历面试分A，B两个步骤：A英语口语测试，比较简单，不属于卡人的地方；王道论坛www.cskaoyan.com王道论坛（www.cskaoyan.com）友情分享！予人玫瑰手留余香！B专业知识测试，比较广泛，基本都是概念，很简单，但是特别重要，考官的主观性较强，起决定性作用；王道论坛www.cskaoyan.com