上海交大计算机考研复试机试

《上海交大计算机考研复试机试》由会员分享，可在线阅读，更多相关《上海交大计算机考研复试机试（20页珍藏版）》请在金锄头文库上搜索。

1、我自己在准备考研时曾做了下 06，07，08，09 年的题目，并且在博客中提供了一个参考的 题解，10 年的题目以及 11 年保研的题目有空我会再做做，毕竟现在上研了没多少时间研究 这些，祝大家考出个好成绩，支持王道论坛()交大版。 解答请关注我的个人博客。 这个 PDF 文档里的参考答案不是我给出的， 有些代码是是有问题 的，但思路是正确的。 我可能近期内会把历年题目做一个分类，并全部提供一个参考的题解和程序，哪位获得较高 初试分数正在备战复试的同学可以与我联系， 另外本次重新整理这些题目的时候， 基本上都加了一些个人的注解另外本次重新整理这些题目的时候， 基本上都加了一些个人的注解和思路和

2、思路， 如果有不对或欠， 如果有不对或欠 妥的地方妥的地方或者你有更好的想法或者你有更好的想法，请你与我联系，谢谢！，请你与我联系，谢谢！ 靖难（http:/www.longbin.org）2011 年 2 月 18 2005 年上机试题年上机试题 问题问题 1： 网上回忆版的原文如下网上回忆版的原文如下 太恐怖了， 12 翻一下是 21 对吗？ 34 翻一下是 43 对吗？ 12+34 是 46 对吗？46 翻一下是 64 对吗？ 现在给你 21 与 43，把 64 输出就可以了。 我猜题目的大概意思是给定整数我猜题目的大概意思是给定整数 a,b， 若， 若 reverse(a)+rever

3、se(b)=reverse(a+b)则输出则输出 a+b,否则否则 输出输出 NO 总之这应该是一道颇为简单的题目，鉴于交大喜欢使用总之这应该是一道颇为简单的题目，鉴于交大喜欢使用 NOIP 原题作为复试题，类似的题目原题作为复试题，类似的题目 作为练习我推荐一道作为练习我推荐一道 NOIP 题目题目 http:/ 问题问题 2： 给你一串路径，譬如 abc ade bcst d 你把这些路径中蕴涵的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右 缩一格，就象这样 a b c d E b cst d 同一级的需要按字母顺序排列，不能乱。 为了方便看清题目意思， 我划表格表达了一下层

4、次关系。为了方便看清题目意思， 我划表格表达了一下层次关系。 本题其实关键是找到合适的数据结本题其实关键是找到合适的数据结 构来存储构来存储 初步思考了一下，可以考虑使用有序的初步思考了一下，可以考虑使用有序的 N 叉树来存储，第一层目录的你节点记为叉树来存储，第一层目录的你节点记为 0，然后使，然后使 用类似于先序遍历的方式来遍历，用一个全局变量来记录当前递归深度，并控制空格数量。用类似于先序遍历的方式来遍历，用一个全局变量来记录当前递归深度，并控制空格数量。 有空我会试写一下代码。有空我会试写一下代码。 问题问题 3. 回忆版原文如下：回忆版原文如下： 这题听说.有点问题。反正大概意思是这

5、样的(除非我理解错了.)： 有一个 x66 任意的 0=2 Write a program to calculate the Fibonacci Numbers. Input The input file contains a number n and you are expected to calculate Fn.(0n; couts; ft; coutn; coutA)的循环结构。当我把第四题做完的时 候已经是四点一刻了，我回过头来检查了已经做好的这三个题目，保证滴水不漏。然后我又 回过头来做第二题，但是最后仍然没得出正确结果。不过我仍然比较高兴，毕竟剩下三个题 目基本能保证通过所有黑盒

