算法与数据结构考研试题精析(第3版)
更多详情
内容简介:本书收集了国家统考（2009～2015年）、985和211重点高校以及科学院、所340多套硕士研究生入学“(算法与)数据结构”考试试卷的2000多道试题，并给出了参考答案和分析。
本书可以作为高等院校计算机及相关专业学生学习数据结构课程的参考书，对于报考相关专业硕士研究生的读者也极具价值，同时适用于讲授该课程的教师以及自修该课程的其他人员。
目录:第3版前言
第2版前言
第1版前言
第一部分复习纲要
第1章概论2
第2章线性表2
第3章栈和队列3
第4章串4
第5章 数组和广义表4
第6章 树和二叉树5
第7章图6
第8章 动态存储管理7
第9章集合7
第10章 排序8
第11章 文件9
第二部分试题部分
第1章 概论12
第2章 线性表21
第3章 栈和队列39
第4章串54
第5章 数组和广义表62
第6章 树和二叉树78
第7章 图119
第8章 动态存储管理150
第9章 集合152
第10章 排序183
第11章 文件210
第三部分参考答案
第1章 概论214
第2章 线性表219
第3章 栈和队列231
第4章 串246
第5章 数组和广义表254
第6章 树和二叉树269
第7章 图308
第8章 动态存储管理333
第9章集合336
第10章 排序365
第11章 文件390
附录A 2009～2015年全国硕士研究生
入学计算机学科专业基础综合
试题在教材各章中的分布394
附录B本书所选试题在教材各章中的
分布395
参考文献396
前言:第3版前言
本书自2007年再版以来，已过去近8年。为适应教学和硕士研究生入学考试的变化，编者决定对本书再版。
这次再版做了如下变动：加入了2009～2015年的全国统考试题；删除了一些已不具典型性的试题，强化了985和211大学以及科学院、所的试题；加入了一些重点大学近年来的考研试题；删除了绝大部分以语言描述的试题，保留了个别以定义数据结构的试题，但用C给出了解答；按授课常见的知识点的顺序对试题进行了编排，尽量把相似内容放在一起；增加了对选择题和判断题答案的分析；修正了答案；考虑到算法的多样性和篇幅限制，只对少数题给出完整算法，多数题只给出算法分析提示和核心语句段。像过去的版本一样，对所有试题都标明出处。个别试题只标出学校和年份，没有具体题号和分数。全国试题放在相关章的前面。再版后的试题按题号计是2031题，其中选择题553道、判断题313道、填空题350道、应用题453道、算法设计题362道。
由于本书引用了各校真实试题，为尊重原题，除极个别情况外，对试题中的术语和变量未作校正。例如，链表指针域next和link，变量n和N，生成树和跨接树，遍历和周游，等等。还应指出，有个别试题（包括全国统考试题）在叙述上不够严格，编者给予了说明。
编者对全国试题进行了深入分析。由于四门课程一张试卷，数据结构占45分，很难涵盖数据结构的各章。选择题10道，占20分（有6年是11道，占22分）；应用题2道，占25分，其中算法题至多占15分。试题在各章的分布详见附录A。
数据结构作为一门课程，几十年来一直在发展中。描述算法的语言一直在变化，从Knuth的算法描述语言，到语言，再到类C语言，近年又出现了用C++和Java语言描述的教材。编者认为，数据结构的基础知识没有太大变化，教材涵盖的内容基本没有变化，基本算法没有变化。对具体问题用哪种语言描述，只是描述工具不同，解决问题的算法思想是一样的。研究7年来国家统考、67所高等院校和研究院、所的340多套试题，编者发现试题重复量很大，20年前的试题至今仍在重复使用。很多国家统考试题都可以在本书中找到原题或类似题。编者强调掌握数据结构的基础知识和一些重要的算法，这对学好数据结构课程和取得更好的考研成绩是非常重要的。
对于学生如何使用本书，我们给出如下建议。在学习数据结构课程时，要同步完成选择题、判断题和应用题，部分完成填空题和算法设计题。考研的学生，要在本课程结束后的假期做完算法设计题。即使写不完全部代码，至少要把各题的算法思想搞清楚。要特别重视算法填空题中的填空，这部分内容对学生的算法设计训练很有益处。
2009年，国家对硕士研究生入学计算机学科专业基础综合进行全国统考，后来，国家允许一些院校对硕士研究生入学考试的计算机专业课实行自主命题。某些学校将150分的专业考试都给了数据结构，足见数据结构课程的重要性。鉴于此，本书选题基本涵盖了数据结构课程的全部内容，除了国家统考大纲规定的内容外，还包含目前国家统考大纲中不包括的串、数组和广义表、动态存储管理、外部排序和文件等内容。学生在备考时，要特别注意所考学校对数据结构内容方面的要求。
感谢读者多年来对本书的肯定，这是编者再版本书的动力；的温莉芳女士和朱劼女士，她们对本书试题的选择提出了有益的建议和具体要求；感谢迟振春女士和朱秀英女士的辛勤编辑工作。
本书自出版以来，深受读者喜爱，被评为“2008年度畅销榜TOP50”，成为众多考研读者的必备参考书。编者虽已尽最大努力，但是书中难免还会有缺点和错误数据结构试题及答案，恳请读者批评指正（陈守孔邮箱：）。
编 者
2015年1月于珠海
第2版前言
自《算法与数据结构考研试题精析》第1版出版以来，得到了读者的好评。为了反映近几年考研试题的变化，更好地为读者服务，编者对本书进行了全面修订。
首先是对试题进行了增删，删除了400多道试题，替换了200多道试题，按编号计算再版试题共1659题，其中算法设计327题。不再设立“类似本题的叙述”这部分内容，每题都是单独编号。对参考答案进行了审核，尽量做到答案准确、简练。
在准备再版的资料时，编者再次印证了“数据结构的考研试题重复量很大”的结论。在收集的近几年的试题中，绝大部分试题都可在本书第1版中找到，尤其是基础知识题，有些试题的叙述完全一样。由此可以看出，弄懂了本书的试题，无疑将对考研有很大帮助。
通过整理这几年的试题，编者还发现，几乎所有院校都突出了对基础知识的考查。本书中各章的第一到第四部分就属于基础知识。过去，个别院校的试题过于侧重算法设计，而没有基本概念和基本知识。现在大多数院校的硕士研究生考试将专业课整合为一张试卷（占150分）（少数院校仍单独考核数据结构），其中包括两门课程或三门课程的内容。数据结构所占的分数少则50分，多则90分数据结构试题及答案 算法与数据结构考研试题精析(第3版)，并且基础知识占多数，一道算法设计题占20分以上的现象已很少见。所以，编者希望读者，特别是考研的学生，应该加强基础知识的学习。
为了节省篇幅，避免在每道试题解答中重复定义所用数据结构，在本书附录中将给出所用的数据结构，试题解答中将直接使用。
编者欣喜获悉，许多教师将本书作为教学参考书和考试的题库，考研学生通过学习本书大大提高了考研的成绩，我们期望本书在教学中发挥更大作用。
尽管我们作了很大努力，但由于水平有限，书中难免会有缺点错误，恳请读者批评指正。
编 者
2007年3月
第1版前言
“算法与数据结构”课程是高等学校计算机科学与技术专业的一门重要的综合专业基础课，近年来也成为非计算机专业的必修课或选修课。在以往的硕士研究生入学考试中，该课程是计算机类专业的必考科目，也是相关专业的考试科目。
编者多年来在大学讲授“算法与数据结构”课程。在教学中感到，学生理解课程的概念和书本知识并不困难，一旦涉及解决具体问题，特别是编制算法，往往无从着手。为了加强学生对本课程基本概念和基础知识的理解，特别是加强对编写算法的训练，我们编写了本书。
本书从编排上分三部分。第一部分简要复习数据结构各章的重点，第二部分是编者收集的自1992年以来国内68所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1800多道试题，第三部分给出了参考答案和分析。
本书的各章名称与《算法与数据结构（C语言版）》教材相同。每章分选择题、判断题、填空题、应用题和算法设计题五部分。前四类题属于基础知识。选择题多是单选，也有少数是多选，编者直接给出参考答案；判断题是判断对错，除给出参考答案外，还对个别题给予了解释；填空题有概念填空、计算填空，值得注意的是有些院校的算法（程序）填空，即填上几个关键语句，使之成为完整算法（程序），这类题要求较高；应用题有的回答基本概念和基础知识，较多的是手工模拟算法，这部分占的比例较大；算法设计是本书重点，占的篇幅最大，除比较简单的题外，多数题都按题目分析、算法设计、算法讨论三部分展开。算法设计中除题目要求必须用语言描述的外，一律用类C语言描述。算法描述中涉及的类型定义和数据结构基本取自本书的配套教材《算法与数据结构（C语言版）》，为节省篇幅，本书不再重新定义而直接使用。
试题的选取原则是：覆盖教材各章节，兼顾重点章节；主要选名牌院校的考题；同类型试题解答一个，列出类似试题，多数未作解答。列出类似题的目的之一，是引起学生对该类题的重视，考题重复率高也从侧面说明了该类题的重要性。由于本书收集的是全国各高校和科学院、所的试题，加之各校教材不同，所以在题目的叙述上有很大差异。甚至所用名词、概念也不相同。语言描述上有语言、类C语言、框图和伪码等，叙述及算法描述中的大小写不是很统一。我们尽量尊重原题，为保持本书风格大体一致，对部分术语进行了统一。另外，在每道题后都注明了题目出处，例如【清华大学 1997 三（10分）】的含义是本题选自清华大学1997年硕士研究生数据结构试题第三题，试题分数是10分，有的还指出大题中的小题。对于类似题，个别的也作了简单解答。
试题也按教材分11章列出。但试题内容具体分到哪章，其划分并不唯一。例如，线性表的问题，可以放在第2章，也可能因其用顺序存储结构实现使用了数组而放到第5章数据结构试题及答案，也可能因排序而放到第10章，甚至因用顺序查找而放到第9章。本书各章相互独立，在使用本书时，可以顺序学习，也可以根据需要直接选择某章。
为了增大本书的信息量，在保持算法易读性的前提下，尽量使用多语句行，尽量减少图（使用表格代替图形）。
本书是很多人的劳动结晶。计算机学院的学生购买了试题，并进行了文字输入。宁方美、田相庆、庞圣波、王景波等同学对输入的试题进行了校对。范策、孟佳娜、卢云宏等老师对算法提出了一些建议，编者对所有帮助编写本书的同志表示衷心的感谢。在成书过程中，还得到了机械工业出版社的支持和帮助，在此表示衷心的感谢。
胡潇琨老师编写了本书的第10章，并做了试题归类等工作。李玲老师编写了本书的第1章，绘制了大量图表，并核查了部分算法。本书中除第1章、第10章外的其余内容均由陈守孔老师编写。
我们尽全力保证本书的质量，但由于水平有限，加之时间紧张，书中肯定会有缺点和错误，特别是算法的编写很难保证是优化的。编者诚恳地期望读者给予批评指正。
编 者
2004年4月于烟台大学
书摘:三、填空题
1.数组的存储结构采用存储方式。（中山大学1998一、6（1分））（北京邮电大学2006一、6（2分））
2.二维数组A（10..20，5..1）采用行序为主序方式存储，每个数据元素占4个存储单元，且A（10，5）的存储地址是1000，则A（18，9）的存储地址是。（北京交通大学2006二、2（2分））
3.对于数组An*n，其元素aij按行优先与按列优先存储时地址之差为。（东南大学2005数据结构部分二、3（1分））4.设数组a（1..50，1..80）的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，
则元素a（45，68）的存储地址为（1）；若以列序为主序顺序存储，则元素a（45，68）的存储地址为（2）。（华中理工大学2000一、5（2分））
5.三维数组a（4）（5）（6）（下标从0开始计，a有456个元素），每个元素的长度是2，则a（2）（3）（4）的地址是____。（设口（0）（0）（0）的地址是1000，数据以行为主方式存储。）（南京理工大学2000二、11（1.5分））
6.已知二维数组A（1..10，0..9）中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A（5，9）的地址是。（厦门大学2002六、5（4分））。
文章来源:http://m.china-pub.com/touch/tbookinfo_more.aspx?id=3771098