logo资料库

2013年王道论坛计算机考研机试指南pdf.pdf

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：3.27M 资料格式：pdf 举报 版权申诉
第1页 / 共229页
第2页 / 共229页
第3页 / 共229页
第4页 / 共229页
第5页 / 共229页
第6页 / 共229页
第7页 / 共229页
第8页 / 共229页
资料共229页，剩余部分请下载后查看
    / www.cskaoyan.com + 2013.01.06 ) _ F ’ A ) _ F ’ A / A u 1 k 5 - Ł A ' f
    写在前面的话 各位王道的小崽子们，今天你们考完初试了，感觉解放了吧？轻松了吧？无 论结果如何，总算坚持到了最后。但是，其实你的考研生活只刚刚走出了第一步， 接下来会有初试成绩出来前的煎熬、分数线出来的煎熬、准备复试以及复试的煎 熬以及录取结果出来前的煎熬，这些都远远比初试更折磨人，未来的两个月你会 感觉到王道没有吓唬你们。 王道是个好姑娘，四年多的时光里陪伴了接近二十万计算机考研人，不离 不弃。今年不小心又压中一道算法题，说实话，王道的书里有那么多的题，知识 点又只有那么多，总能瞎猫碰见死耗子吧？王道尊重的不是考研这个行业，而是 你们这群执着的小崽子们的梦想！看着你们圆梦，我们内心充满了成就感。 初试考完了，是不是应该好好放松放松？是不是初试考得好，录取就肯定没 有问题了？对不起，这个不是计算机专业研究生考试的规则。目前已经有越来越 多的高校采用上机考试的形式来考察考生的实际动手编程能力，并且机试在复试 中所占的比例非常高，并且很多高校规定复试成绩不及格者，一律不得录取。目 前国内高校开展 ACM 教学的高校非常少，而 ACM 是目前所有高校机试所采取 的唯一形式，因此提早开始准备和练习，对于一个完全没有接触过 ACM 的计算 机考研人来说，是必须的！ 为了方便各位道友练习机试，我们编写了本书，搭建了九度Online Judge （http://ac.jobdu.com），并收集了全国各大高校的复试上机真题，希望能给大家 复试上机考试提供强有力的支持。你可以直接使用王道论坛的帐号进行登录。如 果您在使用过程中遇到问题，欢迎你到复试机试讨论专区发贴提出。目前已经收 录了我们能够收集到的各高校上机复试真题，欢迎大家继续向我们提供各高校上 机真题，具体请站内信或者电子邮件联系浩帆（Email:qihu#zju.edu.cn）。此外， 华科的上机题我们经过了变型，将其中一些便于修改成OJ判题的题目收录进了 我们的OJ。 考研其实没有什么诀窍，就是每天比别人早起一点，晚睡一点，比别人早准 备一点，勤奋一点。考研离我已经很远了，同时我也坚信一个写不出合格代码的 计算机专业的学生，即使考上了研究生，无非也只是给未来失业判个缓期执行而 已。 小崽子们，要忠实于自己心底的梦想，勇敢地坚持下去，而当下，请开始 准备复试吧，熬过这两个月，一切就都好了。
    一 机试的意义 第1章 从零开始 众所周知，机试是计算机考研当中非常重要的一个环节。在越来越注重实践 动手能力的今天，越来越多的知名高校在计算机研究生招生考试当中采用了机试 的形式，通过这种考试手段来考察考生分析问题并利用计算机程序解决问题的能 力。通过机试，可以考察一个考生从实际问题当中抽象得出数学模型的能力，利 用所学的计算机专业知识对该模型进行分析求解的能力，以及利用计算机编程语 言，结合数据结构和算法真正解决该实际问题的能力。 所以，我们在准备机试的过程中要特别注意以下几个方面： 1、如何将一个实际问题抽象成数学问题。例如将高速公路网抽象成带权图， 这就是一种简单的、直接的抽象。 2、如何将我们所学的计算机专业知识运用到解决抽象出来的数学模型上去。 这就要求我们在脑子里事先熟知一些常用的数据结构和算法，再结合模型求解的 要求，很快地选择合适的编程思想来完成算法的设计。甚至可以利用一些经典算 法特征，加入一些自己的优化，使得编写的程序更优雅、更高效（当然这是建立 在充分理解经典算法的基础上）。 3、如何将我们为解决该数学模型所设计的算法编写成一个能被计算机真正 执行的计算机程序。我们认为，关于这个能力的定义有三个层次：1）会编写（默 写）一些经典算法的程序代码。2）能够将自己的想法或设计的算法转换为程序 代码。3）能够使得自己编写的程序在大量的、多种多样的、极限的测试数据面 前依旧正常完成功能（程序的健壮性）。我们在准备机试的训练过程中，就要依 次经历这三个层次，从而最后能够在实际考试当中取得理想的成绩。 本教程从分析经典机试真题出发，引入近几年频繁被考察的数据结构和算 法，利用 C/C++语言讲解例题，并加以一些相关知识的扩展，希望在读者准备计 算机考研机试的过程中充当指引者的角色。同时，由于笔者自身实力的限制以及 编写时间的不足，教程中难免存在一些疏漏和错误，也欢迎读者提出、指正。 二 机试的形式 绝大部分机试所采用的形式，归结起来可以概括为：得到题目后，在计算机 上完成作答，由计算机评判并实时告知结果的考试过程。
    机试考试中的问题往往有五部分组成。首先是问题描述，问题描述描述该问 题的题面，题面或直接告知考生所要解决的数学问题或给出一个生活中的实际案 例，以待考生自己从中抽象出所要解决的数学模型。第二是输入格式，约定计算 机将要给出的输入数据是以怎样的顺序和格式向程序输入的，更重要的是它将给 出输入数据中各个数据的数据范围，我们通过这些给出的数据范围确定数据的规 模，为我们设计算法提供重要依据。第三是输出格式，明确考生将要编写的程序 将以怎样的顺序和格式向输出输出题面所要求的答案。第四第五部分即输入、输 出数据举例（Sample）。好的 Sample 不仅能为考生提供一组简单的测试用例，同 时也能明确题意，为题面描述不清或有歧义的地方做适当的补充。 另外我们也要特别注意，题目中给定的两个重要参数：1、时间限制。2、空 间限制。这两个重要的参数限定了考生提交的程序在输出答案之前所能耗费的时 间和空间。 我们来看一个典型的题目描述，从而了解机试题的问题形式。 例 1.1 计算 A+B （九度 OJ 题号：1000） 时间限制：1 秒 内存限制：32 兆 特殊判题：否 题目描述： 求整数 a，b 的和。 输入： 测试案例有多行，每行为 a，b 的值，a，b 为 int 范围。 输出： 输出多行，对应 a+b 的结果。 样例输入： 1 2 4 5 6 9 样例输出： 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.1 所示，该题给予我们的程序 1 秒的运行时限，这也是最常见的时间 限制（或最常见的时间限制数量级）。对于该时限，通常，我们所设计的算法复
    杂度不能超过百万级别，即不能超过一千万。即若算法的时间复杂度是 O(n^2)， 则该 n（往往在题目中会给出数据范围）不应大于 3000，否则将会达到我们所说 的千万数量级复杂度，从而程序运行时间超出题目中给出的用时限定。举例来说， 我们不能在 1 秒时限的题目当中对 10000 个整数进行冒泡排序，而必须使用快速 排序等时间复杂度为 O(nlogn)的排序算法，否则程序很可能将会得到运行时间超 出限制的评判结果。因此你可以对你的程序在最坏情况下的复杂度进行一个估 算，假如确定其在百万数量级之内，那么你的程序一般是不会超出时间限制的。 对于其它时间限制的情况，可以参考 1 秒时限对时间复杂度的要求，做出一定的 估计，从而保证自己的程序运行所需的时间不会超过题目中对运行时间的限制。 我们同样可以知道，例 1.1 中限定的内存空间为 32 兆，即你的程序在评测 系统中运行时，不得使用超过 32 兆大小的内存。空间限定则比较好处理，你可 以简单的计算你所申请的内存空间的大小（例如我们可以轻易的计算 int mat[300][300]所占用的内存大小）。只要该大小没有超过或过分接近空间限定(运 行时需要一些额外的空间消耗)，那么你的程序应当是符合空间限制条件的。现 如今的机试题，一般不会对空间做过多的限制，大多数情况只对时间做出明确的 要求，所以考题在空间上将会尽量满足考生程序的需要。正因为如此，我们在很 多情况下都应该有“空间换时间”的思想。 五 OJ的使用 我们该去何处开始我们的机试训练和模拟考试呢？可能大部分人已经听说 Judge ） ， 例 如HDOJ 过 在 线 评 判 系 统 （Online （http://acm.hdu.edu.cn/ ）,POJ(http://poj.org/ )。但是这些OJ都是为ACM/ICPC训练而 设计的，虽然形式与机试大同小异但是难度却有较大差别，普通的考生在其中训 练不仅打击了信心，也在一定程度上浪费了时间。因此，推荐专门为我们计算机 考研机试所设计的九度OJ（http://ac.jobdu.com/ ），它收录了近三百道各大高校近几 年来的机试真题，真正为我们准备机试提供了极大的便利。
    我们在它的首页上可以看到九度 OJ 所包含的各种功能。 首先，我们需要点击“注册”按钮，为自己注册一个账号，有了该账号你就 能在九度 OJ 上进行日常练习，同样也有资格参加九度 OJ 举行的各类比赛和模 拟考试。 现假设我们已经有了一个账号，并且想要开始在线练习。那么，可以在页面 左边的导航栏找到在线练习，我们可以选择题目汇总来查看九度 OJ 收录的所有 在线练习题，或者点击考研机试题集来查看九度为各位考生收录的近几年各大高 校机试真题。例如我们选择题目汇总中的题号为 1000 的问题，例 1.1 中的例子 便出现在页面当中。当用户完成作答以后，可以在页面左侧点击“提交答案”按 钮，将源代码提交给九度在线评测系统，提交完成后，系统会自动跳转到评测状 态页面，通过查看你刚才提交的源代码的评测状态，你就可以知道你是否通过了 该题，从而达到锻炼自我的目的。在本文中，凡是涉及九度 OJ 上收录的例题， 本书会明确该题的题号。 同样的，九度 OJ 也经常为广大考生提供在线模拟考试训练。我们可以点击 “比赛及考试”按钮，来查看过往的比赛以及近期的比赛安排，从而有选择的参 加在线比赛，考察自己的训练质量，为日后进一步训练做出导向 总结 本节主要介绍机试的意义、形式，以及机试题的形式和考察的方法，并在最
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料