王道论坛
王道论坛计算机考研机试指南
王道论坛
写在前面的话
各位王道的小崽子们，今天你们考完初试了，感觉解放了吧？轻松了吧？无论结果如何，总算坚持到了最后。但是，其实你的考研生活只刚刚走出了第一步，接下来会有初试成绩出来前的煎熬、分数线出来的煎熬、准备复试以及复试的煎熬以及录取结果出来前的煎熬，这些都远远比初试更折磨人，未来的两个月你会感觉到王道没有吓唬你们。
王道是个好姑娘，四年多的时光里陪伴了接近二十万计算机考研人，不离
不弃。今年不小心又压中一道算法题，说实话，王道的书里有那么多的题，知识点又只有那么多，总能瞎猫碰见死耗子吧？王道尊重的不是考研这个行业，而是你们这群执着的小崽子们的梦想！看着你们圆梦，我们内心充满了成就感。
初试考完了，是不是应该好好放松放松？是不是初试考得好，录取就肯定没有问题了？对不起，这个不是计算机专业研究生考试的规则。目前已经有越来越多的高校采用上机考试的形式来考察考生的实际动手编程能力，并且机试在复试中所占的比例非常高，并且很多高校规定复试成绩不及格者，一律不得录取。目前国内高校开展ACM教学的高校非常少，而ACM是目前所有高校机试所采取
的唯一形式，因此提早开始准备和练习，对于一个完全没有接触过ACM的计算
机考研人来说，是必须的！
为了方便各位道友练习机试，我们编写了本书，搭建了九度OnlineJudge （），并收集了全国各大高校的复试上机真题，希望能给大家
复试上机考试提供强有力的支持。你可以直接使用王道论坛的帐号进行登录。如果您在使用过程中遇到问题，欢迎你到复试机试讨论专区发贴提出。目前已经收录了我们能够收集到的各高校上机复试真题，欢迎大家继续向我们提供各高校上机真题，具体请站内信或者电子邮件联系浩帆（）。此外，
华科的上机题我们经过了变型，将其中一些便于修改成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
通过该例，我们基本明确了机试试题的问题形式，以及问题各部分所起到的作用。这里补充解释一下所谓特殊判题（SpecialJudge）的含义，特殊判题常被应用在可能存在多个符合条件的答案的情况下，若评判系统采用了特殊判题，那么系统只要求输出任何一组解即可；若系统对该题并没有采用特殊判题，那么你必须严格按照题目中对输出的限定输出对应的答案（如输出字典序最小的解）。
得到题目后，考生在计算机上立即编写程序，确认无误后，将该程序源代码提交给评判系统。评判系统将考生提交的源代码编译后，将后台预先存储的输入测试数据输入考生程序，并将该程序输出的数据与预先存储在评判系统上的“答案”进行比对得出结果。
评判系统评判考生程序后，实时地将评判结果返回考生界面，考生可以根据该结果了解自己的程序是否被评判系统判为正确，从而根据不同的结果继续完成考试。
三评判结果
本节将对评判系统评判考生提交程序后返回的结果做详细的说明，并且针对不同的返回结果，对可能出现错误的地方作出初步的界定。
Accepted（答案正确）：你的程序对所有的测试数据都输出了正确的答案，你已经得到了该题的所有分数，恭喜。
WrongAnswer（答案错误）：评判系统测试到你的程序对若干组（或者全部）测
试数据没有输出正确的结果。
出现该种错误后，一般有两种解决方向：如果对设计的算法正确性有较大的把握，那么你可以重点考虑代码健壮性，即是否存在某些特殊数据使程序出现错误，比如边界数据，比如程序中变量出现溢出。另一种方向，即怀疑算法本身的正确性，那么你就需要重新考虑你的算法设计了。
PresentationError（格式错误）：评判系统认为你的程序输出“好像”是正确的，
只是没有严格按照题目当中输出所要求的输出格式来输出你的答案，例如你忽略了题目要求在每组输出后再输出一个空行。
出现这种错误，往往预示着你离完全正确已经不远了，出现错误似乎只是因为多输出了一些空格、换行之类的多余字符而已。但这不是绝对的，假如在排版题（后文会有介绍）中出现格式错误，那么有可能你离正确的答案仍然有一定的距离。
TimeLimitExceeded（超出时间限制）：你的程序在输出所有需要输出的答案之前
已经超过了题目中所规定的时间。
若这种结果出现在你的评判结果里，依然有两种方向可供参考：1、假如你确定算法时间复杂度能够符合题目的要求，那么依旧可以检查是否程序可能在某种情况下出现死循环，是否有边界数据可能会让你的代码不按照预想的工作，从而使程序不能正常的结束。2、你设计的算法时间复杂度是否已经高于题目对复杂度的要求，如果是这样，那么你需要重新设计更加高效的算法或者对你现行的算法进行一定的优化。
RuntimeError（运行时错误）：你的程序在计算答案的过程中由于出现了某种致
命的原因异常终止。
你可以考虑以下几个要点来排除该错误：1、程序是否访问了不该访问的内存地址，比如访问数组下标越界。2、程序是否出现了除以整数0，从而使程序异常。3、程序是否调用了评判系统禁止调用的函数。4、程序是否会出现因为递归过深或其他原因造成的栈溢出。
CompileError（编译错误）: 你提交的程序并没有通过评判系统的编译，可根据更详细的编译信息修改你的程序。
MemoryLimitExceeded（使用内存超出限制）: 你提交的程序在运行输出所有的答案之前所调用的内存已经超过了题目中所限定的内存限制。
造成这种错误的原因主要有两个方面：1、你的程序申请过多的内存来完成所要求的工作，即算法空间复杂度过高。2、因为程序本身的某种错误使得程序不断的申请内存，例如因为某种原因出现了死循环，使得队列中不断的被放入元素。当然也千万别忽略自己的低级错误，比如在声明数组大小时多打了一个0。
OutputLimitExceeded(输出超出限制): 你的程序输出了过多的东西，甚至超出了评判系统为了自我保护而设定的被评判程序输出大小的最高上限。
一般来说该种错误并不常见，一旦出现了也很好找原因。要么就是你在提交时忘记关闭你在调试时输出的调试信息（我经常输出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也经常为广大考生提供在线模拟考试训练。我们可以点击“比赛及考试”按钮，来查看过往的比赛以及近期的比赛安排，从而有选择的参加在线比赛，考察自己的训练质量，为日后进一步训练做出导向
总结
本节主要介绍机试的意义、形式，以及机试题的形式和考察的方法，并在最
后给出了我们可以完成机试训练的网站——九度OnlineJudge。
第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 printf("%s%d%d\n",buf[i].name,buf[i].age,buf[i].score); } } return0; } 由于已经指明了结构体的小于运算符，计算机便知道了该结构体的定序规则（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 Forexample,years2004,,2181and2300arenot leap. Yourtaskistowriteaprogramwhichwillcomputethedayofweek correspondingtoagivendateinthenearestpastorinthefutureusingtoday’s agreementaboutdating. 输入： Thereisonesinglelinecontainsthedaynumberd,monthnameMandyear numbery(1000≤y≤3000).ThemonthnameisthecorrespondingEnglishname startingfromthecapitalletter. 输出： OutputasinglelinewiththeEnglishnameofthedayofweekcorrespondingto thedate,. 样例输入： 9October2001 14October2001 样例输出： 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 }; structDate{ 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 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个学生的信息，然后进行查询。 输入： 东南大学计算机专业基础历年考研真题答案汇编 最新资料，WORD格式，可编辑修改！ 目录 2014年东南大学935计算机专业基础考研真题 (3) 2005年东南大学935计算机专业基础考研真题 (5) 2004年东南大学935计算机专业基础考研真题 (10) 2014年东南大学935计算机专业基础考研真题 2014年东南大学935计算机专业基础（回忆版） 题量：40道选择题，7道大题。 39.磁盘上有1800个磁道，每个磁道有120个分区，每个分区最多2KB，现磁盘5400MB/min的转速，求最大带宽 A.2点多 MB/S B.好像是9点多 MB/S C.20.6 MB/S D.20点多 MB/S （记得不是很清楚） 大题 1.死锁的四个条件. 银行家算法 2.PV同步 3.hash排序 散列表，求成功和不成功下平均查找长度 4.设计一个判断一维数组中是否有主函数存在。比如说 A[]={’a’,’b’,’a’,’c’,’a’,’a’}，A中’a’有4个，大于长度的一半，输出存在主函数’a’，B[]={’a’,’b’,’d’,’c’,’e’,’f’}，B 中没有元素的个数大于长度的一半，输出不存在主函数’a’。c/c++语言实现，简单文字说对程序的思路，并求时间复杂度和空间复杂度。 5.cache地址，偏移量和指令格式综合在一起 6.基址运算 这一个月来睡了不超过150小时，记忆变得很差，大题怎么也想不起来第一题是什么了，只感觉是很简单的 选择都是些基础性的东西，知识点很多，尽量看全 补充： 一、选择包含知识点： 1.给了一个入栈序列，下列是合法出栈序列的是？ 2.下列哪个不是特权指令 3.下列哪个不是算法的重要特性 4.排序（很常规，有关排序有几道选择） 5.一个有7个数的数列，采用快速排序，至少需要比较多少次？ 6.组成原理有关中断....串行判优平行判优的内容……. 7．四个序列中哪个不是二叉排序树的先序遍历序列 8．选择题哪个是特权指令的题目两个选项B读时钟指令，C设置基址寄存器的值 9．流水线加速比 10．图的层次遍历 11．Round Robin 计算机统考是09年开始的，所以09年以前都是各个大学自己命题，所以各个大学的复试分数没有可比性。所以只有09年可以参考。以下就是09年给NB大学的复试分数线。其他一些不入流的大学就不用看了，计算机考研就在这些大学里挑。 1、北京大学（分数排名） 330 数学自主命题，进复试的60多人，被刷了10个左右，330+的几个基本全留下了，复试率基本1：1.2，今年360以下的基本都去软院，录取除特殊人物外，基本看排名总排名40开外，专业排名6之外的都很危险，排名之间还要看分数差距 2、清华大学 352（含工程硕士） 清华工程不享受奖学金，不享受国家补助，不享受公费医疗，工学录了35个，5个去深圳，每年工学收30个左右 3、南京大学 341 （不含工程硕士，南大工程的复试线是其工科校线到341之间） 计划招收工学硕士90人，本校和外校推免生一共34人，通过考试招收56人，按照1：1.2的比例，共有68人进入复试，工学刷下来的可以直接选读工程硕士（南大工程硕士可以评定奖学金的），无需复试 4、浙江大学（分数排名） 320（不含工程硕士） 浙大复试比例：1：1.5，进入复试240人，录取140+，刷了90人。实际录取线在350分左右，140人中只有30人公费（其中浙大本校免复试占去15个名额），剩下的大部分交一半学费，少数全交 5、复旦大学 325（不含工程硕士） 工学招80个，已有48名免推生，复旦专硕的复试线是其工科校线310，复旦专硕和清华专硕待遇一样 6、哈尔滨工业大学（分数排名） 320（含工程硕士） 360以上的87个 7、上海交通大学 333（含工程硕士） 工程硕士享受奖学金，享受公费医疗，可参与学校专业奖学金评比 8、中科院计算所338 （含工程硕士，同软件所待遇） 今年扩招了11个工程，计算所的工程与工学硕士待遇没有差别，只是不能直博 9、中科院软件所300（含工程硕士） 软件所工程全部公费，享受中科院每月补助！09软件所分数很异常。因为08年分数线过高，比计算所的还高5分，所以09很多人都不敢报，加上扩招，分数线自然就低了。10分数线肯定会提高的，要说稳定和实力更强的还是计算所，如果相信自己的实力，还是考计算所吧 10、中国科学技术大学 315 （含工程硕士，中科大工程无奖学金，无国家补助） 今年中科大没公费了，80个工学硕士，前40第一年学费全免，后40免一半学费，60个工程学费全额交，第二年的学费到第一年结束时候再讲 Word上机练习题 1．打开Word，输入如下内容： 【文档开始】 今日荣宝斋 荣宝斋的木版水印技艺，久已闻名海内外，其制作工厂的师傅们，均属艺林翘楚。目前，荣宝斋及其门市部仍在经营和发展各项业务，包括经销古今书画家的真迹或木版水印作品，供应文房四宝，提供装裱、加工修复等业务。其下属荣宝斋出版社、荣宝斋艺术品拍卖公司、荣宝外贸公司、服务公司亦为书画家们创作和繁荣书法绘画艺术、增进国际文化交流做出贡献。 【文档结束】 按要求对文档进行格式设置： ①标题： 字体：隶书；字形：加粗；字号：小二号；字体颜色：绿色；位置：水平居中； 下滑线线形：波浪形；下滑线颜色：紫罗兰（128,0,128）；字符间距：缩放90%，间距加宽3磅，位置降低2磅；字符效果：七彩倪虹。（10,13没有这个效果） ②正文文字： 字体：仿宋；字号：四号；字体颜色：淡紫色（255,83,255）。行间距：1.5倍行间距；段落：首行缩进2个字符；左右各缩进2个字符；分栏：分为等宽3栏，并加分割线。 ③插入页眉页脚：页眉为“荣宝斋简介”，居中显示；页脚为当前日期。 ④设置奇偶页不同的页眉和页脚。 ⑤将该文档以名字WD1．DOC保存在C盘下。 2．打开Word，输入如下内容： 【文档开始】 云居寺简介 位于北京房山区境内的云居寺建于隋末唐初。云居寺的石经山藏经洞中的石经始刻于隋大业年间（公元605年），僧人静琬等为维护正法刻经于石。刻经事业历经隋唐、辽、金、元、明六个朝代，绵延1039年，篆刻佛经1122部3572卷14278块。这时石阶文化史上罕见的壮举，堪与文明寰宇的万里长城、京杭大运河相媲美，是世上稀有而珍贵的文化遗产。 【文档结束】 按要求对文档进行格式设置： ①标题： 字体：华文新魏；字形：加粗，倾斜；字号：小二号；字体颜色：玫瑰红；字体加着重号；字符间距：缩放150%；字符效果：礼花绽放（07版）。位置：水平居中。 ②正文文字： 字体：楷体_GB2312；字号：四号；段间距：段前1行，段后0.5行；首字下沉：2行；首字字体：华文楷体；首字颜色：茶色；插入当前日期和时间：在段尾插入，格式为××年××月××日； ③设置页边距上、下各2.5厘米，左、右各3厘米；纸张大小为A3； ④在文档下方插入一幅剪贴画（可以任选），将环绕方式设置为紧密型，水平对齐方式设置为居中对齐。 ⑤为该文档设置打开权限密码（密码可自己设定），并将该文档以名字WD2．DOC保存在C 盘下。 3．打开Word，输入如下内容： 2015年全国硕士研究生入学统一考试 计算机学科专业基础综合试题 一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。 1．已知程序如下： int s(int n) { return (n<=0) ? 0 : s(n-1) +n; } void main() { cout<< s(1); } 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main() C．m ain()->S(0)->S(1) D．S(1)->S(0)->main() 2．先序序列为a,b,c,d的不同二叉树的个数是 A．13 B．14 C．15 D．16 3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是 A．24，10，5和24，10，7 B．24，10，5和24，12，7 C．24，10，10和24，14，11 D．24，10，5和24，14，6 4．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是 A．根节点的度一定为2 B．树中最小元素一定是叶节点 C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树 5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={ 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位机器中执行下列关系表达式,则结果为真的是 2008-2009计算机学全国各院校排名及分数线计算机应用技术专业国家线(2008年) 类别总分政治外语专1专2 A类考生﹡30044446666 B类考生﹡29040406060 C类考生﹡28538385757 计算机应用技术专业国家线(2009年) 类别总分政治外语专1专2 A类考生﹡27537375656 B类考生﹡26534345151 C类考生﹡25531314747 *A类考生：报考地处一区招生单位的考生。 *B类考生：报考地处二区招生单位的考生。 *C类考生：①报考地处三区招生单位的考生;或者②目前在三区工作且定向或委托培养回原单位的考生。 一区：北京、天津、上海、江苏、浙江、福建、山东、河南、湖北、湖南、广东11省(市); 二区：河北、山西、辽宁、吉林、黑龙江、安徽、江西、重庆、四川、陕西10省(市); 三区：内蒙古、广西、海南、贵州、云南、西藏、甘肃、青海、宁夏、新疆10省(区)。 2008年、2009年计算机应用技术专业排名A+、A类院校分数线 排名招生单位 2008年分数线2009分数线 总分政治外语专1专2总分政治外语专1专2 1清华大学（A+）3205050808031550508080 2浙江大学（A+）3305353909032050508080 3*哈尔滨工业大学 （A+） 3105050828232050508282 4北京大学（A+）3105050909030050509090 5东南大学（A+）3205353888831548488080 6东北大学（A+）3004545707029542426363 7西北工业大学（A+）3054545707029045457070 8安徽大学（A+）2904040606026534345151 9上海交通大学（A+）3505555858532055508080 10华中科技大学（A+）3205050909030547478080 11北京航空航天大学 （A+） 3155050808030045457575 12北京理工大学（A+）3105050757530545456868 13西安电子科技大学 （A+） 2904040606026534345151 14西安交通大学（A+）3355050808030045457575 15*吉林大学（A）31045456890290404090（60）90（60）16西南交通大学（A）2904040606026534345151 王道考研系列 2011 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机 学科专业基础综合 （科目代码：408） 特别鸣谢：阿三（casper08， 哈工大）王道考研系列辅导书 编写团队 予人玫瑰手留余香 2 2 共 1895个中间结点 一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一 项符合题目要求的。请在答题卡上将所选项的字母涂黑。) 1． 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是 x=2； while （x 计算机科学与技术专业考研院校排名 计算机科学与技术专业考研热门院校排名，其中包含众多院校。希望能够对于处于备考初期阶段的2017考研的`同学们在选择院校的过程中提供帮助。 学校代码及名称 学科整体水平得分 10003清华大学 95 90002国防科学技术大学 88 10001北京大学 87 10006北京航空航天大学 82 10213哈尔滨工业大学 10248上海交通大学 10335浙江大学 10284南京大学 80 10358中国科学技术大学 79 10145东北大学 77 10487华中科技大学 10013北京邮电大学 76 10247同济大学 10486武汉大学 10614电子科技大学10699西北工业大学10246复旦大学 75 10286东南大学 10558中山大学 10183吉林大学 74 10533中南大学 10610四川大学 10611重庆大学 10698西安交通大学10701西安电子科技大学10002中国人民大学 72 10004北京交通大学10005北京工业大学10007北京理工大学 10056天津大学 10359合肥工业大学10532湖南大学 10008北京科技大学 70 10141大连理工大学10217哈尔滨工程大学10287南京航空航天大学10422山东大学 10027北京师范大学 69 10055南开大学 10269华东师范大学10288南京理工大学10613西南交通大学10617重庆邮电大学10730兰州大学 90006解放军理工大学10108山西大学 68 10216燕山大学 10285苏州大学 10058天津工业大学 67 10060天津理工大学10186长春理工大学10280上海大学 10293南京邮电大学10294河海大学 10299江苏大学 10337浙江工业大学10475河南大学 10491中国地质大学10511华中师范大学10635西南大学 10697西北大学 10718陕西师范大学10755新疆大学 10032北京语言大学 65 10143沈阳航空航天大学10144沈阳理工大学10252上海理工大学10295江南大学 WORD部分选择题 1、在Word文档中，“插入”菜单中的“书签”命令是用来__________。 A) 快速移动文本 B) 快速定位文档 C) 快速浏览文档 D) 快速复制文档 2、在Word中，下列关于模板的说话中，正确的是_______。 A) 在Word中，文档都不是以模板为基础的 B) 模板不可以创建 C) 模板的扩展名是.TXT D) 模板是一种特殊的文档，它决定着文档的基本结构和样式，作为其他同类文档的模型 3、WORD中在编辑文档时，如果希望在“查找”对话框的“查找内容”文本框中只需输入一个较短的词，便能依次查找分散在文档各处的较长的词，如输入“look”,便能将“look”、“looked”…“looking”等，那么在“查找”对话框中，用户选择复选框（）。 （A）、“同音” （B）、“模式匹配” （C）、“查找单词的各种形式” （D）、“全字匹配” 4、WORD中拆分单元格的完整含义是： （A）、把一个单元格拆分成两个，并分别并到左、右两个相邻的单元格中去 （B）、把一个单元格的行数或列数增多 （C）、把一个单元格的行数或列数一分为二 （D）、把一个单元格拆分成两个，并分别并到上、下两个相邻的单元格中去 5、在WORD编辑文档时，选择某一段文字后，把鼠标指针置于选中文本的任一位置，按[Ctrl]键并按鼠标左键不放，拖到另一位置上才放开鼠标，那么，刚才的操作是： （A）、替换文件（B）、删除文件（C）、移动文本（D）、复制文本 6、在WORD中使用标尺设置“左制表位”的正确操作是： （A）、在标尺的选定位置处单击 （B）、选择要设置制表符位的段落；在水平标尺的左端选择“左对齐制表位”；在标尺的选定位置处单击 （C）、在水平标尺的左端选择“左对齐制表位”，在标尺的选定位置处单击 （D）、在水平标尺的左端选择“左对齐制表位” 7、在Word中，下列关于标尺的叙述中错误的是________。 A)水平标尺的作用是缩进全文或插入点所在的段落、调整页面的左右边距、改变表的宽度、设置制表符的位置等 计算机专业是近年来比较热门的专业，随着本科计算机专业毕业生数量的增多，很多本科毕业生打算考研的比较多，以下是分享的计算机考研学校排名，希望能帮助到大家! 计算机考研学校排名 1、北京大学考研330分 数学自主命题，进复试的60多人，被刷了10个左右，330+的几个基本全留下了，复试率基本1:2，今年360以下的基本都去软院，录取除特殊人物外，基本看排名总排名40开外，专业排名6之外的都很危险，排名之间还要看分数差距 2、清华大学352分(含工程硕士) 清华工程不享受奖学金，不享受国家补助，不享受公费医疗， 工学录了35个，5个去深圳，每年工学收30个左右 3、南京大学341分(不含工程硕士，南大工程的复试线是其工科校线到341之间) 计划招收工学硕士90人，本校和外校推免生一共34人，通过考试招收56人，按照1:2的比例，共有68人进入复试，工学刷下来的可以直接选读工程硕士(南大工程硕士可以评定奖学金的)，无需复试 4、浙江大学考研320分(不含工程硕士) 浙大复试比例:1:5，进入复试240人，录取140+，刷了90人。实际录取线在350分左右，140人中只有30人公费(其中浙大本校免复试占去15个名额)，剩下的大部分交一半学费，少数全交 5、复旦大学325分(不含工程硕士) 工学招80个，已有48名免推生，复旦专硕的复试线是其工科校线310，复旦专硕和清华专硕待遇一样 6、哈尔滨工业大学320分(含工程硕士) 360以上的87个 7、上海交通大学333分(含工程硕士) 工程硕士享受奖学金，享受公费医疗，可参与学校专业奖学金评比 8、中科院计算所338分(含工程硕士，同软件所待遇) 今年扩招了11个工程，计算所的工程与工学硕士待遇没有差别，只是不能直博 全国计算机等级考试二级公共基础知识 考试大纲 一、基本要求 1、掌握算法的基本概念。 2、掌握基本数据结构及其操作。 3、掌握基本排序和查找算法。 4、掌握逐步求精的结构化程序设计方法。 5、掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。 6、掌握数据库的基本知识,了解关系数据库的设计。 二、考试内容 （一）基本数据结构与算法 1、算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2、数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3、线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4、栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5、线性单链表、双向链表与循环链表的结构及其基本 运算。 6、树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7、顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序) （二）程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法,对象,方法,属性及继承与多态性。 （三）软件工程基础 1、软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。 2、结构化分析方法,数据流图,数据字典,软件需求规格说明书。 3、结构化设计方法,总体设计与详细设计。 4、软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。 5、程序的调试,静态调试与动态调试。 （四）数据库设计基础 1、数据库的基本概念:数据库,数据库管理系统,数据库系统。 目录 2014 年东南大学935 计算机专业基础考研真题 (2) 2005 年东南大学935 计算机专业基础考研真题 (4) 2004 年东南大学935 计算机专业基础考研真题 (7) 2014 年东南大学935 计算机专业基础考研真题 2014 年东南大学935 计算机专业基础（回忆版）题量： 40 道选择题，7 道大题。 39.磁盘上有1800 个磁道，每个磁道有120 个分区，每个分区最多2KB，现磁盘5400MB/min 的转速，求最大带宽 A.2 点多MB/S B.好像是9 点多 MB/S C.20.6 MB/S D.20 点多MB/S （记得不是很清楚） 大题 1.死锁的四个条件. 银行家算法 2.PV 同步 3.hash 排序 散列表，求成功和不成功下平均查找长度 4.设计一个判断一维数组中是否有主函数存在。比如说A[]={’a’,’b’,’a’,’c’,’a’,’a’}，A 中’a’有4 个，大于长度的一半，输出存在主函数’a’，B[]={’a’,’b’,’d’,’c’,’e’,’f’}，B 中没有元素的个数大于长度的一半，输出不存在主函数’a’。c/c++语言实现，简单文字说对程序的思路，并求时间复杂度和空间复杂度。 5.cache 地址，偏移量和指令格式综合在一起 6.基址运算 这一个月来睡了不超过150 小时，记忆变得很差，大题怎么也想不起来第一题是什么了，只感觉是很简单的选择都是些基础性的东西，知识点很多，尽量看全 补充： 一、选择包含知识点： 1.给了一个入栈序列，下列是合法出栈序列的是？ 2.下列哪个不是特权指令 3.下列哪个不是算法的重要特性 4.排序（很常规，有关排序有几道选择） 5.一个有7 个数的数列，采用快速排序，至少需要比较多少次？ 6.组成原理有关中断....串行判优平行判优的内容……. 7．四个序列中哪个不是二叉排序树的先序遍历序列 8．选择题哪个是特权指令的题目两个选项B 读时钟指令，C 设置基址寄存器的值 9．流水线加速比 10．图的层次遍历 11．Round Robin 12．进程 状态转换，等点 综合应用题： 操作系统： 1.（1）写出外层页表，页号，页内地址位数； （2）叙述逻辑地址转换为物理地址的过程； 2.（1）回答死锁产生的四个必要条件； （2）写出Need 矩阵 （3）系统是否处于安全状态 3．PV 操作：有两个进程P1，P2，一个容量为n 的缓冲区，P1 向缓冲区放数据，一次放一个，当缓冲区中数据个数大于m（n>m）时，P2 才能从缓冲区取数据，一次取一个。该同步机制用用pv 操作描述 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考研：计算机专业考研方向及各地区院校推荐计算机学科的方向很多，如软件、数据库、网络、硬件、芯片、无线通信和移动智能应用等，多数就业形势都不错，而且毕业生薪资水平经常占据就业榜第一的位置，毕业研究生平均月薪过万。但在当前整体就业形势严峻和就业压力大的情况下，考生在考研前作出适合自己的院校选择也非常重要。下面为大家分析一下计算机专业考研专业分类及几大优势院校。 一、专业分类及介绍 目前我国计算机专业主要分为三大类：计算机基础专业、与理工科交叉的计算机专业、与文科艺术类交叉的计算机专业。 (一)计算机基础专业 推荐院校：北京大学、清华大学、浙江大学、南京大学、上海交通大学、东南大学 (二)与理工科交叉的计算机专业 1、数学与应用数学专业 推荐院校：同济大学、东南大学、中山大学、宁波大学、深圳大学 2、自动化专业 推荐院校：清华大学、东南大学、北京邮电大学、重庆大学 3、信息与计算科学专业 推荐院校：清华大学、南京大学、苏州大学 4、通信工程专业 推荐院校：复旦大学、北京邮电大学、吉林大学、哈尔滨工业大学、南京理工大学 5、电子信息工程专业 推荐院校：浙江大学、清华大学、厦门大学、武汉大学、四川大学、云南大学 (三)与文科艺术类相交叉的计算机专业 在此提醒广大考生，如果选择艺术类院校的上述专业，应有充分的思想准备：报考人数众多而招生人数有限，竞争残酷，门槛很高。 1、计算机美术设计专业 推荐院校：四川美术学院、云南大学、南京艺术学院、重庆师范大学 2、网页设计专业 推荐院校：首都师范大学、中央美术学院 3、影视动画设计专业 推荐院校：北京电影学院、成都大学 4、环境艺术设计专业 推荐院校：浙江工业大学、中国美术学院 全国计算机等级考试二级MS Office高级应用真题题库2 2016年3月 (总分100, 做题时间120分钟) 一、选择题(每小题1分。共20分) 1. 英文缩写CAM的中文意思是（）。 A 计算机辅助设计 B 计算机辅助制造 C 计算机辅助教学 D 计算机辅助管理 该问题分值: 1 答案:B CAM是计算机辅助制造。 2. 若网络的各个节点通过中继器连接成一个闭合环路，则称这种拓扑结构称为（）。 A 总线型拓扑 B 星型拓扑 C 树型拓扑 D 环型拓扑 该问题分值: 1 答案:D 环型拓扑结构是指各个节点通过中继器连接到一个闭合的环路上，环中的数据沿着一个方向传输，由目的节点接收。 3. 有三个关系R、S和T如下： 则由关系R和s得到关系T的操作是（）。 A 自然连接 B 交 C 投影 D 并 该问题分值: 1 答案:A 关系R和关系S有公共域，关系 T是通过公共域的等值进行连接的结果，符合自然连接，选A。 4. 对下列二叉树进行前序遍历的结果是（）。 A DYBEAFCZX B YDEBFZXCA C ABDYECFXZ D ABCDEFXYZ 该问题分值: 1 答案:C 前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作。否则：①访问根结点；②前序遍历左子树；③前序遍历右子树，C正确。 5. 字长是CPU的主要技术性能指标之一，它表示的是（）。 A CPU的计算结果的有效数字长度 B CPU一次能处理二进制数据的位数 C CPU能表示的最大的有效数字位数 D CPU能表示的十进制整数的位数 2018考研计算机学科专业基础综合考试大纲 I考试性质 计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。 II考查目标 计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。III考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 二、答题方式 答题方式为闭卷、笔试。 三、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 四、试卷题型结构 单项选择题80分(40小题，每小题2分) 综合应用题70分 IV考查内容 数据结构 【考查目标】 1.掌握数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 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分） 本科华科电信，12年考上交电子系失败收场，之后找工作到某运营商，在工作期间跨考复旦 大学计算机专业硕士成功录取，初试359，复旦计算机专硕考数学一专业课408 英语二政 治，各科分数分别是111 111 75 62，初试成绩至少是专硕前五，初试和学硕的区别就是英语。 自觉得我的考研路有点特别，但是两次考研的经历有些感悟，希望和大家分享，希望对大家有启发。 一、是否考研 是否决定考研需要根据自己的具体情况，想好自己要走的路。如果是单纯想多学点东西，想进入IT行业，能入行就可以考虑直接工作了，工作中学到实用的东西绝对比读研多。如果要 搞学术，优先考虑出国，其次是国内读研读博。如果是要进入体制内或其他对学历有硬性要求的地方，一些学历可以转化为职称的地方，那就刷学历吧。如果想去大型IT公司又绝对没 实力想在学校继续深造的可以考虑考研。还有学历情结、名校情结等等原因。 我的情况是大四的考研失利导致错失找工作的最佳时期，进入运营商做后台，对工作不满想通过考研换专业换行业，提升自己专业能力的，其实最佳选择或许是本科找份合适的工作。 好了，先思考一下是否要考研，如果你决定考研了再往下看。 二、考研专业 本科电子信息工程跨考计算机。本身对电信的核心专业课就没有感觉。第一次的考研失利及在运营商的工作经历让我对通信失去兴趣，当前互联网行业发展迅速，自身对计算机也比较兴趣，决定考研计算机。 总之，是要根据自己的兴趣和能力等具体情况选择。 PS.个人觉得当前最好的行业是金融，工科跨考金融的同学都令我佩服不已。 三、学硕专硕 国家政策上是希望学硕做科研，专硕搞工程项目，实际中现在学硕和专硕的区别越来越小，实际最大的区别就是“钱”和“时间”！就是专硕学制短、奖学金少。一些学校的某些专业 已经一视同仁了，具体情况看学校的专业。大趋势是学硕和专硕的待遇趋于一致，近些年但是一直在变化。复旦计算机学硕3年，专硕2.5年，专硕奖学金少。考学硕过专硕线科研调剂 到专硕。PS.今年复旦计算机的最高分是直接考专硕的。 大部分现今情况还是，就是专硕学制短、奖学金少。 专硕的学制据我了解2年、2.5年、3年的都有，早毕业早工作，适合想在大学里再学习技能 的。少读的一年、半年很轻松就能赚回奖学金，所以不要太顾虑钱的问题。 如果想搞学术尽量考学硕。想提升项目实践能力的建议报专硕。 专硕当前的难度还比学术略低，但是差距随着社会对专硕的认识加深在逐渐缩小。 如果是想提升实践能力可以考虑直接报考专硕，专硕对发paper没有硬性要求，有更多时间参与到工程项目中。个人觉得理论研究在部分求职及实际工作当中不被重视，当然一些做前沿研究的高校、研究所、研究院则大不一样。 四、考研学校 个人觉得主要考虑1、学校名气2学校地区3专业实力4本科院校（排名不分先后） 计算机考研学校难度排名 计算机专业作为每年研究生入学考试中的热门专业，其报考难度相对较大，但是在不同的高校难度却也有很大的差异，高校间报名录取比甚至有几十个百分点的差距！为帮助广大考生避开竞争激烈的热门高校，结合自身实力、专业排名、高校综合实力排名、最低分数线等因素综合考虑后能够更科学地确定自己所要报考的高校 1、北京大学考研330分 数学自主命题，进复试的60多人，被刷了10个左右，330+的几个基本全留下了，复试率基本1:1.2，今年360以下的基本都去软院，录取除特殊人物外，基本看排名总排名40开外，专业排名6之外的都很危险，排名之间还要看分数差距 2、清华大学352分(含工程硕士) 清华工程不享受奖学金，不享受国家补助，不享受公费医疗，工学录了35个，5个去深圳，每年工学收30个左右。 3、南京大学341分(不含工程硕士，南大工程的复试线是其工科校线到341之间) 计划招收工学硕士90人，本校和外校推免生一共34人，通过考试招收56人，按照1:1.2的比例，共有68人进入复试，工学刷下来的可以直接选读工程硕士(南大工程硕士可以评定奖学金的)，无需复试 4、浙江大学考研320分(不含工程硕士) 浙大复试比例:1:1.5，进入复试240人，录取140+，刷了90人。实际录取线在350分左右，140人中只有30人公费(其中浙大本校免复试占去15个名额)，剩下的大部分交一半学费，少数全交 5、复旦大学325分(不含工程硕士) 工学招80个，已有48名免推生，复旦专硕的复试线是其工科校线310，复旦专硕和清华专硕待遇一样 6、哈尔滨工业大学320分(含工程硕士) 360以上的87个 7、上海交通大学333分(含工程硕士)东南大学计算机专业基础历年考研真题答案汇编附答案
计算机考研学校排名
全国计算机等级考试-一级教程word测试题
计算机专业基础综合考研真题
10年计算机考研真题解析
计算机专业考研院校排名及历年分数线
2011年计算机统考真题+解析
计算机科学与技术专业考研院校排名
计算机等级考试WORD选择题
计算机考研学校排名范文
全国计算机等级考试二级大纲(MS-office)
东南大学935计算机专业基础历年考研真题汇编word版
南京大学计算机考研试题
2018考研：计算机专业考研方向及各地区院校推荐
完整word版,全国计算机等级考试二级MS+Office高级应用真题精彩试题库2+20173月
2018考研计算机学科专业基础408综合考试大纲
天津大学计算机技术专硕考研真题
复旦大学计算机专业考研经验
计算机考研难度排行榜
相关主题
文本预览