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

《2011年全国硕士研究生入学考试》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2011年全国硕士研究生入学考试计算机基础综合考试大纲(word版)（五)散列(Hash)表及其查找【10年为“散列（Hash）表”】2.微程序控制器微程序、微指令和微命令；微命令格式；微指令的编码方式；微地址的形式方式。【“微命令格式”为11年新增加】（一）通信基础1.信道、信源与信宿、信号、宽带、码元、波特、速率等基本概念【10年“信源与信宿”单独作为1点列出来的】（四）流量控制与可靠传输机制2.停止-等待协议【10年为“单帧滑动窗口与停止-等待协议”】3.后退N帧协议(GBN)【10年为“多帧滑

2、动窗口与后退N帧协议（GBN）”】4.选择重传协议(SR)【10年为“多帧滑动窗口与选择重传协议（SR）”】2.IP组播地址【10年还有“3.组播路由算法”】这是根据之前网上的各个版本以及网友及本人的回忆版汇总的，材料有点乱，但还算全，希望大家多点耐心，慢慢练习。推荐习题是清华大学06-10年的所有题目，以及浙大06-10年的所有题目，初试后大家完全有足够的时间练习，希望大家根据自己的情况制定练习计划。建议初试完后就开始练习上机，大概有不到三个月的练习时间。个人建议基础较好的同学的练习方案：（1）数据

3、结构的基本实现，实现教材上二叉树，图的各种算法，如三种树的遍历，以及DFS,BFS,Dijkstra,Prim,Floyd等算法（2）练习浙大上机题，浙大题注重数据结构基础。同时可以上HDOJ练习一些基础数据结构题。（3）熟悉常用的DP模型，贪心算法，回溯，搜索算法，以及大数运算等高精度运算问题。如01背包问题，最大子段和，最大不增子序列等（4）练习清华历年题目，清华题目注重算法和技巧。（5）最后练习交大历年题目，找感觉基础较差或动手能力较弱的同学应该先补好数据结构，保证相关结构和算法能随手写出，然后

4、以交大历年题目为基础练习，然后上OJ练习一些基础题（过一段时间我会总结出相关的推荐练习题）今年的时间安排特别紧迫，上午八点半到十一点机试，实际上九点才开始，前半个小时是试机用的，两个半小时解决4道题，是比较紧张的。第一题，后缀数组，唯一一道菜鸟题输入grain对其子串grainrainaininn分别编号为0，1，2，3，4然后对各子串按字典顺序排序，即：ain,grain,in,n,rain输出2，0，3，4，1大概的思路就是定义一个结构体,包括两个成员，一个是编号，一个是指向该子串位置的指针，然后

5、按字符串比较进行快速排序，输出便可以了。第二题最短路径第一行输入N,MN表示城市的个数，各城市编号为0到N-1，N的范围我记不清了，不过主要的难题不在这M表示道路的条数，道路也是0到M-1编号，第K条道路的长度为2^K，问题主要在于K可以非常大，比如495接下来M行输入M条道路中每条连结的两个城市编号输出编号为0的城市与其它各城市的最短距离大小，数值太大的以MOD100000的结果输出这个问题可以直接Dijkstra算法，我只做出了int64表达范围的结果，超出的要么用大数运算，要么用某些数论的知识。

6、曾经学过有2的高次幂MOD运算，不过不记得了。第三题中缀表达式运算这题其实非常常见，而且没有括号，只有+—*/四种运算，不过也只解决了60%的数据第四题最小面积子矩阵定义矩阵中元素个数为矩阵面积输入NMK然后就输入N行M列的数，在这个矩阵中所有元素和不小于K的最小的子矩阵。这题一看就知道用DP,可惜一直没想出DP的转移方程，就用穷举了，但数据规模太大，穷举也只能过其中部分数据，大约30%吧机试先说这么多，面试被老师问得很崩溃，书都白读了，看来我RP很有有问题，老师问了五六个专业课问题：1.离散数学里面

7、的归结证明你能说说吗？2.什么是流密码？2.密码学中的RSA公钥加密和RSA签名的关系？（我本科信息安全，那老师恰好是研究安全的）3.数据库中的查询操作是用什么数据结构实现的？用什么搜索算法？4.你毕业设计做的是视频隐写分析，你知道什么是概率密码函数吗？视频帧之间的帧间差异你是怎么处理的？5.英文题：描述一下今天上午上机的情况，你解决了多少个问题，你是如何设计这些算法的？我是第一组第二个，比较郁闷，我们组是比较郁闷的，基本上每个人出来都叹气，我前面唯一一个400+的也被问得直叹气，呵呵。其它有些组很轻

8、松，有位帅哥被问喜欢看哪个古典名著，看过红楼梦没有喜欢什么样的音乐。。。。。。RP那叫一个好啊。期待RP爆发，千万别死在面试上.今天加上听力有关的：听力真的很抽象，哈哈，除非是英语六级580+以上，或者是能听懂VOA标准语速，CNN新闻的那种呀，否则大家都差不多，哈哈竟然还说明：本录音特意加入了干扰因素，哈哈，变态。关于怎么准备，水平高的就听听VOA标准节目以及CNN的新闻吧，一般的就随便听听六级算了，哈哈，难怪前几届的都说听力是浮云交大面试加上机第一帖