2011年全国硕士研究生入学考试.doc

2011 年全国硕士研究生入学考试计算机基础综合考试大纲(word版)（五) 散列(Hash)表及其查找 【10 年为“散列（Hash）表”】2. 微程序控制器微程序、微指令和微命令；微命令格式；微指令的编码方式；微地址的形式方式。【“微命令格式”为11 年新增加】（一）通信基础1. 信道、信源与信宿、信号、宽带、码元、波特、速率等基本概念【10 年“信源与信宿”单独作为1 点列出来的】（四）流量控制与可靠传输机制2. 停止-等待协议【10 年为“单帧滑动窗口与停止-等待协议”】3. 后退N 帧协议(GBN)【10 年为“多帧滑动窗口与后退 N 帧协议（GBN）”】4. 选择重传协议(SR)【10 年为“多帧滑动窗口与选择重传协议（SR）”】2. IP 组播地址【10 年还有“3. 组播路由算法”】这是根据之前网上的各个版本以及网友及本人的回忆版汇总的，材料有点乱，但还算全，希望大家多点耐心，慢慢练习。推荐习题是清华大学06-10年的所有题目，以及浙大06-10年的所有题目，初试后大家完全有足够的时间练习，希望大家根据自己的情况制定练习计划。建议初试完后就开始练习上机，大概有不到三个月的练习时间。个人建议基础较好的同学的练习方案：（1）数据结构的基本实现，实现教材上二叉树，图的各种算法，如三种树的遍历，以及DFS,BFS,Dijkstra,Prim,Floyd等算法（2）练习浙大上机题，浙大题注重数据结构基础。同时可以上HDOJ练习一些基础数据结构题。（3）熟悉常用的DP模型，贪心算法，回溯，搜索算法，以及大数运算等高精度运算问题。如01背包问题，最大子段和，最大不增子序列等（4）练习清华历年题目，清华题目注重算法和技巧。（5）最后练习交大历年题目，找感觉基础较差或动手能力较弱的同学应该先补好数据结构，保证相关结构和算法能随手写出，然后以交大历年题目为基础练习，然后上OJ练习一些基础题（过一段时间我会总结出相关的推荐练习题）今年的时间安排特别紧迫，上午八点半到十一点机试，实际上九点才开始，前半个小时是试机用的，两个半小时解决4道题，是比较紧张的。第一题，后缀数组，唯一一道菜鸟题输入grain对其子串grainrainaininn分别编号为0，1，2，3，4然后对各子串按字典顺序排序，即：ain,grain,in,n,rain输出2，0，3，4，1大概的思路就是定义一个结构体,包括两个成员，一个是编号，一个是指向该子串位置的指针，然后按字符串比较进行快速排序，输出便可以了。第二题 最短路径第一行输入N,MN表示城市的个数，各城市编号为0到N-1，N的范围我记不清了，不过主要的难题不在这M表示道路的条数，道路也是0到M-1编号，第K条道路的长度为2K ，问题主要在于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的新闻吧，一般的就随便听听六级算了，哈哈，难怪前几届的都说听力是浮云交大面试加上机第一帖 请求加精！回来了面试加上机一天搞完 面试没有什么太大感觉 就是发现今年复试的女生只有不到5个，估计去了面试的哥们都会觉得，虽然数量不够多，但是质量还不错！上机有二道简单题一道超级繁杂题一题非常诡异的题（简直是在考一个英文单词） 一个25分总分1001点半开始试机 二点整开始到5点、面试部分：先一大群人到了电院群楼3号房200房是一个多媒体教室，然后余勇老师向大家介绍了一下各种事项，基本上也就是招生简章和复试安排里面的原话。面试分组随即马上被贴到200门口。一共分6组 1到6名分别被排到第一组 第二组。第六组的第一个。我是第一组第6个，也就是31名。然后不同的组不同的教室。我们这组有4个老师，大概15分钟一个人。我的内容是 进去以后看了看材料闲聊了几句，然后开始问英语问题1.talk aout your family烂熟&（被他们喊停。2.接着老师跟着我的问题问 do you parents have operations?(因为我说了我父母是医生）结果没听懂这句是什么意思，问英文的老师不耐烦了，就是你父母做不做手术的意思，寒。然后又问我父亲是哪一种医生？。寒 只能说（can not say it in english) 。结果老师竟然让我用中文说，我说是麻醉师。英文以失败为告终。3.问了问我家乡是哪的，jiangxi provice.PS：其他哥们有的用英语描述B树，有的要自我介绍，有的要说一下编程语言的特点，这个无法准备，看运气，看底子，其实还是自我介绍的哥们占便宜，个人建议这方面花的时间就是自我介绍别的也不用多看了。然后开始中文，问得很咋，问了问我的项目经历，具体描述一个，问了问一些软件工程的基础知识，我说我没学过这门课，瞎掰了一些，还让我说了下喜欢哪门语言，（浙大攻略里有，烂熟）。最后竟然让我写了一个概率里面方差的公式，我转身看黑板，上面公式若干，。最后让我出去了。总的来说交大老师非常随和，平易近人。思政：二个老师，很随意的聊天，聊到一半，说 ，你竟然上那些论坛发表抵制日货，地址家乐福的帖子么（心里一紧，到关键的了），一个字，装！于是说：老师事物都有二面性，我看事情比较理智。（不要拍我）别的也就是闲聊。上机：今年是4题。1.求二个日期间的天数相差，如果二天是连续的，我们认为有二天。如果数据不符合要求，输出0；格式是YYYYDDMMINPUT：20090411200904112009.。(忘记）2008.。2009 2 292008 2 29OUT1.0这题说白了就是把去年第4题给翻新一下，基本思想都不变，注意数据的合法性判断，（超多，我写了一个很长的JUDGE函数），这题做起来要点时间，我花了30+分钟。二：怨念啊怨念，。intergral竟然是积分的意思，英文超长，如果有机会看到PDF大家就能领略了，给了你一个矩阵，让你求矩阵的积分，。这题超级无语，做了一个半小时，最后实在忍不住问监考学长，学长充满爱怜的问：你是不是不知道什么意思，然后放低声音（就是积分啊）。周围的同学也一片哗然，估计也没看懂。，立马明白怎么做 但是此时离时间到还有不到2分钟，也没心情改了，此处为另一次失误，因为我程序的框架已经完全写好，只要加下求给出数据的面积就行了。而且关键是，到时间了不收卷，竟然在分发奖学金申明要我们签字，此时有同学在狂调