王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
中科大计算机考研 2012 复试机试试题
(感谢王道论坛“林影清风”版主)
本次机试两个半小时,共 5 题。
1. 字符串处理:从 string.in 文件里读入两个字符串,字符串除了数字还可能包括 '—'、
'E'、'e'、'.',相加之后输出到文件 string.out 中,如果是浮点型,要求用科学计数法表示(最
多包含 10 个有效数字)。
Sample Input: Sample Output:
34.56 2.7956e2
2.45e2
2. 最大公约数:从 number.in 文件中读入 n 个数,求出这 n 个数的最小值、最大值以
及它们两的最大公约数,输出到文件 number.out 中。number.in 中第一行为 n,接下来为 n
个大于零的整数。
Sample Input: Sample Output:
3 4 8 4
4 8 6
3. 任务调度:从 task.in 文件中读入任务调度序列,输出 n 个任务适合的一种调度方式
到 task.out 中。每行第一个表示前序任务,括号中的任务为若干个后序任务,表示只有在前
序任务完成的情况下,后序任务才能开始。若后序为 NULL 则表示无后继任务。
Sample Input: Sample Output:
Task0(Task1,Task2) Task0 Task1 Task3 Task2
Task1(Task3)
Task2(NULL)
Task3(NULL)
4. 火车票订购:火车经过 X 站,火车最大载客人数为 m,有 n 个订票请求,请求订购
从 a 站到 b 站的 k 张票,若能满足订购要求则输出 1,否则输出 0。数据从 ticket.in 中输入,
第一行有四个数,分别为 n,m。接下来有 n 行,每行三个数分别为 a,b,k。结果输出到
文件 ticket.out 中。
Sample Input: Sample Output:
5 10 1
4 10 9 0
8 12 2 1
8 12 1 1
14 20 8 0
30 300 15
5. 最短路径:有 n 个城市 m 条道路(n<1000, m<10000),每条道路有个长度,请找到
从起点 s 到终点 t 的最短距离,并且输出经过的城市的名,如果有多条,输出字典序最小的
那条;若从 s 到 t 没有路径,则输出“can't arrive”。从 road.in 中读入数据,第一行有四个
数,分别为 n,m,s,t。接下来 m 行,每行三个数,分别为两个城市名和距离。输出结果
到 road.out 中。
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
Sample Input: Sample Output:
3 3 1 3 2
1 3 3 1 2 3
1 2 1
2 3 1
============================================================================
测试数据不完全一样,但题目意思是差不多的。这次机试,整体感觉难度一般,其中第
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//表示节点个数
1 2 4 //2 是节点 1 的左孩子,4 为右孩子
2 0 3//0 表示没有左孩子
3 0 0
4 0 0
本题“loujian_1989”道友的描述:给你一个二叉树,每个节点有编号,给你一个序列,每
个节点给了左孩子和右孩子的编号,让你输出这个二叉树的后序遍历结果。我的做法是加一
个父亲节点域,用来找到父亲节点,然后写一个后续遍历的递归程序。
第 3 题“水东流”道友的代码如下:
我画出了该模式的 DFA 图,然后写出了一下代码。可知,只要适当修改 move 数组,可匹配任意模式。
1. #include "iostream"
2. using namespace std;
3.
4. int InitiaMove(int move[5][5]){
5. for (int i=0;i<5;i++)
6. {
7. for (int j=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. return 0;
19. }
20.
21. int main()
22. {
23. FILE * fp;
24. fp=fopen("3.txt","r+");
25. char file_c;
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
26. int s;
27. int move[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. else
40. s=1;
41. }
42.
43. if (s==5)
44. {
45. printf("找到 abc*d?e匹配\n");
46. }
47. else
48. {
49. printf("没有找到 abc*d?e 匹配\n");
50. }
51.
52. return 0;
53. }
中科大计算机考研 2010 复试机试试题
(感谢王道论坛“lowtec”和“baisy”道友)
第一题: input.txt 文件里面有一段文章,由字符串和一些特殊字符构成。先把 input 文件中的
内容读入缓冲区,在从缓冲区中取字符,进行如下操作:
1.如果是字符,空格,输出
2.如果是'!',删除前面一个字符
3.如果是'*',删除前面 1 行字符串
4.如果是'>',讲前面一个单词的首字符,进行大小写转化
5.如果是数字,则不作任何操作
第二题: 从键盘输入 N,建立 N*N 矩阵,每个元素是一个字符串,为每个元素赋值。然后求
出按字典序排列最大的元素所在的行列。
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
第三题: 已知二叉排序树用二叉链表存储,结点的关键字为 1 正整数。从键盘输入结点的关
键字(以 0 表示结束)建立一棵二叉排序树,并输出其后序遍历序列。
例如
输入:40 20 60 70 0
输出:20 70 60 40
中科大计算机考研 2009 复试机试试题
(感谢王道论坛“lowtec”和“baisy”道友)
机试一小时,共三题
机试分三组进行,每组又有 A、B 卷,共六套卷
第一组 试卷 A (共分 3组,每组又分 A/B卷,很抱歉只能提供这一组的试题,别的没
搞到)
1.输入:0~65535 的十进制数
处理:比如输入 4,转化为 16位二进制数 0000 0000 0000 0100 ,4个一组,相异或,
变为 0001,然后把
0001转化为十进制的 1输出
输出:1
2.键盘输入 n个数
处理:将 n个数由小到大排序,如果 n是奇数,输出正中间的数;如果 n是偶数,输出
正中间的两个数
3.输入:文件读入类 ABC00DE00...的二叉树先序序列,0表示叶子
输出:中序输出深度<=depth/2的节点,其中 depth 是你所建立的树的深度
中科大计算机考研 2008 复试机试试题
08 复试上机题
上午组
1. /////////////一个十进制正整数转换成二进制有多少个 1
2. ////////////////约瑟夫环问题
3. ///////////////////从文件读入 2 个矩阵,输出矩阵相乘后的矩阵
4. ///////////字符串问题。从文件中读入几行英文句子。输出单词,行号,并按单词字典索
引。
08上午
////////1.输入一个十进制数,输出二进制 0,1串中 1的个数
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
//////2,fib函数求出 n,然后就是 n个小孩喊 m出圈的问题
3,//////////一个文件中的两个矩阵相乘输出到另一个文件上,
abc.in
2 3 2
3 1 2
1 2 1
1 1
2 2
3 3
一个文件中的两个矩阵相乘输出到另一个文件上,
第一行是三个整数 m n l,
输入 2,3,2//矩阵下标
3 1 2
1 2 1
1 1
2 2
3 3
输出 2 2
1 1
1 1
//////4,字典索引的建立,一个文件第一行是行数
如输入 4
i am
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
a student form
china
am
输出
i 1
am 1
a 2
student 2
from 2
china 3
am 4
08 下午组
1. /////////输入十进制正整数将其转换成任意的进制
2. ///////从文件读入 2 个矩阵,转置后相加再输出
3. //////字符串问题,给几个字符串集合,每个集合中有若干的单词,找出每个集合中都有
的单词
4. //////////////////给一个先序(中序)遍历序列,按层次输出该树的结点
08 下午
//////1。一个 10进制 m转成 n进制,输出
//////2.一个 m*n矩阵先转置,再和一个 n*m矩阵相加
///////3,读入一个文件,第一行是字符串集合个数,第二行到第五行是这四个集合,从中
找到,字符串集合中出现两次的字符串
然后标识出第几个集合(行数),输出到一个文件
如 4
I am
a stdudent
from china
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
am not
运行 am 1
4,////////////一个二叉树的先序序列,按层遍历?
中科大计算机考研 2007 复试机试试题
07上午上机题目(2小时)
1.////////////编写程序,判断回文数,如输入:121,输出:Y,出入:234,输出:N,
最大位数为13;(本人注:用char类型数组实现之较方便,但是主要非字符的判断)
2.///////////////队列的循环报数问题
3./////////////图的最小生成树;
4.后序中序得先序
07 年下午(王道论坛分享):
//////////1.输入字符串,倒序输出,例如:输入 I come from China.输出 China from come I.(单
词不需倒序,只是句子倒了)
/////// 2.输入一个数判断是不是完数,是输出 yes,不是输出 no
////////// 3.文件读取一个文件,做无向图的广度遍历输出,文件的第一行是图的节点个
数,后面是边的信息,0 0 表示结束
例如文件:
4
1 2
1 4
2 3
2 4
3 4
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
0 0
最后输出 1 2 4 3 到文件上
/////////////// 4.没有括号只有加减乘除的表达式求值,表达式从文件读入,计算的结果
输出到文件上。
中科大计算机考研 2006 复试机试试题
上机题目(3小时)
///求矩阵的转置;
////写一程序,用来判断C语言中的变量命名是否合法;
编写一程序,求逆波兰式(含括号情况),如:a-b*(c+d)转换成:abcd+*-;
?????????????给定两个数m,n,实现如下功能:如m=3,n=4时,输出:
1 2 3
1 2 4
1 3 4
2 3 4
////////////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,2
4,3,1
4,2,1
3,2,1
06 下午(王道论坛分享)
//////////第一题,统计一个字符串当中有多少字母、数字、空格和其它字符;
/////////第二题,给你一个 10 进制数,要你输出 8 进制数;
/////////第三题,给你一个数,要求你求出这个数与其反序数的和相加多少次才可以得到回
文字,
比方说给你 56
56+65=121,是回文字,所以输出 1;
给你 1568
1568+8651=10219,不是回文字,继续,
10219+91201=101410,不是回文字,继续,
101410+014101=115511,是回文字,结束,输出 3;
///////////////第四题,给你一个数列,求出最大子序列之和;
???????第五题,给你几个整数,求出最大的组合数,
比如:123 456 78
最大的组合是:78456123;
////////////////////第六题,关于图的最大连通分量
/////////////////////第七题,利用二叉树,给你先序和中序遍历,输出后续遍历
面试分A,B两个步骤:
A 英语口语测试,比较简单,不属于卡人的地方;
王道论坛(www.cskaoyan.com)友情分享!予人玫瑰 手留余香!
王道论坛 www.cskaoyan.com
B 专业知识测试,比较广泛,基本都是概念,很简单,但是特别
重要,考官的主观性较强,起决定性作用;
本文档为【中科大计算机考研2006-2012机试试题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。