2012年复旦大学计算机考研复试笔试题目详细版

1．离散：这是第三次考的真题了！估计明年不会考了，但是以后就不一定了。
这个题目是个老题目了，考了很多年了。
已知G={<（x, y）, *> | x, y 是实数，x != 0 }，且(x, y)*(z, w)= (xz, xw+y) 。

求证：1。该G是个群
      2。证明H={<(1, y),*>| y实数}是其正规子群。
证法很简单。首先证明G是个半群
因为G是个代数系统 而且元素abc=a（bc），所以G是个半群
再找幺元e=(1,0),再求一个（x，y）的逆 证明逆肯定存在
得出G是个群
证明正规子群的时候更简单，找个a和a的逆然后证明aha-1一定属于H 就得出结论了。这个
题目在离散里很典型，希望后来者高度注意。

2. 组成原理：（英文题）
给一段汇编代码，要求对一段C代码进行填空。
汇编代码不是大家普遍学的那种，比如AX，BX，CX等寄存器，都是用的EAX，EBX，ECX。还涉及到一些其他我不懂的东西！可能要大家参考复旦本科用的教材！
汇编代码实现的功能是两个二维矩阵的变换，难读懂！


3. 计算机网络：
自动重传滑动窗口协议（发送窗口大小=接收窗口大小），地球到卫星的距离已知3000km（光的传播速率3*10^8m/s）发送速率1Mb/s，每帧长1kB，求最大效率时的表示帧序号的二进制位。
这道题王道的教材上有，不过协议好像改了，王道上好像用的是回退n帧还是什么的，但是原理是一样的。


4. 概率论：
联合密度函数
           F(x,y)=ae^(-X-Y)     0<X<1  0<Y<+∞   
求a值
求边缘密度
求z=max(x,y)密度函数

往年都考的是第一二章的内容，去年考了估计。今年考了个二维。复旦出题每年的变化还是比较大，这点要大家特别注意，不单只是要认真复习往年考过的点，没考过的点也一定要复习。


5. 软件工程：5个选择题，考内聚
内聚和耦合大家一定要记清楚顺序，而且要清楚每个内聚和耦合的定义。
软工的测试什么的大家也一定重点复习，这些点是比较好考的。其他点都太抽象不太好出题。

6．数据库：4道范式题，涉及到1NF、2NF、3NF、4NF、BCNF
今年数据库出得非常意外，问到了那种范式是无损分解；
对于2NF的分解，进行关系选择，性能是降低？不变？升高？
对于3NF的分解，系统的性能是降低？不变？升高？
大家注意上面两个2NF、3NF是问的方面不一样，一个是对于关系选择的性能，一个是系统的性能。如果我没记错的话。


7、体系结构：（英文题，英文非常简单）
给出一段程序中的4种指令的数量，所需的时钟周期。
求CPI，MIPS，程序的执行时间。
非常简单，了解上面的概念，绝对没问题。
体系结构大家一定要注意复习流水、Cache的效率、CPI、MIPS等带有计算性的知识点。一般不会考什么具体原理性东西，都是考计算，其他基本课也都是这样的。


8、图形学
考的B曲线! 我没复习到，图形学确实是个难复习的东西。大家有时间就复习，没时间就复习一下坐标变换那一块经常考的点吧。今年的B曲线确实令人意外。


9、操作系统：
操作系统包括多种锁的机制，如自旋锁、信号量、条件变量。请说明这些锁的原理和适用的环境。
操作系统这门课，复旦的教材与我们用的初试经典教材不一样，好像是国外的。自旋锁我是没听过，没答出来。大家复习比强求复旦的教材，一般不会有人去全看复旦的教材的，太多了，太杂了，没时间，个人觉得也实在没那个必要。


10、算法
两个数组，一个长度n，一个n+1。元素已经按升序排列。请设计算法，写出伪代码找出两个数组的综合中位数。比如：{1,3,5,6}，{2,4,7,8,9}。中位数为5。它的左边有4个数，右边有4个数。设计的算法时间复杂度要求为log2N。并要求根据自己的算法，分析时间复杂度。
这好像是那年的初试真题。当时确实时不太记得了，只记得思想，把算法思想写了上去。
算法确实不好复习，我考试之前什么都没看，本来就打算直接放弃的。结果还能写的点东西，感觉不错。

11、数据结构：
给出一段代码，让你对代码中间的两空进行补充，并写出代码的时间复杂度和代码实现的功能。
涉及到2维数组。有个TSM的东西，不懂。
大家一般都能写出3空，但是代码实现的功能就确实有点不清楚了，没看懂，但还是能填出来，因为挖的那两空非常简单，几乎是一看就知道的。

12、编译原理
S-->a(a|b)*
请画出上面的确定DFA。
这个非常简单，相信大家都能做出来。
但是题目只要求确定化。我当时画出NFA，在确定化后，就没最小化了。不知道有没有扣分。大家保险点的话，还是最小化吧。




最后说说12门的复习思路。
初试4门在复试中算5门，组成原理细分为了原理和体系结构。这个5门还有概率论，大家初试中基本上复习的差不多了。但是复试时不可放松，其他六门个把月不可能复习的特别好，但是这六门，是大家的强项，一定要用一定的时间进行重新攻克。
看看往年的题，抓住重点，但是其他点也不能过于疏忽。

算法：我直接放弃了，没时间。所以大家只能自己想办法。

编译：正则表达式，DFA、NFA、最小化、确定化、LL(1)、LR(0)、SLR(1)、LR(1)。这是必须要看的。后面的语法制导有时间就看吧。

离散：大家可以弄本复旦的教材，因为有些知识点一般的离散书上还没有。12门的教材论坛上都有，自己查。比如有年考到环的理想，这个我还只在复旦的教材上看见有这个概念。
复习重点：树、图、群、环。群是重中之重！函数什么的就没必要看了，复习了前面写的四个点就差不多了。

图形学：我只看了坐标变换，实在没时间，也看不太懂。大家看着办吧，像今年的曲线那一章的内容我觉得大家也没必要复习，太多，太复杂。还不如留下时间看别的。

数据库：关系代数、关系演算、SQL、范式。这几个点一定要认真重点复习。

软工：没事翻翻书，过个一两遍应该就差不多了。重点：内聚、耦合、测试。其他的我个人以为有个大概的印象就成，每年考的都是选择题，也不深。

总而言之，大家要注意，复旦的笔试注重的是计算和原理。不考死记硬背的东西。不要把时间花在记忆性的东西上。比如体系结构，一般不会考各部分关系、数据通路这类带有记忆性的东西。非常喜欢考能用来计算的点，如CPI，MIPS，Cache效率，流水线的加速比之类的东西。