算法与数据结构考研试题精析 第4版

    书籍
    计算机书籍
本书收集了历年来国家统考和985、211等重点高校和研究院、所的350多套硕士研究生入学“(算法与)数据结构”考试试卷的2100多道试题。作者按照数据结构课程的知识点对这些题目进行分类。在回顾知识点的基础上，对每一类题目进行分析、归纳答题思路，并给出了参考答案。本书收录的题目具有典型性，充分理解这些题目有助于学生更好地掌握数据结构课程的核心内容，以及应用知识解决实际问题的方法。
本书可以作为高等院校计算机及相关专业学习数据结构课程的参考书，对于报考相关专业硕士研究生的考生也极具价值，同时也适用于讲授该课程的教师以及自修该课程的其他人员。

第4版前言
第3版前言
第2版前言
第1版前言
第一部分　复习纲要
第1章　概论2
第2章　线性表2
第3章　栈和队列3
第4章　串4
第5章　数组和广义表4
第6章　树和二叉树5
第7章　图6
第8章　动态存储管理6
第9章　集合7
第10章　排序8
第11章　文件9
第二部分　试题部分
第1章　概论12
第2章　线性表21
第3章　栈和队列39

　　第4版前言
　　自本书2015年出版第3版以来，又过去了5年。为了紧跟时代的发展，这次我们又推出了第4版。
　　和第3版相比，第4版修订了参考答案，增加了对题目的分析和答案的解释，删除了一些叙述含糊、理解上容易产生歧义的题目，增加了近5年全国硕士研究生入学统考试题和一些重点大学的入学考试试题。再版后的试题按题号计共有2165题，其中选择题627道、判断题323道、填空题365道、应用题474道、算法设计题376道。
　　自2009年起，国家对硕士研究生招生考试的计算机科学与技术学科实行联考（计算机学科专业基础综合试题为一张试卷，其中数据结构占45分、计算机原理占45分、操作系统占35分和计算机网络占25分），至今已经11年。本书包括这11份试卷中数据结构部分的全部试题（共有单项选择109题，综合应用22题）。分析这些试题可以看出：题目强调基本概念和基础知识，突出重点和综合运用，考核范围逐渐扩大，出题更加灵活，综合性更强；本属于计算繁杂的应用题，也出现在一道只有2分的单项选择题中；数据结构与计算机网络结合的题目连年出现，算法设计题的数学基础要求更高，突出了对计算机学科的知识综合应用能力的考核。
　　分析近年来数据结构的考题可以发现，考题重复量很大，有的题型（甚至原题）年年出现。实际上，从20世纪70年代Knuth确定数据结构的课程体系以来，虽然算法的描述经过了类Pascal、类C、C++、Java的变化，但是课程的基本内容并没有变化。几十年前的考题至今仍在使用，全国联考的题目并非都是新题，有的院校每年的考题中也有上年的考题了。所以，本书对于数据结构课程的教学和学生的备考是非常重要的。
　　对于选入的试题，为尊重出题的院校，除极个别情况外，未进行文字改动，因此会出现同一问题有不同描述，以及同一概念有不同翻译的情况，这类情况不影响题目的正确性和理解。另外，本书对叙述不够严谨的题目，包括国家联考的题目（例如判定树的画法、B树的高度等），给予了较详细的分析，目的在于让读者了解同一问题的不同描述，并深刻理解问题的实质。
　　对于如何使用本书，编者建议读者首先阅读前三版的前言，尤其是第3版前言中有具体的进度要求。大四考研学期除复习、巩固基础知识题外，参加全国联考的考生要熟练掌握联考的所有试题，报考某院校的考生要完成所考院校近几年的试题。
　　虽然本书经过八个月的认真修订，但是限于能力且题量较大，仍可能会有缺点和错误，恳请读者批评指正，以不断完善本书，给读者奉献精品。编者的联系邮箱是skcnmu@163.com。
　　第4版新增一位编者冯广慧，她在试题搜集、解答和校对中做了大量工作。还有许多人对本书的再版做出了贡献，编者表示衷心的感谢：感谢家人多年来对工作的理解和支持；感谢周世平老师给予的业务帮助；感谢梁艳春老师、潘庆先老师、蔡新海老师、高慧老师和许多学生提供的试题；感谢机械工业出版社温莉芳女士、朱劼女士多年来的支持和帮助，她们对本书的修订提了许多具体建议；感谢迟振春编辑认真仔细的工作。
　　编者
　　2019年12月24日于烟台大学
　　第3版前言
　　自本书2007年再版以来，已过去近8年。为适应教学和硕士研究生入学考试的变化，编者决定对本书再版。
　　这次再版做了如下变动：加入了2009～2015年的全国统考试题，并在附录中增加了2016年的统考试题；删除了一些已不具典型性的试题，强化了985和211大学以及科研院所的试题；加入了一些重点大学近年来的考研试题；删除了绝大部分以Pascal语言描述的试题，保留了个别以Pascal定义数据结构的试题，但用C给出了解答；按授课常见的知识点的顺序对试题进行了编排，尽量把相似内容放在一起；增加了对选择题和判断题答案的分析；修正了答案；考虑到算法的多样性和篇幅限制，只对少数题给出完整算法，多数题只给出算法分析提示和核心语句段。像过去的版本一样，对所有试题都标明出处。个别试题只标出学校和年份，没有具体题号和分数。全国试题放在相关章的前面。再版后的试题按题号计是2031题，其中选择题553道、判断题313道、填空题350道、应用题453道、算法设计题362道。
　　由于本书引用了各校真实试题，为尊重原题，除极个别情况外，对试题中的术语和变量未作校正。例如，链表指针域next和link，变量n和N，生成树和跨接树，遍历和周游，等等。还应指出，有个别试题（包括全国统考试题）在叙述上不够严谨，编者给予了说明。
　　编者对全国试题进行了深入分析。由于四门课程一张试卷，数据结构占45分，很难涵盖数据结构的各章。选择题10道，占20分（有6年是11道，占22分）；应用题2道，占25分，其中算法题至多占15分。试题在各章的分布详见附录A。
　　数据结构作为一门课程，几十年来一直在发展中。描述算法的语言一直在变化，从Knuth的算法描述语言，到Pascal语言，再到类C语言，近年又出现了用C++和Java语言描述的教材。编者认为，数据结构的基础知识没有太大变化，教材涵盖的内容基本没有变化，基本算法没有变化。对具体问题用哪种语言描述，只是描述工具不同，解决问题的算法思想是一样的。研究7年来国家统考、67所高等院校和研究院所的340多套试题，编者发现试题重复量很大，20年前的试题至今仍在重复使用。很多国家统考试题都可以在本书中找到原题或类似题。编者强调掌握数据结构的基础知识和一些重要的算法，这对学好数据结构课程和取得更好的考研成绩是非常重要的。
　　对于学生如何使用本书，我们给出如下建议。在学习数据结构课程时，要同步完成选择题、判断题和应用题，部分完成填空题和算法设计题。考研的学生，要在本课程结束后的假期做完算法设计题。即使写不完全部代码，至少也要把各题的算法思想搞清楚。要特别重视算法填空题中的填空，这部分内容对学生的算法设计训练很有益处。
　　2009年，国家对硕士研究生入学计算机学科专业基础综合进行全国统考，后来，国家允许一些院校对硕士研究生入学考试的计算机专业课实行自主命题。某些学校将150分的专业考试都给了数据结构，足见数据结构课程的重要性。鉴于此，本书选题基本涵盖了数据结构课程的全部内容，除了国家统考大纲规定的内容外，还包含目前国家统考大纲中不包括的串、数组和广义表、动态存储管理、外部排序和文件等内容。学生在备考时，要特别注意所考学校对数据结构内容方面的要求。
　　感谢读者多年来对本书的肯定，这是编者再版本书的动力；感谢机械工业出版社华章公司的温莉芳女士和朱劼女士，她们对本书试题的选择提出了有益的建议和具体要求；感谢迟振春女士和朱秀英女士的辛勤编辑工作。

　　“数据结构”是计算机及相关专业的核心课程之一，也是后续专业课程的基础。2009年开始的全国硕士研究生入学统一考试计算机学科专业综合试题中，数据结构方面的试题占据重要地位。本书基于作者多年来教授数据结构课程的经验，以及对知名高校、科研院所招收硕士研究生时的数据结构试题的跟踪和分析，从数据结构课程内容以及如何应用数据结构的知识解决实际问题的角度编写而成，是学习数据结构课程和准备研究生入学考试的极佳参考。
　　本书特色
　　在内容上，对数据结构课程的主要知识点进行了梳理，再按照知识点对试题进行分类讲解，使读者灵活运用知识点并举一反三。
　　题量大、题型多，全书的题目共计2100余道，包括选择题、填空题、应用题、算法设计题等，通过不同类型的练习使读者巩固所学知识。
　　本书题目来自全国硕士研究生入学统一考试的真题、国内重点高校及科研院所硕士生考试真题，并对这些题目进行了精析，便于学生有针对性地复习和参考。
　　每个问题均给出了参考答案或解题思路指导，便于读者快捷、高效地学习。