王道论坛
王道论坛计算机考研机试指南
王道论坛
写在前面的话
各位王道的小崽子们，今天你们考完初试了，感觉解放了吧轻松了吧无
论结果如何，总算坚持到了最后。但是，其实你的考研生活只刚刚走出了第一步，接下来会有初试成绩出来前的煎熬、分数线出来的煎熬、准备复试以及复试的煎熬以及录取结果出来前的煎熬，这些都远远比初试更折磨人，未来的两个月你会感觉到王道没有吓唬你们。
王道是个好姑娘，四年多的时光里陪伴了接近二十万计算机考研人，不离
不弃。今年不小心又压中一道算法题，说实话，王道的书里有那么多的题，知识点又只有那么多，总能瞎猫碰见死耗子吧王道尊重的不是考研这个行业，而是
你们这群执着的小崽子们的梦想！看着你们圆梦，我们内心充满了成就感。
初试考完了，是不是应该好好放松放松是不是初试考得好，录取就肯定没
有问题了对不起，这个不是计算机专业研究生考试的规则。目前已经有越来越
多的高校采用上机考试的形式来考察考生的实际动手编程能力，并且机试在复试中所占的比例非常高，并且很多高校规定复试成绩不及格者，一律不得录取。目前国内高校开展ACM 教学的高校非常少，而ACM 是目前所有高校机试所采取的唯一形式，因此提早开始准备和练习，对于一个完全没有接触过ACM 的计算机考研人来说，是必须的！
为了方便各位道友练习机试，我们编写了本书，搭建了九度Online Judge （），并收集了全国各大高校的复试上机真题，希望能给大家
复试上机考试提供强有力的支持。你可以直接使用王道论坛的帐号进行登录。如果您在使用过程中遇到问题，欢迎你到复试机试讨论专区发贴提出。目前已经收录了我们能够收集到的各高校上机复试真题，欢迎大家继续向我们提供各高校上机真题，具体请站内信或者电子邮件联系浩帆（）。此外，
华科的上机题我们经过了变型，将其中一些便于修改成OJ判题的题目收录进了
我们的OJ。
考研其实没有什么诀窍，就是每天比别人早起一点，晚睡一点，比别人早准备一点，勤奋一点。考研离我已经很远了，同时我也坚信一个写不出合格代码的计算机专业的学生，即使考上了研究生，无非也只是给未来失业判个缓期执行而已。
小崽子们，要忠实于自己心底的梦想，勇敢地坚持下去，而当下，请开始
准备复试吧，熬过这两个月，一切就都好了。
第1章从零开始
一机试的意义
众所周知，机试是计算机考研当中非常重要的一个环节。在越来越注重实践动手能力的今天，越来越多的知名高校在计算机研究生招生考试当中采用了机试的形式，通过这种考试手段来考察考生分析问题并利用计算机程序解决问题的能力。通过机试，可以考察一个考生从实际问题当中抽象得出数学模型的能力，利用所学的计算机专业知识对该模型进行分析求解的能力，以及利用计算机编程语言，结合数据结构和算法真正解决该实际问题的能力。
所以，我们在准备机试的过程中要特别注意以下几个方面：
1、如何将一个实际问题抽象成数学问题。例如将高速公路网抽象成带权图，这就是一种简单的、直接的抽象。
2、如何将我们所学的计算机专业知识运用到解决抽象出来的数学模型上去。这就要求我们在脑子里事先熟知一些常用的数据结构和算法，再结合模型求解的要求，很快地选择合适的编程思想来完成算法的设计。甚至可以利用一些经典算法特征，加入一些自己的优化，使得编写的程序更优雅、更高效（当然这是建立在充分理解经典算法的基础上）。
3、如何将我们为解决该数学模型所设计的算法编写成一个能被计算机真正执行的计算机程序。我们认为，关于这个能力的定义有三个层次：1）会编写（默写）一些经典算法的程序代码。2）能够将自己的想法或设计的算法转换为程序代码。3）能够使得自己编写的程序在大量的、多种多样的、极限的测试数据面前依旧正常完成功能（程序的健壮性）。我们在准备机试的训练过程中，就要依次经历这三个层次，从而最后能够在实际考试当中取得理想的成绩。
本教程从分析经典机试真题出发，引入近几年频繁被考察的数据结构和算法，利用C/C++语言讲解例题，并加以一些相关知识的扩展，希望在读者准备计算机考研机试的过程中充当指引者的角色。同时，由于笔者自身实力的限制以及编写时间的不足，教程中难免存在一些疏漏和错误，也欢迎读者提出、指正。
二机试的形式
绝大部分机试所采用的形式，归结起来可以概括为：得到题目后，在计算机上完成作答，由计算机评判并实时告知结果的考试过程。
机试考试中的问题往往有五部分组成。首先是问题描述，问题描述描述该问
题的题面，题面或直接告知考生所要解决的数学问题或给出一个生活中的实际案例，以待考生自己从中抽象出所要解决的数学模型。第二是输入格式，约定计算
机将要给出的输入数据是以怎样的顺序和格式向程序输入的，更重要的是它将给
出输入数据中各个数据的数据范围，我们通过这些给出的数据范围确定数据的规模，为我们设计算法提供重要依据。第三是输出格式，明确考生将要编写的程序
将以怎样的顺序和格式向输出输出题面所要求的答案。第四第五部分即输入、输
出数据举例（Sample）。好的Sample 不仅能为考生提供一组简单的测试用例，同时也能明确题意，为题面描述不清或有歧义的地方做适当的补充。
另外我们也要特别注意，题目中给定的两个重要参数：1、时间限制。2、空
间限制。这两个重要的参数限定了考生提交的程序在输出答案之前所能耗费的时
间和空间。
我们来看一个典型的题目描述，从而了解机试题的问题形式。
例计算A+B （九度OJ 题号：1000）
时间限制：1 秒内存限制：32 兆特殊判题：否
题目描述：
求整数a，b 的和。
输入：
测试案例有多行，每行为a，b 的值，a，b 为int 范围。
输出：
输出多行，对应a+b 的结果。
样例输入：
12
45
69
样例输出：
3
9
15
通过该例，我们基本明确了机试试题的问题形式，以及问题各部分所起到的
作用。这里补充解释一下所谓特殊判题（Special Judge）的含义，特殊判题常被
应用在可能存在多个符合条件的答案的情况下，若评判系统采用了特殊判题，那
么系统只要求输出任何一组解即可；若系统对该题并没有采用特殊判题，那么你
必须严格按照题目中对输出的限定输出对应的答案（如输出字典序最小的解）。
得到题目后，考生在计算机上立即编写程序，确认无误后，将该程序源代码提交给评判系统。评判系统将考生提交的源代码编译后，将后台预先存储的输入测试数据输入考生程序，并将该程序输出的数据与预先存储在评判系统上的“答案”进行比对得出结果。
评判系统评判考生程序后，实时地将评判结果返回考生界面，考生可以根据该结果了解自己的程序是否被评判系统判为正确，从而根据不同的结果继续完成考试。
三评判结果
本节将对评判系统评判考生提交程序后返回的结果做详细的说明，并且针对不同的返回结果，对可能出现错误的地方作出初步的界定。
Accepted（答案正确）：你的程序对所有的测试数据都输出了正确的答案，你已经得到了该题的所有分数，恭喜。
Wrong Answer（答案错误）：评判系统测试到你的程序对若干组（或者全部）测
试数据没有输出正确的结果。
出现该种错误后，一般有两种解决方向：如果对设计的算法正确性有较大的把握，那么你可以重点考虑代码健壮性，即是否存在某些特殊数据使程序出现错误，比如边界数据，比如程序中变量出现溢出。另一种方向，即怀疑算法本身的正确性，那么你就需要重新考虑你的算法设计了。
Presentation Error （格式错误）：评判系统认为你的程序输出“好像”是正确的，
只是没有严格按照题目当中输出所要求的输出格式来输出你的答案，例如你忽略了题目要求在每组输出后再输出一个空行。
出现这种错误，往往预示着你离完全正确已经不远了，出现错误似乎只是因为多输出了一些空格、换行之类的多余字符而已。但这不是绝对的，假如在排版题（后文会有介绍）中出现格式错误，那么有可能你离正确的答案仍然有一定的距离。
Time Limit Exceeded （超出时间限制）：你的程序在输出所有需要输出的答案之前
已经超过了题目中所规定的时间。
若这种结果出现在你的评判结果里，依然有两种方向可供参考：1、假如你确定算法时间复杂度能够符合题目的要求，那么依旧可以检查是否程序可能在某种情况下出现死循环，是否有边界数据可能会让你的代码不按照预想的工作，从而使程序不能正常的结束。2、你设计的算法时间复杂度是否已经高于题目对复杂度的要求，如果是这样，那么你需要重新设计更加高效的算法或者对你现行的算法进行一定的优化。
Runtime Error （运行时错误）：你的程序在计算答案的过程中由于出现了某种致
命的原因异常终止。
你可以考虑以下几个要点来排除该错误：1、程序是否访问了不该访问的内存地址，比如访问数组下标越界。2、程序是否出现了除以整数0，从而使程序异常。3、程序是否调用了评判系统禁止调用的函数。4、程序是否会出现因为递归过深或其他原因造成的栈溢出。
Compile Error （编译错误）: 你提交的程序并没有通过评判系统的编译，可根据更详细的编译信息修改你的程序。
Memory Limit Exceeded （使用内存超出限制）: 你提交的程序在运行输出所有的答案之前所调用的内存已经超过了题目中所限定的内存限制。
造成这种错误的原因主要有两个方面：1、你的程序申请过多的内存来完成所要求的工作，即算法空间复杂度过高。2、因为程序本身的某种错误使得程序不断的申请内存，例如因为某种原因出现了死循环，使得队列中不断的被放入元素。当然也千万别忽略自己的低级错误，比如在声明数组大小时多打了一个0。
Output Limit Exceeded (输出超出限制): 你的程序输出了过多的东西，甚至超出了评判系统为了自我保护而设定的被评判程序输出大小的最高上限。
一般来说该种错误并不常见，一旦出现了也很好找原因。要么就是你在提交时忘记关闭你在调试时输出的调试信息（我经常输出DP 时的数组来动态的观察状态的转移）；要么就是程序的输出部分出现了死循环，使得程序不断地输出而超出系统的限制。
以上几种结果就是评判系统可能会返回的几个最基本的结果。若返回Accepted，则你可以获得该题的所有分数。若返回其它错误，则根据不同的考试规则，你的得分将会有一定的差异。若你参加的考试采用按测试点给分规则，你依然能够获得你通过的测试点（即该程序返回正确结果的那部分测试数据）所对应的分数；但是，若你参加考试采用所有数据通过才能得分的评分规则，那么很可惜，到目前为止你在这道题上的得分依旧是0 分。
假如评判结果显示你提交的程序错误的，你可以在修改程序后再次提交该题，直到获得满意的分数或者放弃作答该题。
四复杂度的估计
本节将详细讨论题目中所给定的时间限定和空间限定对我们程序设计的指
导作用。
如例所示，该题给予我们的程序 1 秒的运行时限，这也是最常见的时间限制（或最常见的时间限制数量级）。对于该时限，通常，我们所设计的算法复
杂度不能超过百万级别，即不能超过一千万。即若算法的时间复杂度是O(n^2)，
则该n（往往在题目中会给出数据范围）不应大于3000，否则将会达到我们所说
的千万数量级复杂度，从而程序运行时间超出题目中给出的用时限定。举例来说，
我们不能在 1 秒时限的题目当中对10000 个整数进行冒泡排序，而必须使用快速
排序等时间复杂度为O(nlogn)的排序算法，否则程序很可能将会得到运行时间超
出限制的评判结果。因此你可以对你的程序在最坏情况下的复杂度进行一个估
算，假如确定其在百万数量级之内，那么你的程序一般是不会超出时间限制的。
对于其它时间限制的情况，可以参考 1 秒时限对时间复杂度的要求，做出一定的
估计，从而保证自己的程序运行所需的时间不会超过题目中对运行时间的限制。
我们同样可以知道，例中限定的内存空间为32 兆，即你的程序在评测
系统中运行时，不得使用超过32 兆大小的内存。空间限定则比较好处理，你可
以简单的计算你所申请的内存空间的大小（例如我们可以轻易的计算int
mat[300][300]所占用的内存大小）。只要该大小没有超过或过分接近空间限定(运
行时需要一些额外的空间消耗)，那么你的程序应当是符合空间限制条件的。现
如今的机试题，一般不会对空间做过多的限制，大多数情况只对时间做出明确的
要求，所以考题在空间上将会尽量满足考生程序的需要。正因为如此，我们在很
多情况下都应该有“空间换时间”的思想。
五OJ的使用
我们该去何处开始我们的机试训练和模拟考试呢可能大部分人已经听说
过在线评判系统（Online Judge ），例如HDOJ
（）,POJ( )。但是这些OJ都是为ACM/ICPC训练而
设计的，虽然形式与机试大同小异但是难度却有较大差别，普通的考生在其中训
练不仅打击了信心，也在一定程度上浪费了时间。因此，推荐专门为我们计算机
考研机试所设计的九度OJ（），它收录了近三百道各大高校近几
年来的机试真题，真正为我们准备机试提供了极大的便利。
我们在它的首页上可以看到九度OJ 所包含的各种功能。
首先，我们需要点击“注册”按钮，为自己注册一个账号，有了该账号你就
能在九度OJ 上进行日常练习，同样也有资格参加九度OJ 举行的各类比赛和模拟考试。
现假设我们已经有了一个账号，并且想要开始在线练习。那么，可以在页面左边的导航栏找到在线练习，我们可以选择题目汇总来查看九度OJ 收录的所有在线练习题，或者点击考研机试题集来查看九度为各位考生收录的近几年各大高校机试真题。例如我们选择题目汇总中的题号为1000 的问题，例中的例子
便出现在页面当中。当用户完成作答以后，可以在页面左侧点击“提交答案”按钮，将源代码提交给九度在线评测系统，提交完成后，系统会自动跳转到评测状态页面，通过查看你刚才提交的源代码的评测状态，你就可以知道你是否通过了该题，从而达到锻炼自我的目的。在本文中，凡是涉及九度OJ 上收录的例题，本书会明确该题的题号。
同样的，九度OJ 也经常为广大考生提供在线模拟考试训练。我们可以点击“比赛及考试”按钮，来查看过往的比赛以及近期的比赛安排，从而有选择的参
加在线比赛，考察自己的训练质量，为日后进一步训练做出导向
总结
本节主要介绍机试的意义、形式，以及机试题的形式和考察的方法，并在最
后给出了我们可以完成机试训练的网站——九度Online Judge。
第2章经典入门
本章通过对频繁出现在考研机试真题中的一些经典问题进行讲解，并对解题方法做详细的说明，旨在使读者快速的了解机试的考察形式和答题方法，以便进
一步的学习。
一排序
排序考点在历年机试考点中分布广泛。排序既是我们必须要掌握的基本算法，同时也是学习其他大部分算法的前提和保证。
首先我们来学习对基本类型的排序。所谓对基本类型排序，即我们对诸如整
数、浮点数等计算机编程语言内置的基本类型进行排序的过程。
例排序（九度教程第 1 题）
时间限制：1 秒内存限制：32 兆特殊判题：否
题目描述：
对输入的n 个数进行排序并输出。
输入：
输入的第一行包括一个整数n(1<=n<=100)。接下来的一行包括n 个整数。输出：
可能有多组测试数据，对于每组数据，将排序后的n 个整数输出，每个数后
面都有一个空格。每组测试数据的结果占一行。
样例输入：
4
1432
样例输出：
1234
来源：
2006 年华中科技大学计算机保研机试真题
这便是一例曾经出现在机试中关于排序考点的真题。面对这样的考题，读者可能很快就会联想到《数据结构》教科书上各种形形色色、特点不同的排序算法。例如，我们可以自然的想到选择冒泡排序来完成此题。但是在确定使用冒泡排序之前，我们不应忽略对其复杂度的考量，我们应特别注意在选择将要采用的算法
时估计其复杂度。以此处为例，假如我们采用冒泡排序来完成此题，我们应该注意到冒泡排序的时间复杂度为O(待排序个数的平方)，在此例中即O(n^2)。而n
的取值范围也在题面中明确地给出(1<=n<=100)，这样我们可以估算出n^2 的数量级仅在万级别，其时间复杂度并没有超过我们在前一章中所讲的百万数量级复杂度，所以使用冒泡排序在该例限定的一秒运行时间里是完全可以接受的；同时冒泡排序的空间复杂度为O(n)，即大致需要100 * 32bit（数组长度* int 所占内存）的内存，这样，所需的内存也不会超过该例限定的内存大小（32 兆）。只有经过这样的复杂度分析，我们才能真正确定冒泡排序符合我们的要求。于是，我
们可以开始着手编写该例的解题代码。
代码
#include <>
int main () {
int n;
int buf[100];ame,&buf[i].age,&buf[i].score);
}ame,buf[i].age,buf[i].score);
}ame,&buf[i].age,&buf[i].score);
}
sort(buf,buf + n);
for (int i = 0;i < n;i ++) {
printf ("%s %d %d\n",buf[i].name,buf[i].age,buf[i].score);
}
}
return 0;
}
由于已经指明了结构体的小于运算符，计算机便知道了该结构体的定序规则（sort 函数只利用小于运算符来定序，小者在前）。于是，我们在调用sort 时，便不必特别指明排序规则（即不使用第三个参数），只需说明排序起始位置和结
束位置即可。虽然，该方法与定义cmp 函数的方法类似，我个人还是建议使用
第二种方法。这样，首先可以对重载算符的写法有一定的了解；其次，在今后使
用标准模板库时，该写法也有一定的用处。后文中，将会广泛使用该方法编写例程。若读者坚持使用定义cmp 函数的写法，只需自行将重载小于运算符中的语
句转化为定义cmp 函数函数体的相关语句即可，并在调用sort 函数时加上第三
个参数cmp。
相信通过本节的学习与练习，读者不会再对排序问题感到恐惧。有了sort
函数，你所需要做的只是按照题面要求为其定义不同的排序规则即可。
练习题：特殊排序（九度教程第 3 题）；EXCEL 排序（九度教程第 4 题）；字符串内排序（九度教程第 5 题）；
二日期类问题
关于日期运算的各种问题，同样被频繁选入机试考题当中。但是这类问题都
有规律可循。只要把握住这类问题的核心，解决这类问题就不会再有太大的难度。
例日期差值（九度教程第 6 题）
时间限制：1 秒内存限制：32 兆特殊判题：否
题目描述：
有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们
之间的天数为两天
输入：
有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD
输出：
每组数据输出一行，即日期差值
样例输入：
样例输出：
11
来源：
2009 年上海交通大学计算机研究生机试真题
该例题考察了日期类问题中最基本的问题——求两个日期间的天数差，即求分别以两个特定日期为界的日期区间的长度。这里值得一提的是，解决这类区间问题有一个统一的思想——把原区间问题统一到起点确定的区间问题上去。在该例中，我们不妨把问题统一到特定日期与一个原点时间（如0000 年 1 月 1 日）的天数差，当要求两个特定的日期之间的天数差时，我们只要将它们与原点日期的天数差相减，便能得到这两个特定日期之间的天数差（必要时加绝对值）。这样做有一个巨大的好处——预处理。我们可以在程序真正开始处理输入数据之前，预处理出所有日期与原点日期之间的天数差并保存起来。当数据真正开始输入时，我们只需要用O（1）的时间复杂度将保存的数据读出，稍加处理便能得
到答案。值得一提的是，预处理也是空间换时间的重要手段（保存预处理所得数据所需的内存来换取实时处理所需要的时间消耗）。
另外，日期类问题有一个特别需要注意的要点——闰年，每逢闰年 2 月将会有29 天，这对我们计算天数势必会产生重大的影响。这里，我们必须明确闰年的判断规则——当年数不能被100 整除时若其能被 4 整除则为闰年，或者其能被400 整除时也是闰年。用逻辑语言表达出来即为Year % 100 != 0 && Year %
4 == 0 || Year % 400 == 0，当逻辑表达式为true 时，其为闰年；反之则
不是闰年。从中我们也可以看出，闰年并不严格的按照四年一次的规律出现，在某种情况下也可能出现两个相邻闰年相隔八年的情况（如1896 年与1904 年）。所以，这里我们推荐严格按照上述表达式来判断某一年是否是闰年，而不采用某
一个闰年后第四年又是闰年的规则。。
代码
#include <>
#define ISYEAP(x) x % 100 != 0 && x % 4 == 0 || x % 400 == 0 1 : 0
The leap years are years
with number divisible by 4 but not divisible by 100, or divisible by 400.
For example, years 2004, 2180 and 2400 are leap. Years 2004, 2181 and 2300 are not leap.
Your task is to write a program which will compute the day of week corresponding to a given date in the nearest past or in the future using today’s
agreement about dating.
输入：
There is one single line contains the day number d, month name M and year number y(1000≤y≤3000). The month name is the corresponding English name starting from the capital letter.
输出：
Output a single line with the English name of the day of week corresponding to the date, starting from the capital letter. All other letters must be in lower case.
样例输入：
9 October 2001
14 October 2001
样例输出：
Tuesday
Sunday
来源：
2008 年上海交通大学计算机研究生机试真题
该题是一例以英文命题的机试真题。其大意为，输入一个日期，要求输出该日期为星期几。我们照样可以利用上例的思路来解答该题。星期几是以七为周期循环的，那么我们只需要知道：1.今天是星期几；2.今天和所给定的那天相隔几
天。利用其对7求余数，我们便可以轻易的知道所给定的那天是星期几了。
代码
#include <>
#include <>
#define ISYEAP(x) x % 100 != 0 && x % 4 == 0 || x % 400 == 0 1 : 0
int dayOfMonth[13][2] = {
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30,
31,31
};
struct Date {
int Day;
int Month;
int Year;
void nextDay() {
Day ++;
if (Day > dayOfMonth[Month][ ISYEAP(Year) ]) { Day = 1;
Month ++;
if (Month > 12) {
Month = 1;
Year ++;
}
}
}
};
int buf[3001][13][32];
char monthName[13][20] = {
"",
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};行“*”的个数和梯形高度都是h；2.
下一行总是比上一行多两个“*”；3.每行都是右对齐，左边空余的位置用空格代
替。有了这些规律，我就能得知如下程序所需要的关键信息：1.需要h 次循环来
输出每一行。2.第一行包含h 个“*”，第二行包含h + 2 个“*”，依次类推，最
后一行包含h + ( h - 1 ) * 2 个“*”；3.在每行输出“*”之前，都需要输出空格来
使输出的“*”右对齐，每行输出的空格数是该行所要输出的“*”个数与最后一
行所具有的“*”数目之差。这样，我们得出了该输出图形的所有有用的规律，
并可以把规律应用到程序的输出过程当中。
代码
#include <>
int main () {
int h;
while (scanf ("%d",&h) != EOF) {
int maxLine = h + (h - 1) * 2;出格式。题面要求我们在输出的每个叠筐间输出一个空行，即除了最后
一个叠筐后没有多余的空行，其它叠筐输出完成后都需要额外的输出一个空行。
为了完成这个要求，我们将要求形式改变为除了在第一个输出的叠筐前不输出一
个空行外，在其它每一个输出的叠筐前都需要输出一个额外的空行。为完成这一
目的，我们在程序开头设立了firstCase 变量来表示正在处理数据的是否为第一组
数据，毫无疑问它的初始值为true。在程序读取每组数据后，我们都测试firstCase
的值，若其为true 则表示当前处理的数据为第一组数据，我们不输出空行，并在
此时将firstCase 变量改变为false。以后，每当程序读入数据，测试firstCase 变
量时，该变量均为false，于是我们完成题目的要求，在输出的叠筐前额外的输
出一个空行，来达到题面对于输出格式的要求。
2.边界数据处理。按上文所说，我们在输出缓存中完成字符阵列排版后，需
要将该阵列四个角的字符修改为空格，但是这一修改不是一定需要的。当输入的
n 为1 时，该修改会变得多余，它会使输出仅变为一个空格，这与题面要求不符。
因此，在进行该修改之前，我们需要对n 的数值作出判断，若其不为 1 则进行修
改，否则跳过修改部分。由此不难看出，机试考题要求我们在作答时，不仅能够
大致的把握算法，同时还要细致的考虑边界数据会给我们的程序造成什么样的影
响。只有充分考虑了所有情况，并保证在所有题面明确将会出现的条件下，程序
依旧能够正常工作，这样我们才能使自己的程序真正的万无一失、滴水不漏。
本例介绍了另一种解决排版题的思路，当输出图形所具有的规律不能或者很难直
接应用到输出上时，我们就要考虑采用该例所采用的方法，先用一个二维数组来
保存将要输出的字符阵列，并在该数组上首先完成排版。因为没有了输出时从上
至下、从左至右的顺序限制，我们能更加随意的按照自己的需要或者图形的规律
来依次输出图形，从而完成题目要求。
练习题：Repeater（难度较大）（九度教程第16 题）；
五查找
查找是另外一类我们必须掌握的算法，它不仅会被机试直接考察，同时也可
能是完成其他某些算法的重要环节。对于查找问题，有难有易。可能只是直接的
对某个数字的查找，也可能涉及搜索等相对难度更大的算法。本节所涉及的查找问题，都是查找的基础。只有先充分掌握查找的概念和方法，我们才能继续学习
其他难度更大的算法。
例找x（九度教程第17 题）
时间限制：1 秒内存限制：32 兆特殊判题：否
题目描述：
输入一个数n，然后输入n 个数值各不相同，再输入一个值x，输出这个值
在这个数组中的下标（从0 开始，若不在数组中则输出-1）。
输入：
测试数据有多组，输入n(1<=n<=200)，接着输入n 个数，然后输入x。
输出：
对于每组输入,请输出结果。
样例输入：
2
13
样例输出：
-1
来源：
2010 年哈尔滨工业大学计算机研究生机试真题
由此例我们可以看出，即使是在数组中查找特定数字这样最最基本的问题，也会出现在考研机试真题当中，查找在整个算法体系中的重要性可见一斑。通过此例，我们可以了解一下查找所涉及的几个基本要素。
1.查找空间。也常被称为解空间。所谓查找，就是在该查找空间中找寻符合我们要求的解的过程。在此例中，整个数组包含的整数集就是查找空间。
2.查找目标。我们需要一个目标来判断查找空间中的各个元素是否符合我们的要求，以便判断查找活动是否已经成功。在此例中，即数组中的数字与目标数字是否相同。
3.查找方法。即利用某种特定的策略在查找空间中查找各个元素。不同的策略对查找的效率和结果有不同的影响，所以对于某个特定的问题，我们要选择切实可行的策略来查找解空间，以期事半功倍。在此题中，查找方法即线性地遍历数组。
读者可以牢记这些概念，这对在后续章节中充分的理解搜索的原理是大有裨益的。关于更高级的查找方式——搜索，将在后续章节详细讨论，这里只需对查找有初步的概念即可。
这里提出此例，即为了说明查找的相关概念。这里对解题不加过多的说明，仅提供解题代码供读者参考。
代码
#include <>
int main () {
int buf[200];
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
}查找开始点设为第一个数组元素(1)，结束点设为最后一个数组元素(10)，即查找子集为整个搜索空间{1,3,4,5,6,8,10}。
2.然后将起始点和结束点正中间的数与查找目标进行比较，若该中间数字等于目标数字则查找成功，查找结束；若大于查找目标，则说明查找目标只可能存在于查找子集中以该中间数字为界的较小的一半中，则移动查找结束点为该中间
数字的前一个数字，即新的查找子集为旧的查找子集中以中间数字为界的较小的一半；若小于查找目标，则相应的得到新的查找子集为旧查找子集中以中间数字为界的较大的一半。在该例中，即目标数字 3 小于中间数字5，移动查找结束点至中间点（5）的前一个元素（4），新的查找子集为{1,3,4}，然后继续步骤2。
3.若在查找过程中出现查找起始点大于查找结束点的情况，则说明查找子集已经为空集，查找失败。否则继续步骤 2 的查找过程。
该例的查找过程如下：
查找子集{1,3,4,5,6,8,10} 查找起始点
1(下标0)
查找终止点
10（下标6）
中间点
5（下标3）↓目标数3 小于中间数5
{1,3,4,} 1(下标0) 4（下标2）3（下标3）
↓目标数3 等于中间数3
查找成功。
若我们查找一个待查找数组中不存在的数字2，情况又会怎样呢
查找子集{1,3,4,5,6,8,10} 查找起始点
1(下标0)
查找终止点
10（下标6）
中间点
5（下标3）↓目标数2 小于中间数5
{1,3,4,} 1(下标0) 4（下标2）3（下标3）
↓目标数2 小于中间数3
{1} 1(下标0) 1（下标0）1（下标0）
↓目标数2 大于中间数1
{} 3(下标1) 1（下标0）无
↓查找子集变为空集
查找失败。
可见，若我们在数组中二分查找一个不存在的数字，其查找的最后结果为查找子集变为空集。用二分查找查找长度为L 的有序数组，时间复杂度可由原本线性查找的O（L）降低到O（logL）。
例查找学生信息(九度教程第18 题)
时间限制：1 秒内存限制：32 兆特殊判题：否
题目描述：
输入N 个学生的信息，然后进行查询。
输入：
输入的第一行为N，即学生的个数(N<=1000)
接下来的N 行包括N 个学生的信息，信息格式如下：
01 李江男21
02 刘唐男23
03 张军男19
04 王娜女19
然后输入一个M(M<=10000),接下来会有M 行，代表M 次查询，每行输入一个学号，格式如下：
02
03
01
04
输出：
输出M 行，每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息，则输出“No Answer!”
样例输入：
4
01 李江男21
02 刘唐男23
03 张军男19
04 王娜女19
5
02
03
01
04
03
样例输出：
02 刘唐男23
03 张军男19
01 李江男21
04 王娜女19
03 张军男19
来源：
2003 年清华大学计算机研究生机试真题
计算机专业考研科目及细节分析 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 四、试卷题型结构 单项选择题80分（40小题，每小题2分） 综合应用题70分 五、考查范围 【数据结构】 1、理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2、掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3、能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现
1、顺序存储结构 2、链式存储结构 3、线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构 （四）栈和队列的应用（五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1、二叉树的定义及其主要特征 2、二叉树的顺序存储结构和链式存储结构 3、二叉树的遍历 4、线索二叉树的基本概念和构造 5、二叉排序树 6、平衡二叉树 （三）树、森林 1、书的存储结构 2、森林与二叉树的转换 3、树和森林的遍历 （四）树的应用 1、等价类问题 2、哈夫曼（Huffman）树和哈夫曼编码 三、图 （一）图的概念 （二）图的存储及基本操作 1、邻接矩阵法 2、邻接表法 （三）图的遍历 1、深度优先搜索 2、广度优先搜索 （四）图的基本应用及其复杂度分析 1、最小（代价）生成树 2、最短路径 3、拓扑排序 4、关键路径 四、查找 （一）查找的基本概念（二）顺序查找法（三）折半查找法 （四）B-树（五）散列（Hash）表及其查找（六）查找算法的分析及应用 五、内部排序 （一）排序的基本概念（二）插入排序（三）气泡排序（bubble
一、单项选择题：1-40题，每题20分共80分。在每个小题给出的四个选项中选正确答案。 1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（） A、dcebfa B、cbdaef C、bcaefd D、afedcb 2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺顺序是（） A、bacde B、dbace C、dbcae D、ecbad 3、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（） 4、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（） A、13，48 B、24，48 C、24，53 D、24，90 5、在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（） A、41 B、82 C、113
D、122 6、对n（n>=2）个权值均不相同的字符构成哈弗曼树，关于该树的叙述中，错误的是（） A、该树一定是一棵完全二交叉 B、树中一定没有度为1的结点 C、树中两个权值最小的结点一定是兄弟结点 D、树中任一非叶结点的权值一定不小于下一层任一结点的权值 7、若无向图G=（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（） A、6 B、15 C、16 D、21 8、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（） A、4 B、3 C、2 D、1 9、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（） A、4 B、5 C、6 D、7
2010年全国硕士研究生入学统一考试 计算机学科专业基础综合试卷 一、单项选择题(1-40小题,每小题2分,共80分,下列每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内.) (1)若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是 (A)d,c,e,b,f,a(B)c,b,d,a,e,f(C)b,c,a,e,f,d(D)a,f,e,d,c,b (2)某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是 (A)b,a,c,d,e(B)d,b,a,c,e(C)d,b,c,a,e(D)e,c,b,a,d (3)下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是 (A)(B) (C)(D) (4)在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是 (A)13,48(B)24,48(C)24,53(D)24,90 (5)在一棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的 结点,10个度为1的结点,则树T的叶结点个数是
(A)41(B)82(C)113(D)122 (6)对n(n>=2)个权值均不相同的字符构成哈弗曼树,关于该树的叙述中,错误的是 (A)该树一定是一棵完全二叉树 (B)树中一定没有度为1的结点 (C)树中两个权值最小的结点一定是兄弟结点 (D)树中任一非叶结点的权值一定不小于下一层任一结点的权值 (7)若无向图G=(V,E)中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是 (A)6(B)15(C)16(D)21 (8)对下图进行拓扑排序,可以得到不同的拓扑序列的个数是 (A)4(B)3(C)2(D)1 (9)已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是 (A)4(B)5(C)6(D)7 (10)采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是 (A)递归次数于初始数据的排列次数无关 (B)每次划分后,先处理较长的分区可以减少递归次数 (C)每次划分后,先处理较短的分区可以减少递归次数 (D)递归次数与每次划分后得到的分区处理顺序无关 (11)对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下: 第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是 (A)冒泡排序法(B)希尔排序法(C)归并排序法(D)基数排序法 (12)下列选项中,能缩短程序执行时间的措施是 Ⅰ.提高CPU时钟频率 Ⅱ.优化通过数据结构 Ⅲ.优化通过程序 (A)仅Ⅰ和Ⅱ(B)仅Ⅰ和Ⅲ(C)仅Ⅱ和Ⅲ(D)Ⅰ、Ⅱ、Ⅲ (13)假定有4个整数用8位补码分别表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若将运算结果存放在一个8位寄存器中,则下列运算会发生益处的是 (A)r1×r2(B)r2×r3(C)r1×r4(D)r2×r4 (14)假定变量i,f,d数据类型分别为int,float,double(int用补码表示,float和double用IEEE754单精度和双精度浮点数据格式表示),已知i=785,f=1.5678e3,d=1.5e100,若在32位机器中执行下列关系表达式,则结果为真的是
计算机考研知识点 万学海文专业课教研中心 临近考研,万学海文集合考研专业课教研中心,深入研究2012年考研统考专业课考试 大纲,结合统考专业课的命题趋势、规律及特点,经过反复推敲锤炼之后,分析提炼各层级知识核心要点,从而对本年的考研命题进行预测,帮助学员把握出题重点。 数据结构 1. 线性表的基本操作问题:顺序表,单链表,带头结点的单链表,双向链表上的增 删改操作 2. 特殊线性表的性质问题:栈的FILO和队列的FIFO性质及其在实际问题中的应用 3. 二叉排序树的构造与基于其的查找问题:给定数据序列,能给出相应的二叉排序树 4. 基于二叉树性质的计算问题:计算二叉树的层数,节点总数,叶节点数等 5. 图的存储结构问题:图的矩阵表示,链表表示等表示方法的特点,以及不同的图,不同的应用问题中存储方法的选择 6. 图的最短路径问题:Dijkstra算法,给定一个图,能够按照Dijkstra算法逐步找到单源最短路径 7. 散列查找的特点与散列表的构造问题:不同散列函数的使用,不同散列存储方式的特征可以简化问题 8. 稀疏矩阵的压缩存储问题:稀疏矩阵的三元组表示,特殊矩阵的压缩存储,矩阵中元素下标的计算
9. 排序算法的选择和应用问题:根据给定的数据序列的特点,选择相应的高效排序算法,在解决特定的应用问题时,使用合适的排序算法先对数据进行处理 计算机组成原理 1. 数的原码、反码与补码表示法:给定一个数,做原码、反码与补码的相互转换 2. 浮点数的表示问题:浮点数的表示;对阶,尾数运算,规格化的计算过程 3. SRAM与DRAM的对比问题:存储特性,成本,速率等 4. Cache与主存的映射问题:组相连,全相连,直接映射,相应地址的转换问题 5. 段页式虚存地址变换计算问题:给定虚地址与段表页表,求出实际地址 6. 定长与变长操作码的对比:执行效率等 7. CPU的基本构成:ALU,寄存器,片内总线,控制器等 8. 微程序控制器结构与微地址形成:微控存,中断结构,时序等,微地址的几种形成方式 9. 总线仲裁问题:集中式与分布式的仲裁方式以及相应的仲裁器结构 10. DMA:相关的概念,执行过程,用到的硬件等 11. 多核处理器 操作系统 1. 操作系统体系结构 2. 进程的同步与互斥 3. 各种进程调度算法及其特点
计算机专业考研科目及 细节分析 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT
Ⅰ考查目标 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分 操作系统 35分 计算机网络 25分 四、试卷题型结构 单项选择题 80分（40小题，每小题2分） 综合应用题 70分 Ⅲ考查范围 数据结构 「考查目标」 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。
一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构
王道考研系列 2011 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机 学科专业基础综合 （科目代码：408） 特别鸣谢：阿三（casper08， 哈工大）王道考研系列辅导书 编写团队 予人玫瑰手留余香
2 2 共 1895个中间结点 一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一 项符合题目要求的。请在答题卡上将所选项的字母涂黑。) 1． 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是 x=2； while （x 2017计算机专业考研必知考试科目与内容计算机专业是每年很多同学报考的热门专业之一，既然选择了报考计算机专业，那就要早做准备。今天就和大家分享报考计算机专业必须知道的一些考研常识。 1、考试科目及题型 计算机科学与技术学科采用全国统考方式，初试科目调整后为4门，即政治理论、外国语、数学一和计算机学科专业基础综合，卷面满分值分别为100分、100分、150分和150分。 计算机统考只有两种题型——单选和综合应用题，其中单项选择题占80分(共40题，每小题2分)，综合应用题占70分(共7题，各题分值不等)。在综合应用题中，数据结构、组成原理和操作系统各2道，网络出1道题。 2、专业课考试内容 计算机综合满分为150分，其主要的考试内容包括：数据结构、计算机组成原理、操作系统和计算机网络。数据结构和计算机组成原理均占45分，操作系统35分，计算机网络25分。 数据结构课程以抽象为主，从具体操作上来讲，一个是数组的实现方法，一个是链表的实现方法，从算法角度来讲，难点就是递归，还有回溯法，分治法等，从应用来讲，一个是查找，一个是排序，这三个方面掌握熟练，才能在最后的考试中脱颖而出。 计算机组成原理是目前大家公认比较难的课程，实际上同学们只要掌握冯.诺伊曼模型就可以解决章节知识点融合的考试方法，当然同学们必须把控制器这个难点啃下来， 把数值的表示和计算这个复杂点理顺了。单纯对存储，数值，指令，CPU的考查，同学们都没有问题，综合起来的考查，同学们必须把握住题目中的信息点。 操作系统相对比较容易一下，我们主要还是要了解一下pv操作，熟练掌握生产者和消费者模型，读者和写者模型，哲学家进餐模型，吸烟者问题，理发师问题，独木桥问题等经典问题，学会把问题中给定的情况反馈到已知模型，通过已知模型进行修改得出答案，这部分在冲刺课程也会有专项训练。 计算机网络在近来考研中越来越来重要，自主中的分值也越来越高，击溃网络学习的快捷方法就是协议分析，从实际报文中把握体系结构的概念，层次的意义，协议的过程，应用的设计。做到这一点，网络的题目可迎刃而解。 3、专业课参考书目 科目书名作者出版社 数据结构《数据结构》严蔚敏清华大学出版社 操作系统《计算机操作系统》汤子瀛西安电子科技大学出版社 计算机组成原理《计算机组成原理》唐朔飞高等教育出版社 2015南京大学计算机845考研试题 说明：本人在28号考试过程中抄下来的，时间有限有部分试题（13个选择/共40个，1个算法大题/大题共7个）遗漏，后又根据论坛和考研群其他研友的回忆版资料进行过补充，基本完全。其余因笔记仓促亦可能有少量笔误，见谅。望后来考生，应知年与时驰、意与日去，备考及早动手，坚持到底，衷心祝福大家都能学有所成，梦想成真。 感谢在我半年备考期间与我同一自习室复习的研友们，陈梅，王超，李玲，李浩，大白，王丽坤。感谢好友比助，姗姗，贝贝，成云，康师傅，丁小琳。感谢王道南大考研群诸位学长学姐和战友们，let，嘛嘛，木哥，Tomorrow，胸大的绿色兔子汪a（没错我就是在黑你），六月（强迫症死敌！），地下铁（真诚祝福兄弟），句号，皮卡丘，倩倩，唯安，沧海，浅月，绝，别情，夜吟，风之天炼，河北的妹子i（冒泡一次激励我三天加倍努力），亮靓（学妹加油），马克图布。仰头望明月，寄情千里光。愿你们拥有想要的未来，想去的远方。2014年12月30日于天津师范大学劝学楼C区503自习室。 作者：王道论坛章凝苏（1）单项选择题（40X2分） A.和动态链表相比，以下反映了静态链表缺点的是（） A.插入、输入输出操作不便 B.存储空间有时得不到充分利用 C.要求各结点有相同的类型 D.表中各结点只能读取不能修改 B.二维数组A[8][10]按列优先次序存储在起始地址为0的连续内存单元中，其中每个元素占5个单元，元素A[6，7]的存储地址是（） C.二叉线索树中执行较困难的运算是（） A.中序线索树下查找结点的前驱 B.中序线索树下查找结点的后继 C.前序线索树下查找结点的前驱 D.后序线索树下查找结点的前驱 D.设散列表为H[11]（下标从0开始）。将关键码序列（20，15，19，43，67，30）散列到该地址空间中，散列函数为H(key)=key%11，处理冲突采用线性探查法。则等概率情况下查找成功时平均搜索长度是（） A. B. C. D. 2 E.已知一颗二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为（）A.CBEFDA B. FEDCBA C. CBEDFA D. 不确定 F.以下与数据的存储结构无关的术语是（） A.循环队列 B.链表 C.哈希表 D.优先级队列 G.具有n个关键字的有序表，采用监视哨方式查找，时间复杂度是（） (n) (n^2) (log以2为底n) (nlog以2为底n) 2018年清华大学计算机系计算机技术考研（085211）考试科目、参考书目、 复习经验 一、招生信息 所属学院：计算机科学与技术系 所属门类代码、名称：工学[08] 所属一级学科代码、名称：软件工程[0835] 二、研究方向 01（全日制）计算机技术 02（非全日制）数据科学与工程 三、考试科目 1、初试考试科目： ①101思想政治理论 ②201英语一 ③301数学一 ④912计算机专业基础综合 912计算机专业基础综合含数据结构（70分）、计算机原理（30分）、操作系统（30分）、计算机网络（20分）。 2、复试考试科目： 01方向：复试时专业综合考试内容：软件工程和编译原理。 02方向：仅招收原单位定向生（在职培养），报考类别为定向就业，在学期间不转档案和户口，不提供住宿。考生必须具有工作经验。复试时专业综合考试内容：软件工程。 四、参考书目 汤子瀛《计算机操作系统》； 唐朔飞《计算机组成原理》； 严蔚敏《数据结构》； 谢希仁《计算机网络》； 白中英《计算机组成原理》 五、复习指导 一、参考书的阅读方法 （1）目录法：先通读各本参考书的目录，对于知识体系有着初步了解，了解书的内在逻辑结构，然后再去深入研读书的内容。 （2）体系法：为自己所学的知识建立起框架，否则知识内容浩繁，容易遗忘，最好能够闭上眼睛的时候，眼前出现完整的知识体系。 （3）问题法：将自己所学的知识总结成问题写出来，每章的主标题和副标题都是很好的出题素材。尽可能把所有的知识要点都能够整理成问题。 二、学习笔记的整理方法 （1）第一遍学习教材的时候，做笔记主要是归纳主要内容，最好可以整理出知识框架记到笔记本上，同时记下重要知识点，如假设条件，公式，结论，缺陷等。记笔记的过程可以强迫自己对所学内容进行整理，并用自己的语言表达出来，有效地加深印象。第一遍学习记笔记的工作量较大可能影响复习进度，但是切记第一遍学习要夯实基础，不能一味地追求速度。第一遍要以稳、细为主，而记笔记能够帮助考生有效地达到以上两个要求。并且在后期逐步脱离教材以后，笔记是一个很方便携带的知识宝典，可以方便随时查阅相关的知识点。 （2）第一遍的学习笔记和书本知识比较相近，且以基本知识点为主。第二遍学习的时候可以结合第一遍的笔记查漏补缺，记下自己生疏的或者是任何觉得重要的知识点。再到后期做题的时候注意记下典型题目和错题。 （3）做笔记要注意分类和编排，便于查询。可以在不同的阶段使用大小合适的不同的笔记本。也可以使用统一的笔记本但是要注意各项内容不要混杂在以前，不利于以后的查阅。同时注意编好页码等序号。另外注意每隔一定时间对于在此期间自己所做的笔记进行相应的复印备份，以防原件丢失。统一的参考书书店可以买到，但是笔记是独一无二的，笔记是整个复习过程的心血所得，一定要好好保管。 天津大学计算机技术专硕考研真题 天津大学计算机技术专硕考研复习都是有依据可循的,考研学子关注事项流程为：考研报录比-大纲-参考书-资料-真题-复习经验-辅导-复试-导师，缺一不可。 首先笔者先简单地介绍一下自己的情况，笔者是2017届的考研党，报考的院校和专业是天津大学计算机技术专硕，本科是普通一本，是一个跨专业考生，很幸运地进入了复试阶段并且成为了天津大学的一员。最近正是开学季，也是大家开始要复习专业课的时候了，于是我决定把自己用过的真题资料书分享给大家，希望可以帮到考研的小伙伴们。 天津大学计算机技术专硕的专业课考试科目是901数据结构与程序设计，笔者用的真题资料书是：《天津大学901数据结构和程序设计考研红宝书》，由天津考研网主编。资料中包含了：天津大学901数据结构与程序设计1996－2007、2013、2014、2015、2016年考研真题；天津大学901数据结构与程序设计1996-2007、2013-2016年考研试题解析及参考答案；天津大学901数据结构与程序设计2000-2007、2013、2014年考研真题解析（是视频讲解课的形式）：“天津大学901数据结构与程序设计基础考研真题解析（答案+讲解视频）”，可直接搜索。下面是摘抄的部分真题： 天津大学901数据结构与程序设计2016年考研真题 今年901考试的难度不是很大，感觉上140应该问题不大，比去年稍微简单点，都不是很难，相当于acm初级水平。去年的编程题太简单，今年的编程题稍微提升了难度。然而实做题、读程序与写结束这些部分都是非常简单的，只要掌握好课本知识就没有任何问题，能快速解答。 901考试分为两个部分，就是名字中的这两个科目，其中数据结构考试题分为实做题和算法设计：C++分为程序填空，写结果+程序设计，程序设计要求输入输出可执行的完整的算法，这点与数据结构的算法设计不一样，那个只要表达清楚思想就可以了。本文运用复习课本是王道，数据结构综合联考单科，严蔚敏C语言版数据结构，谭浩强C++面向对象程序设计，这三本课本我感觉足以应付天大的901的考试了，里面有很多的考研类似题，值得大家借鉴。看这些课本的时候，我觉得应该注意，要保证你到考试的时候对数据的算法，每个算法是做什么的，它的特征，思路清晰，比如一说树的先序遍历，立刻想到递归的怎么写，非递归的怎么写，具体哪些算法需要记忆。C++编程，可以做一些ACM的简单题来练习。 数据结构实做题（共45分） 一、（10分） 计算机考研科目 计算机考研初试科目为4门，即政治理论、外国语、数学一和计算机学科专业基础综合。 从2009年起，全国硕士研究生入学考试计算机科学与技术学科实行全国统考。计算机专业研究生考试初试科目有： 英语：100分数学：150分 政治：100分专业课：150分 计算机考研「 408 」初试考试要求以及考试科目主要有： 计算机学科专业基础综合试卷，满分150分；考试时间180分钟。 试卷内容结构： 数据结构45分计算机组成原理45分 操作系统35分计算机网络25分 试卷题型结构： 单项选择题80分 (40小题，每小题2分) 综合题70分 计算机考研难度排行榜 目前国内计算机专业比较强的大学，前5名分别是北京大学、清华大学、浙江大学、北京航空航天大学、哈尔滨工业大学。 这些大学的计算机专业考研难度，都不小。其次，像电子科技大学、西安交通大学、中山大学等，相对来说也比较难考。 以下整理来自网络，大家可以参考下。 计算机考研难度排行榜前五 1、北京大学330分，数学自主命题，进复试的60多人，被刷了10个左右，330+的几个基本全留下了，复试率基本1:1.2，今年360以下的基本都去软院，录取除特殊人物外，基本看排名总排名40开外，专业排名6之外的都很危险，排名之间还要看分数差距。 2、清华大学352分(含工程硕士) 清华工程不享受奖学金，不享受国家补助，不享受公费医疗，工学录了35个，5个去深圳，每年工学收30个左右。 3、浙江大学分320(不含工程硕士) 浙大复试比例:1:1.5，进入复试240人，录取140+，刷了90人。实际录取线在350分左右，140人中只有30人公费(其中浙大本校免复试占去15个名额)，剩下的大部分交一半学费，少数全交。 4、北京航空航天大学323分(含工程硕士) 上线248个，有几个没报道，工学招151个，拟录取155个，工程拟录取50个，实际录取的各个分数段。 5、哈尔滨工业大学 320分(含工程硕士) 360以上的87个。 苏州大学计算机考研复试经验总结之前发过这篇帖子，结果很快就沉了，着实伤心，为了造福更广大的计算机考生，我这里再发一遍。 有感于考研道路的艰辛，特地将我考研过程中的一些经验写出来给15届的学弟学妹们做个参考，仅供参考，不要过分纠结于此。 我报考的是苏大学硕计算机科学与技术专业，也是每年苏大计算机院分数线最高的专业，总分328。直到今年国家线出来了我才知道苏大的学硕中两个专业：计科和软件工程的分数线是不一样的，而且相差还那么大！计科复试线今年是320分，而软件工程只有300分。 从数据可以看出，初试成绩高的，被刷掉的可能性较低，今年除了专软第三名被刷了以外，其余专业刷的都是后几名的人，但是复试对于初试的排名影响还是蛮大的，所以还是得重视，可能一不小心就掉出去了。 14年的可以统计到详细数据，但是13年的只能听上一届的人讲一下，数据没有那么详细，只能做个参考了。14年的学硕录取比例是1:1.3，专硕是1:1.5。 但是奇怪的是，今年每个专业的最后一名都录取了，这说明，苏大的复试还是很公平的，即使初试发挥的不好，也不要灰心，只要你有实力，复试也有机会逆袭的。 总的来说，考上苏大的秘诀就是初试分数尽可能的高，同时还要重视复试的上机，从今年考的情况来看，复试的上机题做出来的，基本都录取了，所以说，要逆袭，就要把上机题做出来。 复试阶段 苏大的复试还是很重要的，之前看过一篇13年考研的前辈写的帖子，说苏大复试基本不改变初试的排名，我在这里不是很认同。今年苏大采取的政策是初试500分+复试400 分的总分排名来决定你能否录取的。我们计科初试第二名那位仁兄由于上机题做的不好，结果直接掉到了17名，险些被刷了。还有专硕软件工程第三名就是被刷掉了。所以只能说，你初试分数高，被刷掉的可能性比较小，但是如果你不重视复试的上机，那么你可能就和苏大说拜拜了。 复试400分=英语口语与听力50分+上机选择题75分+上机编程75分+综合面试200分。 从分数的划分可以看出，英语那边不是很重要，听历年人说：每个人基本都是25分左右，差距也就两三分，非常小的，建议裸考。这个我不是很清楚，因为复试分数是不对外公布的，除非导师给你看，今年机缘巧合我知道了我上机的分数是137，算是比较高的，但是看到录取名单的时候，有三个初试排在我后面的同学超到我前面了，我感觉这里的分差要不就是选择题要不就是英语这块了，因为我英语啥都没准备，考试的时候表现的实在是糟糕。所以呢，我建议大家还是稍微准备一下，考前多讲讲，别张口就额……额……额…… 今年和去年试题题型完全一样，内容稍有不同（不过不代表15年不会改变题型，因为今年有一个特殊情况，原本苏大准备清明节后开始复试的，结果江苏省教育部下达指令要求清明前必须全部搞完，所以苏大准备的非常的仓促，英语口语题型与去年相同，编程题是12年编程题的微改动，可能15年就没这么幸运了）。 ?英语一共4道题目： 第一题：用英语介绍你的名字、专业和座位号（我个人感觉就是考生信息的核对，只需要间接回答一下名字、报考专业、座位号就行了，苏大的英语考试座位号是这样的，A5，B3等等） 第二题：读一个小短文（今年考的是关于移动手机怎么方便人的生活的，等等）一开始有半分钟还是一分钟的准备时间，反正我当时没有及时按下题目翻页键，傻乎乎的在第一题停留了十几秒，后来才按翻页键看到下一页的短文的。短文单词不是很难，都能认识，就是有的句子有点长，我自己没有来得及提前过一遍，所以读起来的时候断句非常糟糕，别的还好。 第三题：三段小对话，每段对话后面有一个题目，额……我听得很糟糕，我们一起的有个369的大神人家是全听懂了，我以为我听懂了，后来我发现我都听错了……这个问完问题一定要讲话，据说只要讲话就有分数，不讲话就没分，不管你讲什么，大声讲出来！ 第四题：一个即兴小演讲，今年题目是：What is more important to you?the knowledge from books or personalexperience?我就讲了两句话，中间还停顿了十几秒，简直太糟糕了……听说有的同学直接就背自己准备的自我介绍……还是那句话，只要开口讲话就行，不开口肯定是0分啊。 ?上机（选择题与编程题）： 选择题50题，每题1.5分，编程题就一题，75分。 全国硕士研究生入学统一考试计算机专业课推荐参考书目 一、数据结构 ★严蔚敏、吴伟民编著：《数据结构（c语言版）》，清华大学出版社 ★严蔚敏、吴伟民编著：《数据结构题集(C语言版)》，清华大学出版社 二、计算机组成原理 ★唐朔飞编著：《计算机组成原理》，高等教育出版社，1999年版 ★唐朔飞编著：《计算机组成原理学习指导与习题解答》，高等教育出版社，2005年9月 ★白中英主编：《计算机组成原理》，科学出版社 三、操作系统 ★汤小丹、梁红兵、哲凤屏、汤子瀛编著：《计算机操作系统(第三版)》，西安电子科技大学出版社★梁红兵、汤小丹编著：《计算机操作系统》学习指导与题解(第二版)，西安电子科技大学出版社，2008年9月 四、计算机网络 ★谢希仁编著：《计算机网络(第5版)》，电子工业出版社 ★高传善、毛迪林、曹袖主编：《数据通信与计算机网络（第2版）》，高等教育出版社 说明： ★ 为首推书；出版年份不需要严格要求，一般是越新越好，关键以出版社和作者为主要参照。 相关参考辅导书： ★本书编写组：《全国硕士研究生入学统一考试计算机专业基础综合考试大纲解析》，高等教育出版社，2008年10月 ★巩微、冯东晖主编：《2009年考研计算机学科专业基础综合考试全真模拟试题集》，原子能出版社，2008年10月★阳光考研命题研究中心编写：《2009年考研计算机科学专业基础综合考试教程》，中国人民大学出版社，2008年11月 2009年计算机科学与技术学科联考高分突破考前冲刺400题 一、数据结构 1.教材：《数据结构》严蔚敏清华大学出版社 清华大学严蔚敏的这本数据结构的教材是国内数据结构教材的权威。也是国内使用最广，其广度远远超越其他同类教材，计算机考研专业课命题必定以它为蓝本。这一本数据结构是2007年的最新版本，完全适合任何学校的考研数据结构的复习之用，是数据结构学习最权威的教材。 2.辅导书：《算法与数据结构考研试题精析（第二版）》机械工业出版社 2016年东南大学935计算机专业基础考研真题（回忆版） 2016年的题型跟14年的一样。 选择题类似2014年的，共40道选择题。其中操作系统16道，数据结构和组成原理均12道。数据结构和操作系统都是很基础的，计组稍微难一点，不过仔细复习注意联系还是都可以轻松地选出正确答案的。 操作系统 1．页表的题。（但是跟往年的差距很大） 一个计算机的逻辑地址空间有64个页，每个页的大小是2048B。物理地址空间占用32个页框（frame）。一个程序P占用6个页框，并且0到5号逻辑页分别分配到3，4，1，7，10，11号页框（具体数字不太确定，只确定最后两个）。 （1）P的逻辑地址有多少位 （2）该计算机的物理地址有多少位 （3）P运行时，逻辑地址为06045H和0C234H的物理地址分别是什么（这两个数字的具体是多少也不记得了，但是每个数字的前两位我确定是对的，而且都是5位16进制数）（4）若访问CPU的时间是200us，访问页表的时间是40us，命中率为90%，则有效访问时间是多少。（具体数字记不清了） 2．文件系统的题。（比较类似15年王道书上的237的第7题） 一个文件系统有10个索引块，每个磁盘块大小为2048B。 （1）若这10个索引块都是直接索引，则最大的文件是多大 （2）若有7个直接索引，2个一级间接索引，1个二级间接索引，最大的文件系统有多大 （3）若不用索引用FAT，FAT的大小已给。（具体想不起来数据了QAQ，反正这个题比较简单） 3．生产者消费者的题 有三个进程，一个进程往缓冲区里放数，缓冲区里面最多只能放n个数。另外两个进程，一个从缓冲区里取负数，另一个从缓冲区里取非负数。实现这三个进程的同步过程。 数据结构 1．想一个从10万个数里面选出最小的10个数的实现方法，不需要用算法实现，分析你的算法为什么高效。 2．一个数组，写一个算法找出这个数组中最大的逆序差。（逆序差就是i＜＝j的情况下，A[j]－A[i]的差。比如4 15 5 6 9 1 16 11中最大的逆序差就是16－1＝15） 计算机组成原理 推荐答案 一、数据结构 1.教材：《数据结构》严蔚敏清华大学出版社 清华大学严蔚敏的这本数据结构的教材是国内数据结构教材的权威。也是国内使用最广，其广度远远超越其他同类教材，计算机考研专业课命题必定以它为蓝本。这一本数据结构是2007年的最新版本，完全适合任何学校的考研数据结构的复习之用，是数据结构学习最权威的教材。 2.辅导书：《算法与数据结构考研试题精析（第二版）》机械工业出版社 网上广为流传的数据结构1800题相信只要是计算机考研的同学无人不知无人不晓。其实1800题是2001年推出来的，当时编者把电子版免费分享给大家，却很少有人知道它也有纸质版本就是《算法与数据结构考研试题精析》。第二版是2007年最新出版的，对里面的题目进行了大量的更新，去掉了一些比较过时和重复的题，加上了很多名校最近几年的考研真题，总共大约1650题左右。真题就是训练的最好武器，相信当你复习完这本数据结构辅导书后，任何关于数据结构的考题都是小菜一碟。 二、计算机组成原理 1.教材：《计算机组成原理》唐朔飞高等教育出版社 《计算机组成原理》白中英科学出版社 这两本教材都是普通高等教育十一五国家级规划教材，其权威性不言而喻，在国内是使用最广的两本教材，而前者应该略胜一筹。而且两位老师说教学的计算机组成原理课程都是国家级精品课程，网上甚至还有他们的讲课视频可以下载，再配合教材的使用，这样可以更加增强学习的效率。 2.辅导书：《计算机组成原理考研指导》徐爱萍清华大学出版社 《计算机组成原理--学习指导与习题解答》唐朔飞高等教育出版社 清华大学的这套辅导教材在广大的考生中有着极为优秀的口碑，特别是系列中的李春葆《数据结构考研辅导》在数据结构考研辅导资料中占据着数一数二的地位。这本辅导书通俗易懂，重点突出，特别适合于考研复习，特别是武汉大学以前的专业试题就完全以这本书为蓝本，甚至直接考上面的原题。唐朔飞的题集上面的题型也比较适合于考研，和它的配套教材一样，是一本不可多得的好书。 三、操作系统 1.教材：《计算机操作系统(修订版)》汤子瀛西安电子科技大学出版社 毫无疑问这本教材是国内操作系统教材的权威，使用度很广，以往一般考操作系统的学校基本都以此本教材作为指定教材。在国内目前还没有其他同类教材的使用广度和其相媲美，所以考研操作系统的复习应以这本书为准，相信操作系统统考试题的出题肯定也会以这本教材为蓝本。 2019上海交通大学计算机技术专硕考研考试科目及参考书目 一、学院介绍 学院目前有38名教职员工，拥有博士学位26人。其中包括教授6人、副教授16人、博导8人。软件学院的学科带头人傅育熙是国家杰出青年基金获得者和上海市优秀学科带头人。学院还有中组部青年拔尖计划人才1，教育部新世纪人才2人。 学院以互联网时代的软件创新为中心，秉承“以理论研究为基础、以系统研究为核心、以应用研究为驱动”的理念，面向国际学术前沿和国民经济主战场，广泛开展国际合作与产业合作，努力建设世界一流的软件人才培养和技术创新中心，为互联网时代培养优秀软件人才、研究创新软件理论、开发领先软件系统、孵化先进软件产品。 本学科培养软件工程专业的本科、硕士和博士研究生。针对互联网时代特点，面向高质量、大规模软件开发、运行和维护的全过程，采用科学教育和工程教育结合的综合性能力培养方式，重视培养学生的坚实的学科知识基础以及解决复杂工程问题的能力，通过设计和创造从软件内核到大型应用系统的实践和研究，以成长为具有国际竞争力的高端软件工程师和未来科学家。并与一大批中外知名IT企业建立了长期合作关系，有效提高了学生的实践 创新能力，历届毕业生的就业率和就业质量一直处于学校各专业的前列。 2011年5月，学院申报成功软件工程一级学科，2012年，在全国第三次学科评估中，软件工程一级学科获得全国第7名。 二、考试科目 初试科目： ①101思想政治理论 ②201英语一 ③301数学一 ④408计算机学科专业基础综合 三、参考书目 《数据结构》(C语言版) (严蔚敏清华大学出版社) 《计算机组成原理（第2版）》（唐朔飞高等教育出版社） 《计算机操作系统》(汤子瀛西安电子科技大学) 《计算机网络》(谢希仁电子工业出版社) （注：仅做参考，也可用其他辅导书籍） 王道论坛 王道论坛计算机考研机试指南 王道论坛 2013.01.06 写在前面的话 各位王道的小崽子们，今天你们考完初试了，感觉解放了吧？轻松了吧？无论结果如何，总算坚持到了最后。但是，其实你的考研生活只刚刚走出了第一步，接下来会有初试成绩出来前的煎熬、分数线出来的煎熬、准备复试以及复试的煎熬以及录取结果出来前的煎熬，这些都远远比初试更折磨人，未来的两个月你会感觉到王道没有吓唬你们。 王道是个好姑娘，四年多的时光里陪伴了接近二十万计算机考研人，不离 不弃。今年不小心又压中一道算法题，说实话，王道的书里有那么多的题，知识点又只有那么多，总能瞎猫碰见死耗子吧？王道尊重的不是考研这个行业，而是你们这群执着的小崽子们的梦想！看着你们圆梦，我们内心充满了成就感。 初试考完了，是不是应该好好放松放松？是不是初试考得好，录取就肯定没有问题了？对不起，这个不是计算机专业研究生考试的规则。目前已经有越来越多的高校采用上机考试的形式来考察考生的实际动手编程能力，并且机试在复试中所占的比例非常高，并且很多高校规定复试成绩不及格者，一律不得录取。目前国内高校开展 ACM 教学的高校非常少，而 ACM 是目前所有高校机试所采取 的唯一形式，因此提早开始准备和练习，对于一个完全没有接触过 ACM 的计算机考研人来说，是必须的！ 为了方便各位道友练习机试，我们编写了本书，搭建了九度Online Judge （），并收集了全国各大高校的复试上机真题，希望能给大家 复试上机考试提供强有力的支持。你可以直接使用王道论坛的帐号进行登录。如果您在使用过程中遇到问题，欢迎你到复试机试讨论专区发贴提出。目前已经收录了我们能够收集到的各高校上机复试真题，欢迎大家继续向我们提供各高校上机真题，具体请站内信或者电子邮件联系浩帆（Email:qihu#https://www.doczj.com/doc/2b11048375.html,）。此外，华科的上机题我们经过了变型，将其中一些便于修改成OJ判题的题目收录进了 我们的OJ。 考研其实没有什么诀窍，就是每天比别人早起一点，晚睡一点，比别人早准备一点，勤奋一点。考研离我已经很远了，同时我也坚信一个写不出合格代码的计算机专业的学生，即使考上了研究生，无非也只是给未来失业判个缓期执行而已。 小崽子们，要忠实于自己心底的梦想，勇敢地坚持下去，而当下，请开始 准备复试吧，熬过这两个月，一切就都好了。 拟录取名单出来有一阵了，也已经忙完了诸多手续问题，静待六月份的录取通知书。现在把自己的一些情况和复习经验整理一下，希望能够帮到奋斗在考研一线的学弟学妹。 我初试成绩67+71+109+107=354，机试75，面试85，总成绩第29名拟录取浙大计算机科学与技术学硕。可以看出我的实力并不突出，也没什么特别有优势的方面，但我本科是普通的一本院校，本科专业数字媒体技术也并非计算机科班出身。所以我的复习经验应该能为各位提供一些指导和帮助。 首先回答一些常见问题。如果您想直接看复习经验可跳过此部分。 1.学硕or专硕? 除了学硕方便读博以外，学硕和专硕没有太大区别。浙大官方的通知是只可报名学硕，专硕从学硕中调剂。但今年复试名单上仍然有32位同学报名了专硕，并且录取了其中的31位，我猜想这三十多个名额是保留给本校学生的。所以今年录取校外的名额是57名学硕和调剂的23名专硕。而报名考生预计在900名左右。 2.我本科学校不好，浙大会不会歧视? 不会。浙大不会考虑你的本科学校，但会仔细研究你的个人能力。如果你是三本学校中的佼佼者，依然有被录取的机会。 3.我本科成绩不好，浙大看成绩单吗? 看。他会要求你提交本科成绩单。但分数并不是最关键的，老师对你本科做出过什么作品更感兴趣。参加的竞赛，做过的项目，做得好的课程设计，都可以在面试时拿出来给老师讲，这些就是你的资本。我本人并没有做过项目，但几门课程的课程设计做的不错，老师很感兴趣，我的面试成绩也就排进了前十名。 4.软工硕士怎么样? 软工学制两年，第一年上课第二年实习，全程学费40000，据说不安排导师。计算机学制两年半，没有实习时间(只能暑假实习)，不收学费，一个导师一般带1～3名学生。软工比计算机初试科目少一门组成原理，但报的人多，难度也没比计算机低很多。 复习经验：初试篇 初试内容如下：政治，英语一，数学一，408基础综合(组成原理，操作系统，计算机网络，数据结构)。 复习奥义：全面和反复(出自王道408复习指导)，记住，好的习题集一定要反复多做几遍，辅导书一定要反复多看几遍，才有效果。 1.政治2017计算机专业考研必知考试科目与内容
南京大学计算机考研试题
2018年清华大学计算机系计算机技术考研(085211)考试科目、参考书目、复习经验---新祥旭考研
天津大学计算机技术专硕考研真题
计算机考研科目
苏州大学计算机考研复试经验总结
计算机专业课推荐参考书目
2016年东南大学935计算机专业基础考研真题(回忆版)【圣才出品】
计算机专业考研专业科目参考书
2019上海交通大学计算机技术专硕考研考试科目及参考书目
Word版王道计算机考研机试指南
【考研经验】浙江大学计算机科学与技术2016年考研经验分享
相关主题
文本预览