复旦计算机复试题汇总.doc

某年1.根据给出的文法写描述相应的语言，判断是否为二义 S-aSbs|bSaS|；是二义，例：abab2.计算条件概率(全概率公式,做火车飞机轮船。分别，迟到概率，已知迟到了，求坐火车来的概率）3.计算一定数量的指令通过给出的一条流水线的时间，计算吞吐量和最大吞吐量（已知流水线4ns一段，共5段，先16条指令通过，完毕后再26条通过）4.用差分法推导一个多项式的递归计算方法，说明这种算法的优点 f(t)=(at3+bt2+ct+d) ti=i/n(i=1,2,3,.n)5.一个1024*16K的存储器，用DDR和EPROM两种芯片构成，前者占四分之三，两种芯片的大小各为128*8位，128*16位，计算两种芯片各要多少片，EPROM的首地址是多少？6.考欧拉图给一张图，最少添几条线成为欧拉图。有几种画法？(找奇数顶点）7.证明一个代数系统是群，判断正规子群G=(x,y)|x不为0, x,y都属于R,定义运算(x,y)(z,w)=(xz,xw+y)证明G;是群。H=(1,y)|y属于R,是不是G的正规子群？8，9.软件测试有关的问题，软件结构设计的问题 （选择）10.文件系统中冗余的概念和关系数据库中冗余的概念 （具体是问：文件系统中不可消除的数据冗余；关系数据库中应该避免的数据冗余）11.分布式数据库中的三层透明性是什么（写出名词即可）12.两个NP语言L1,L2的并和差是否属于NP，证明或举反例 是不是13.移动窗口协议端对端延迟1.25s,已知带宽*Mbps,每个帧的容量1KB,若要充分利用，应该为帧安排几位的序号字段？14.描述一个X86系统中的中断处理过程，主要是根据中断向量N和中断向量表来查中断处理子程序的入口USEINT.（写出过程，实模式or保护模式任选）2005年复试1. G=(a,b)|a0 H=(1,x) 在G中定义运算(x,y)*(w,z)=(xw,xz+y) 求证H为G的正规子群2. 原理：一个32位浮点数分S, M, E三段，其值为(-1)S * 1.M* 2(E-128) ;问最大、小正负数分别是多少，且给出二进制表示。【小心点应不会错，E是移码表示，-128127,等等】3填空题 考概率，涉及到条件独立，正态分布，方差，样本 (1).p(A)=0.5,p(B)=0.25,A与B独立，求P(A-B),P(A并B) (2).X,Y符合N(0,1)N(1,1),求pX+Y2-3-4-5,1-4,3-5),问计算 a1*b1+a2*b2+a3*b3+a4*b4的最佳计算次序,所用时间及加速比.6. 执行DMA时,CPU和总线之间的关系?如有外部中断,系统是否立即响应?7. S-AaAb|BbBa A-空 B-空 证明为LL(1)文法8 数据库函数依赖以及划分后是否保持函数依赖 F=A-B,B-C,C-D,D-A 则AB，BC，CD是否保持依赖9. 设计一种新媒体,每网段最大延迟20uS,两个端系统之间允许最多6个转发器,(repeator),媒体10Mbps,问最小帧长.10. 求从一个顶点到另一个顶点的最短路径的算法叫什么?为什么不是NP难的?什么叫NP难?求一点到另一点的最长路径是NP难的,试给出证明思路.11. 图形学关于坐标变换的填空.2006年复试1.离散:T是无向图G=的一棵生成树,T中恰好有两片树叶u和v,若边(u,v)在E中,证明:对V任意非空的子集V,w(G-V)=|V|。一道图论题目,已知G(V,E)，其中v，u是生成树的两个叶子，且u,v属于V(G), 且(u,v)属于E,求证对于任意S属于G，w(G-S)n=1写一个LR(1)文法。9.考CRC，第一题求CRC后缀，第二题判断某带CRC后缀的串是否有错。10.图形学的题，已知:1一点(a,b,c)和一向量(l,m,n)确定一条直线; 2 P(a1,b1,c1)。问如何得到P点绕已知直线旋转角度后的点P的坐标。11.英文算法题，要求用英文回答。1问NP类的定义；2问NP完全语言的定义；3问证明一个语言是NP完全语言的步骤。2008年复试1.离散。这个题目是个老题目了，考了很多年了。已知G= | x, y 是实数，x != 0 ，且(x, y)*(z, w)= (xz, xw+y) 。求证：1。该G是个群 2。证明H=| y实数是其正规子群。证法很简单。首先证明G是个半群因为G是个代数系统 而且元素abc=a（bc），所以G是个半群再找幺元e=(1,0),再求一个（x，y）的逆 证明逆肯定存在得出G是个群证明正规子群的时候更简单，找个a和a的逆然后证明aha-1一定属于H 就得出结论了。这个题目在离散里很典型，希望后来者高度注意。2.原理。这个题目主要就是考你一个加速比的概念，知道加速比到底是怎么回事，这题就等于送分题。知道3部分的占的总时间的比例分别是：a 0.2 b 0.3c0.5 问是a的加速比到5倍好 还是c的加速比到2倍好。事实上先设定一个大T总的时间则a加速的话0.2/5+0.3+0.5=0.84T 另一个0.2+0.3+0.5/2=0.75T 显然后面一个好。3.概率。概率分两题 第一个是送分题 就是求一下条件概率，太简单了在这里不解释了。第二个是3个填空题前两个有难度，一个是求复合函数的概率一个是求联合概率密度，想搞定这两个题目概率基础要扎实才行，第三个送分题。整个概率就是这样，每年都有人把概率当成必拿分的题，事实上还是有差别的，出到了难题你照样玩完。4.软工。今年的软工出的依然是选择题。是模块之间的耦合度的问答题。问模块间的耦合是高好还是弱好。（显然弱了好）问一个模块可以直接访问另一个模块的内部数据是什么耦合（注意是内部数据，显然是内容耦合，是最高度的耦合），问模块间通过公共数据结构耦合是个什么耦合（显然是公共耦合），问模块间通过一个信号的控制进行耦合是个什么耦合（个人不确定，回家后在书上没找到这种描述的耦合，不过个人觉得是控制耦合）。最后问你那个耦合度最高，这显然是内容耦合。个人觉得，送分。5.体系结构。今年的体系结构出的是cache上的东西，一个是直接访问cache的总的平均时间的求法，一个是串联访问（就是说每次访问完主存还要访问一次cache，个人认为，不然出这个题目实在没什么意思）。还有就是30%的几率访问数据，这个题目是用求CPI的方法求平均时间，懂的人见题目就会做了，不懂的话告诉你怎么做你还是不懂。6.数据库。今年的数据库的sql语句超级简单，这里就不多说了。不过最后一问还是有点意思的，问用什么样的方法建立一个索引最好。个人认为不能用B+树（我卷子上写的就是B+）因为主码不需要排序，需要排序的是另外的非主码。至于用哪种方法，我就不知道了，看高手的吧。7.编译。据说是语义制导翻译模式还是什么鸡毛玩意的。老衲没学过，也不懂。看书复习的时候编译和图形学一块放弃的。8.网络。超级简单的网络题，就是考个香农公式，但是一定要记得分贝这个单位要化一下才行，具体的大家看看书都知道了。9.图形学。不懂就是不懂，据懂的人说超级简单，可是我就是不懂，就好像我懂网络说香农公式超级简单一样，别的没看到的还是不懂。10.算法。动态规划上的东西，老夫依然不懂。随便你怎么说去吧，反正是英文出题。注意，可以不用英文作答。这里要提醒一下师弟师妹，P问题，NP问题，NPC（NP完全）问题，NP难问题出了好多年了，你怎么看是你的事情，但是这几个的概念一定要掌握。好了。总共就10个题目，我在这里就说这么多，我估计做下来应该在50分左右。如果大家都是这个分数的话那初试不算低的话就估计没问题了。但是要提醒一下DDMM，今年的复试有个组很变态。大家被分到三个组里去了，按照成绩蛇形排列。（所谓蛇形排列的意思就是每个组都有高分低分）第一组的同志们最郁闷，专业面试的时候5个老师一个老师一道题，全都是跟复试内容相关的问题譬如 NP问题，譬如hub和路由器的区别（不在同一个层？）这个需要大家平时掌握的知识而不是大家的口才了。另外两个组是拼口才的，看你了。还有就是大家一定要注意的是英语面试会问到毕业设计（历届生），你想想怎么用英语表达吧，如果你做的很有意思而老师很感兴趣，那恭喜你，你更需要表达好了，表达不好老师会让你用汉语说，告诉他到底做的是个啥。（一个哥们做的教学设计的，最后用汉语说的。不过并不能说明这个是哥们的错，毕业设计不过就是抄一抄，谁还真认真了。结果让你用英语表达一下，而且老师还非常感兴趣，那你表达不好也正常）这也可以看出来，有些组的英语面试更像是专业面试，内容都是相关的。老师感兴趣的不是你英语口语有好，而是更多的是专业方面的问题。另外有一个组一个哥们的英语面试就是纯粹是考察口试了，就是考表达，譬如问你人生的成功的要素啊，我一个哥们被要求当场用英文唱个歌，如果那天是4月1号，如果你唱的是生日歌。不敢想结果了。因为我第一个反应就是应该唱个好唱的，生日歌，总之，面试很怪异今年，牛人什么时候都不怕。普通平民还是以专业知识为出发点吧，下面给出8门课的复习思路。1.离散。离散我的复习思路是代数系统，正规子群的证明，图论，欧拉和哈密顿图，范式，推导。这都是大概的章节名称，要求掌握的，结果考了正规子群，命中。2.原理。寻址，数的计算，补码，反码，移码，原码，还有就是浮点数的乘法。在这些课的复习中肯定会有加速比的概念，看一遍就非常明白了。我没学过原理，就复习了这些，这是在赌博，结果算是命中了。3.概率。不解释，考研怎么复习这个就怎么复习。4.软工。大方向着手，譬如瀑布模型，重点在测试，白盒，黑盒，还有耦合和内聚，今年考耦合，明年考内聚。Yes！命中。5.体系结构。我只看了cpi的计算方法，还有mips的计算方法，流水线的东西，以及流水线的三个相关。别的东西都是操作系统上的，考好了初试这个就没问题。命中一半。不算命中。6.数据库。Sql语言，关系演算，模式内模式外模式，2个映像，2个独立性，还有就是无损连接，这个最好百度一下，网上有关于怎么证明是无损连接的。命中一半。7.网络。香农奈奎斯特公式，还有就是数通方面的计算利用率的，不只是停等，滑动窗口的利用率也要会算，7层协议，TCP IP了解，掌握IP地址的概念，还有就是局域网的组建，这个都是本科学过的东西，很多专业都学过，相信大家都不会陌生，总之，命中。8.算法。NP方面的各种问题。我就看这么多。动态规划一点没看，因此未命中。总结下来大概就50分命中的，对于我这个10门科有7门没有学过的人来说，相当相当牛逼了。（本人外校外专业，8天复习8门）我很满意，不管录取与否，我都觉得很满意了，大家想在复试的时候取得好成绩，这个情况必须搞清楚。最好是有复旦本科的课件和本科的时候学过的教材，帮助千万倍。最好就是找一个跟自己分数差不多的人一起复习复试。请注意。考复旦计算机复试和初试同样重要，不重视的人，肯定要遭殃。今年复试的情况是69个刷10个，上帝保佑我，被录取吧。写了这么多这么多，谢谢大家耐心读完。(之所以发在这里，就是考虑到很多人是拿着朋友的账号在登录在了解复旦计算机的情况，很多来这里看帖子的人不是复旦的可能也很大，因此希望复旦本校的朋友不要介意，小弟并没有任何侵权的意思，只是为了方便更多的人加入到考复旦计算机的行列上来，当然我想有些内容对本校的朋友也是略微有一点点用的。)2010复旦考研复试题1.离散数学证明XXXX是环的理想2.计算机原理定义了2个类型A，B，用Union联合起来，对A.XX1,A.XX2等进行赋值，求B类型中的各个值。用小端法表示。3.概率论求几何分布的期望和方差4.软件工程软工之需求分析（几个选择题）5.计算机体系结构加速比程序包含哪几部分，分别加速比是多少，每一问是求总的加速比，第二问是求加速后，每部分在总体中占的比值。6.数据库关系代数表达式表示查询dorm(dormNo,building,floor,area)student(name,sex,dormNo,directorID)director(directorName,directorID)1）求男女都有的宿舍2）求没人住的宿舍3）所管学生数最多的导员7.编绎原理LL(1)E-ET+|TT-TF*|FF-i消除左递归，每个未终结符的First和Follow集，证明新文法是LL(1)文法（此题是老题，以前考过）8.计算机网络慢启动和拥塞控制慢启动是32个分组。阀值分别是16，8，8.最后一个第四个分组丢失，求发送共需要多少RTT。9.图形学画家算法。10.算法一个串T长为n,Ti属于a,b,c,d,e,f,，z(i=0到n-1)，还有模式串P，P长m，pi属于a,b,c,d,e,f,，z(i=0到m-1)T中从第K位开始，长度为m的字符子串的某种排列与p相等称为逆匹配。1）写出一个可行的验证T中从第K位开始与p逆匹配的算法，并给出时间复杂度2）写出一个在O(m+n)时间复杂度内的一个算法，找出T中所有与p逆匹配的字符子串。11.数据结构对于任意正整数n证明叶子数为n的完全二叉树存在，然后要给出完全二叉树的高度和n的关系（根结点为第一层）12.操作系统cache,RAM,磁盘三者的关系访问一次cache,ram和磁盘分别需要10ns,20ns,和12mscpu读取一次数据，有10%概率在cache中寻找不到，有40%概率在ram中寻找不到求cpu读取一次数据时的平均时间。2011年复旦计算机复试题目（12门）1. 计算机组成原理浮点数用六位表示：一位符码，三位阶码，两位尾数。阶码偏移量为3。浮点数的真值是：(-1)S*M*2E给出了几个数的二进制机器码要求写出其阶码，尾数，真值.（真值要求用分数形式表示）比如：010000 阶码编码 阶码E 尾数编码 尾数M 真值4 1 0 4/4 2 (分析：编码是指二进制实际数值，如：阶码编码为4，由于偏移量为3，所以阶码E=4-3=1;尾数不知道为什么是4/4.)2. 离散数学G是mn阶的交换群，单位元e，（m,n）=1，Gm=gG|g的阶数是m的因子 ，Gn=hG|h的阶数是n的因子 ，求证：Gm、Gn是G的子群，且GmGn=e。（分析：“g的阶数是m的因子”等价于gm=e.，证明Gm、Gn是G的子群，即证明运算封闭。GmGn=e，用反证法。提示：e就是幺元，（m,n）=1指的是m,n互质。）3. 概率与统计设随机变量X的概率密度函数是：当0x1时，f(x)=(+1)x；否则f(x)=0；其中 X1,X2.XN为给分布的n个独立随即变量。求的矩估计量和最大似然估计量。4. 软件工程选择题5个，考的很大概，不深，对不起，具体东西记不清了。 5计算机体系结构。一个指令系统，分支指令的判断错误的延迟时间是4个时钟周期，缓冲不命中的延迟时间是3个时钟周期。根据以下条件求分支指令的平均延迟时间，以及全