6、测试。 09 年回忆版年回忆版 II 今年是 4 题。 1.求二个日期间的天数相差，如果二天是连续的，我们认为有二天。如果数据不符合要求， 输出 0；格式是 YYYYDDMM INPUT： 20090411 20090411 2009.。 。(忘记） 2008.。 。 2009 2 29 2008 2 29 OUT 1 . 0 这题说白了就是把去年第 4 题给翻新一下，基本思想都不变，注意数据的合法性判断， （超 多，我写了一个很长的 JUDGE 函数） ，这题做起来要点时间， 我花了 30+分钟。 二： 怨念啊怨念， 。 。 。 。 。 。intergral 竟然是积分的意思，英文超长，如果

7、有机会看到 PDF 大家就能 领略了，给了你一个矩阵，让你求矩阵的积分， 。 。 。 这题超级无语，做了一个半小时，最后实在忍不住问监考学长，学长充满爱怜的问：你是不 是不知道什么意思，然后放低声音（就是积分啊） 。 。 。 。 周围的同学也一片哗然，估计也没看懂。 。 。 。 ，立马明白怎么做 但是此时离时间到还有不到 2 分钟，也没心情改了，此处为另一次失误，因为我程序的框架已经完全写好，只要加下求 给出数据的面积就行了。 而且关键是， 到时间了不收卷， 竟然在分发奖学金申明要我们签字， 此时有同学在狂调，不知道是否能多弄几分。 三： 就是一个模拟题，二个数字，输入后给 4 个数字 a,b

8、,c,d 第一个数组的第 a 到第 b 个，第二 个的第 c 到第 d 个。 放到一个新数组，求处于中间位置的数。 就是一个简单的模拟题，估计所有人都能拿分，但是细节还是要注意的。 四： 随便给一行字，要你求出大小写字符出现的次数， 大家估计只要熟悉 getline 和字符 ASCII 码使用的估计都能写出来吧。 也挺简单的 。 我个人做了一 三 四，一个小时出头全部搞定，然后傻看第二题，简直无语，如果今年死在 这个题上，也是和交大无缘吧。 10 年回忆版 上午八点半到十一点机试，实际上九点才开始，前半个小时是试机用的，两个半小时解决 4 道题，是比较紧张的。 第一题，后缀数组，唯一一道菜鸟题

9、 输入 grain 对其子串 grain rain ain in n 分别编号为 0，1，2，3，4 然后对各子串按字典顺序排序，即： ain,grain,in,n,rain 输出 2，0，3，4，1 大概的思路就是定义一个结构体,包括两个成员，一个是编号，一个是指向该子串位置的指 针，然后按字符串比较进行快速排序，输出便可以了。 第二题 最短路径 第一行输入 N,M N 表示城市的个数，各城市编号为 0 到 N-1，N 的范围我记不清了，不过主要的难题不在这 M 表示道路的条数，道路也是 0 到 M-1 编号，第 K 条道路的长度为 2K ，问题主要在于 K 可以非常大，比如 495 接下来

10、 M 行输入 M 条道路中每条连结的两个城市编号 输出编号为 0 的城市与其它各城市的最短距离大小， 数值太大的以 MOD 100000 的结果输出 这个问题可以直接 Dijkstra 算法，我只做出了 int64 表达范围的结果，超出的要么用大数运 算，要么用某些数论的知识。曾经学过有 2 的高次幂 MOD 运算，不过不记得了。 提示：提示： 把存下来的距离改成道路标号就可以了，只存当前到这个节点的每条路径的最大的一个标把存下来的距离改成道路标号就可以了，只存当前到这个节点的每条路径的最大的一个标 号，可以证明，如果一条路径的所有标号的最大值大于另一条路径，那么这条路径的代价号，可以证明，如

11、果一条路径的所有标号的最大值大于另一条路径，那么这条路径的代价 一定大于另一条，别忘了一定大于另一条，别忘了 20+21+.2n = 2(n+1) - 1 这个基本等式。这个基本等式。 第三题 中缀表达式运算 这题其实非常常见，而且没有括号，只有+*/四种运算，不过也只解决了 60%的数据 注：注： 因为没有括号， 所以其实直接扫描就可以了， 而因为没有括号， 所以其实直接扫描就可以了， 而且题的数据说明中有说且题的数据说明中有说纯纯+， -的占多少，的占多少， 纯纯*/的占多少，所以即使你不会处理优先级，也要扫描法把这部分数据搞定。的占多少，所以即使你不会处理优先级，也要扫描法把这部分数据搞

12、定。 建议大家把后缀前缀中缀的求值都学会吧，呵呵。建议大家把后缀前缀中缀的求值都学会吧，呵呵。 第四题 最小面积子矩阵 定义矩阵中元素个数为矩阵面积 输入 N M K 然后就输入 N 行 M 列的数，在这个矩阵中所有元素和不小于 K 的最小的子矩阵。 这题一看就知道用 DP,可惜一直没想出 DP 的转移方程，就用穷举了，但数据规模太大，穷 举也只能过其中部分数据，大约 30%吧 注：注：暴力的方法比较容易想到，也就是用暴力的方法比较容易想到，也就是用 DFS解答树的建立可以参考一下二维的最大子段解答树的建立可以参考一下二维的最大子段 和问题。和问题。不过暴力的解法显然是不能得满分的，数据规模超级大的说。不过暴力的解法显然是不能得满分的，数据规模超级大的说。 另外也有另外也有 DP 的解法，只不过我懒，就没想咯的解法，只不过我懒，就没想咯有想出来的吱一声。有想出来的吱一声。