计算机考研——机试指南.pdf

王道考研系列 计算机考研机试指南 王道论坛 组编 内 容 简 介 目前已有越来越多的高校采用上机考试的形式来考查学生的动手编程能力，对于以应试为主的大学教学模式，上机往往是学生的薄弱环节。本书由浅入深、从简到难讲解了机试的相关考点，并精选名校的复试上机真题作为例题和习题，以给大家提供最可靠的练习指导。书中的所有机试试题在九度 OJ（）均有收录，建议同学们在阅读本书时，结合上机练习，自己动手才是王道！本书不仅可以作为研究生入学考试的复试复习用书，也可以作为计算机及相关专业的学生练习上机能力的指导用书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 计算机考研:机试指南/王道论坛组编.北京：电子工业出版社，2014.1（王道考研系列）ISBN 978-7-121-22177-4 I计 II王 III电子计算机研究生入学考试自学参考资料 IVTP3 中国版本图书馆 CIP 数据核字（2013）第 302635 号 策划编辑：谭海平 责任编辑：郝黎明 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编 100036 开 本：7871 092 1/16 印张：12.75 字数：326.4 千字 印 次：2014 年 1 月第 1 次印刷 定 价：36.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。前 言 无论结果如何，总算坚持到了最后。初试考完了，是不是应该好好放松放松？是不是初试考得好，录取就肯定没有问题了？对不起，这个不是计算机专业研究生考试的规则。目前已有越来越多的高校采用上机考试的形式来考查学生的实际动手编程能力，并且机试在复试中所占的比例非常高，甚至很多高校规定复试成绩不及格者，一律不得录取。目前国内高校开展ACM 教学的高校非常少，因此提早开始准备和练习，对于一个完全没有接触过提早开始准备和练习，对于一个完全没有接触过ACM 的计算机考研人来说，是必须的！的计算机考研人来说，是必须的！为方便各位道友练习机试，我们编写了本书，搭建了九度 OJ（），本书中的题均可以在九度 OJ 上提交，并给出了相应的提交网址，提交时可以直接使用王道论坛的账号进行登录。如果在使用过程中遇到问题，欢迎到复试机试讨论专区发贴提出。九度 OJ 目前已收录了我们能够收集到的各高校上机复试真题，也欢迎大家向我们提供各高校上机真题，具体请通过邮件联系浩帆（E-mail：）。考研其实没有什么诀窍，就是每天比别人早起一点，晚睡一点，比别人早准备一点，勤奋一点。我坚信一个写不出合格代码的计算机专业的学生，即便考上了研究生，无非也只是给未来失业判个缓期执行而已。王道是道友们考研路上值得信任的好伙伴，五年多来他陪伴了近四十万的计算机考研人，不离不弃。王道尊重的不是考研这个行当，而是王道上这群执着的道友的梦想，看着你们圆梦，我们内心充满了成就感。道友们，要忠实于自己心底的梦想，勇敢地坚持下去，而当下，请开始准备复试吧，熬过这两个月，一切就都好了。目 录 第 1 章 从零开始 1 一、机试的意义 1 二、机试的形式 1 三、评判结果 3 四、复杂度的估计 4 五、OJ 的使用 5 总结 6 第 2 章 经典入门 7 一、排序 7 二、日期类问题 14 三、Hash 的应用 21 四、排版题 25 五、查找 30 六、贪心算法 36 总结 41 第 3 章 数据结构 42 一、栈的应用 42 二、哈夫曼树 48 三、二叉树 50 四、二叉排序树 55 总结 61 第 4 章 数学问题 62 一、%运算符 62 二、数位拆解 64 三、进制转换 67 四、最大公约数（GCD）71 五、最小公倍数（LCM）74 六、素数筛法 75 七、分解素因数 79 八、二分求幂 85 VI 九、高精度整数 89 总结 98 第 5 章 图论 99 一、预备知识 99 二、并查集 103 三、最小生成树（MST）110 四、最短路径116 五、拓扑排序 126 总结 130 第 6 章 搜索 131 一、枚举 131 二、广度优先搜索（BFS）133 三、递归 143 四、递归的应用 145 五、深度优先搜索（DFS）151 总结 155 第 7 章 动态规划 156 一、递推求解 156 二、最长递增子序列（LIS）159 三、最长公共子序列（LCS）162 四、状态与状态转移方程 164 五、动态规划问题分析举例 165 六、背包 171 总结 181 第 8 章 其他技巧 182 一、标准模板库（STL）182 二、滚动数组 189 三、调试技巧 191 四、补充技巧 192 五、最后的提醒 195 总结 195 第 1 章 从零开始 一、机试的意义 众所周知，机试是计算机考研复试中非常重要的一个环节。在越来越注重实践动手能力的今天，有越来越多的知名高校在计算机研究生入学考试当中采用了机试的考查形式，通过这种形式来考查学生的分析问题并利用计算机程序解决问题的能力。通过机试，可以考查一个考生从实际问题当中抽象得出数学模型的能力，利用所学的计算机专业知识对该模型进行分析求解的能力，以及利用计算机编程语言，结合数据结构和算法真正解决该实际问题的能力。所以，大家在准备机试的过程中要特别注意以下几个方面：1如何将一个实际问题抽象成数学问题。例如，将高速公路网抽象成带权图，这就是一种简单的、直接的抽象。2如何将我们所学的计算机专业知识，运用到解决抽象出来的数学模型上去。这就要求我们在脑子里事先熟知一些常用的数据结构和算法，再结合模型求解的要求，很快地选择合适的编程思想来完成算法的设计。甚至可以利用一些经典算法特征，加入一些自己的优化，使得编写的程序更优雅、更高效（当然这是建立在充分理解经典算法的基础上）。3 如何将我们为解决该数学模型所设计的算法编写成一个能被计算机真正执行的计算机程序。笔者认为，关于这个能力的定义有三个层次：会编写（默写）一些经典算法的程序代码。能够将自己的想法或设计的算法转换为程序代码。能够使得自己编写的程序在大量的、多种多样的、极限的测试数据面前依旧正常完成功能（程序的健壮性）。我们在准备机试的训练过程中，就要依次经历这三个层次，从而最后能够在实际考试当中取得理想的成绩。本教程从分析经典机试真题出发，它们均为近几年频繁被考查的数据结构和算法，利用 C/C+语言进行讲解，并加以一些相关知识的扩展，希望在读者准备计算机考研机试的过程中充当指引者的角色。同时，由于笔者自身能力的限制以及编写时间的不足，教程中难免存在一些疏漏和错误，恳请读者指正。二、机试的形式 绝大部分机试所采用的形式，归结起来可以概括为：得到题目后，在计算机上完成作答，由计算机评判并实时告知结果的考试过程。2 机试考试中的问题往往由五部分组成。首先是问题描述，描述该问题的题面，题面或直接告知考生所要解决的数学问题、或给出一个生活中的实际案例，以待考生自己从中抽象出所要解决的数学模型。第二是输入格式，约定计算机将要给出的输入数据是以怎样的顺序和格式向程序输入的，更重要的是它将给出输入数据中各个数据的数据范围，我们通过这些给出的数据范围确定数据的规模，为我们设计算法提供重要依据。第三是输出格式，明确考生将要编写的程序将以怎样的顺序和格式输出题面所要求的答案。第四第五部分即输入、输出数据举例（Sample）。好的 Sample 不仅能为考生提供一组简单的测试用例，同时也能明确题意，为题面描述不清或有歧义的地方做适当的补充。另外也要特别注意，题目中给定的两个重要参数：时间限制。空间限制。这两个重要的参数限定了考生提交的程序在输出答案之前所能耗费的时间和空间。我们来看一个典型的题目描述，从而了解机试题的问题形式。例 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）的含义，特殊判题常被应用在可能存在多个符合条件的答案的情况下，若评判系统采用了特殊判题，那么系统只要求输出任何一组解即可；若系统对该题并没有采用特殊判题，那么你必须严格按照题目中对输出的限定输出对应的答案（如输出字典序最小的解）。得到题目后，考生在计算机上立即编写程序，确认无误后，将该程序源代码提交给评判系统。评判系统将考生提交的源代码编译后，将后台预先存储的输入测试数据输入考生程序，并将该程序输出的数据与预先存储在评判系统上的“答案”进行比对得出结果。第 1 章 从零开始 3 评判系统评判考生程序后，实时地将评判结果返回到考生界面，考生可以根据该结果了解自己的程序是否被评判系统判为正确，从而根据不同的结果继续完成考试。三、评判结果 本节将对评判系统评判考生提交程序后返回的结果做详细的说明，并且针对不同的返回结果，对可能出现错误的地方做出初步的界定。Accepted（答案正确）：（答案正确）：你的程序对所有的测试数据都输出了正确的答案，你已经得到了该题的所有分数，恭喜。Wrong Answer（答案错误）：（答案错误）：评判系统测试到你的程序对若干组（或者全部）测试数据没有输出正确的结果。出现该种错误后，一般有两种解决方向：如果对设计的算法正确性有较大的把握，那么你可以重点考虑代码健壮性，即是否存在某些特殊数据使程序出现错误，比如边界数据，比如程序中变量出现溢出。另一种方向，即怀疑算法本身的正确性，那么你就需要重新考虑你的算法设计了。Presentation Error（格式错误）：（格式错误）：评判系统认为你的程序输出“好像”是正确的，只是没有严格按照题目当中输出所要求的输出格式来输出你的答案，例如你忽略了题目要求在每组输出后再输出一个空行。出现这种错误，往往预示着你离完全正确已经不远了，出现错误似乎只是因为多输出了一些空格、换行之类的多余字符而已。但这不是绝对的，假如在排版题（后文会有介绍）中出现格式错误，那么有可能你离正确的答案仍然有一定的距离。Time Limit Exceeded（超出时间限制）：（超出时间限制）：你的程序在输出所有需要输出的答案之前已经超过了题目中所规定的时间。若这种结果出现在你的评判结果里，依然有两种方向可供参考：假如你确定算法时间复杂度能够符合题目的要求，那么依旧可以检查是否程序可能在某种情况下出现死循环，是否有边界数据可能会让你的代码不按照预想的工作，从而使程序不能正常的结束。你设计的算法时间复杂度是否已经高于题目对复杂度的要求，如果是这样，那么你需要重新设计更加高效的算法或者对你现行的算法进行一定的优化。Runtime Error（运行时错误）：（运行时错误）：你的程序在计算答案的过程中由于出现了某种致命的原因异常终止。你可以考虑以下几个要点来排除该错误：程序是否访问了不该访问的内存地址，比如访问数组下标越界。程序是否出现了除以整数 0，从而使程序异常。程序是否调用了评判系统禁止调用的函数。程序是否会出现因为递归过深或其他原因造成的栈溢出。Compile Error（编译错误）：（编译错误）：你提交的程序并没有通过评判系统的编译，可根据更详细的编译信息修改你的程序。4 Memory Limit Exceeded（使用内存超出限制）：（使用内存超出限制）：你提交的程序在运行输出所有的答案之前所调用的内存已经超过了题目中所限定的内存限制。造成这种错误的原因主要有两个方面：你的程序申请过多的内存来完成所要