上海交大计算机复试机试,交大机试面试第一帖之10版-以及复试准备

----------------------------------------------

09版：http://www.cskaoyan.com/thread-12508-1-3.html

----------------------------------------------

今年的时间安排特别紧迫，

上午八点半到十一点机试，实际上九点才开始，前半个小时是试机用的，两个半小时解决4道题，是比较紧张的。

第一题，后缀数组，唯一一道菜鸟题

输入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条道路的长度为2^K ，问题主要在于K可以非常大，比如495

接下来M行输入M条道路中每条连结的两个城市编号

输出编号为0的城市与其它各城市的最短距离大小，数值太大的以MOD 100000的结果输出

这个问题可以直接Dijkstra算法，我只做出了int64表达范围的结果，超出的要么用大数运算，要么用某些数论的知识。曾经学过有2的高次幂MOD运算，不过不记得了。

第三题 中缀表达式运算

这题其实非常常见，而且没有括号，只有+—*/四种运算，不过也只解决了60%的数据

第四题 最小面积子矩阵

定义矩阵中元素个数为矩阵面积

输入N M K

然后就输入N行M列的数，在这个矩阵中所有元素和不小于K的最小的子矩阵。

这题一看就知道用DP,可惜一直没想出DP的转移方程，就用穷举了，但数据规模太大，穷举也只能过其中部分数据，大约30%吧

机试先说这么多，面试被老师问得很崩溃，书都白读了，看来我RP很有有问题，老师问了五六个专业课问题：

1.离散数学里面的归结证明你能说说吗？

2.什么是流密码？

2.密码学中的RSA公钥加密和RSA签名的关系？ (我本科信息安全，那老师恰好是研究安全的)

3.数据库中的查询操作是用什么数据结构实现的？用什么搜索算法？

4.你毕业设计做的是视频隐写分析，你知道什么是概率密码函数吗？视频帧之间的帧间差异你是怎么处理的？

5.英文题：描述一下今天上午上机的情况，你解决了多少个问题，你是如何设计这些算法的？

我是第一组第二个，比较郁闷，我们组是比较郁闷的，基本上每个人出来都叹气，我前面唯一一个400+的也被问得直叹气，呵呵。

其它有些组很轻松，有位帅哥被问喜欢看哪个古典名著，看过红楼梦没有喜欢什么样的音乐。。。。。。RP那叫一个好啊。

期待RP爆发，千万别死在面试上.

今天加上听力有关的：

听力真的很抽象，哈哈，除非是英语六级580+以上，或者是能听懂VOA标准语速，CNN新闻的那种呀，否则大家都差不多，哈哈

竟然还说明：本录音特意加入了干扰因素，哈哈，变态。

关于怎么准备，水平高的就听听VOA标准节目以及CNN的新闻吧，一般的就随便听听六级算了，哈哈，难怪前几届的都说听力是浮云

PS:今天有神牛说，英语听力是96年托福原题中节选的，好简单，囧。。。。。。。。。。。

---------------------------------------------------------------------------------------分隔线-----------------------------------------------------------

关于复试的准备，应当在初试以后，所以11年报考的同学现在最重要的就是把初试复习好。这里回答几个关于复试的问题。

12年打算报考的除非跨专业，否则就不要老关心考研了，把专业基础课学好，把英语六级过了，尽量的实习和做项目。

1.复试公平吗？

我认为交大的复试是非常公平的，基本上全是实力说话。如果你机试能考高分，那么面试的影响基本上可以忽略不计，因为交大复试是按机试+面试+听力总分算，并不像浙大一样要求面试必须及格。

但事实上，只要你RP不太损，老师面试都会给你一个大众水平的分。也就是不能太高调，态度要诚恳，不知道的老实回答并报以微笑比较好。

2.复试准备

机试：

A. 实现经典的数据结构，这个是必然的了，特别是图论和树有关的算法要熟悉。

04年机试考的已知前序中序求后序，以及今年考得最短路径。

B.算法设计中经典的问题要熟悉.

比如经典的DP问题 : 0-1背包、LCS, LIS，数的划分，最大子段和，二维最大子段和

经典的贪心法，回溯法，搜索算法等也要非常熟悉。

其次是高精度运算。

C 组合数学和数论中非常基本的问题。比如今年就考到一个2^n mod 100000这类的问题

D，过些时候我整理一些个人认为非常好的题型下来给大家。个人认为交大，清华，浙大三校的复试题应该是必做的。

面试：

面试没有什么好特别准备的，主要是英文自我介绍要准备一下，RP好的话英语问题也就这一个，不像我的那么囧。

也可以参考一下浙大版面经，但交大的老师几乎不问语言特性有关的问题，只问离散数据库等基础课程中的一些基本问题。

面试最重要的一点就是态度要端正，不会的就老实回答就行了，老师不会为难你，因为实际上老师更看重你的机试成绩。

英语听力：

这个好像除非大神，否则出入不会太大，听完后的感觉就是抽象。

拿点六级题听听，或者辅助一些CNN的新闻，VOA的标准语速

联系导师：

会有专门的导师见面会，但成绩出来后就可以给导师发邮件了。老师最看重的是你的机试成绩。

当然，有些老师要求数学成绩一定要好。

[本帖最后由 靖难 于 2010-4-1 09:27 编辑]