书名：数据结构抢分攻略：真题分类分级详解
ISBN：978-7-115-64513-5
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
编 著 船说出品
责任编辑 牟桂玲
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书面向参加计算机相关专业的硕士研究生招生考试（简称计算机考研）的考生，以全国硕士研究生招生考试计算机学科专业基础（简称全国统考）的考试大纲中数据结构部分的内容为依据，在研究、分析全国统考和院校自主命题考试的历年真题及其命题规律的基础上编写而成。
本书对全国统考的考试大纲进行了深入解读，提供了应试策略，并根据数据结构部分所涉及考点的知识体系分章讲解，每章以“知识点分类+经典例题精解”的形式，剖析了常考题型、命题特点及解题方法，帮助考生掌握解题思路与解题技巧。此外，章末提供了“过关练习”，供考生进行自测练习。本书还提供了面向数据结构的1套全真模拟题，供考生实战演练。
本书适合参加计算机考研（包括全国统考和院校自主命题考试）的考生备考学习，也适合作为计算机相关专业学生的学习用书和培训机构的辅导用书。
本书主旨“数据结构”是计算机学科的基础课程，也是计算机考研（包括全国统考和院校自主命题考试）涉及的重要内容。学好数据结构不仅有助于提高编程能力，以更好地应对计算机考研，更有助于提高解决问题的能力，对考生的个人成长大有裨益！
计算机考研题量大、涉及的知识点多，不少考生难以抓住重点，导致考试成绩不理想。为了帮助莘莘学子在较短的时间内掌握复习要点及解题方法，提高应试分数，我们深入研究与剖析计算机考研中的历年考点与考题，以全国统考的考试大纲为蓝本，以计算机考研中的重点和难点为主线，精心编写了本书。
主要学习目标全国统考的考查内容包括4部分——数据结构、计算机组成原理、操作系统和计算机网络，重点考查考生掌握相关基础知识、基本理论的情况，以及分析问题、解决问题的能力。
其中，数据结构部分的考查内容占30%。根据全国统考的考试大纲，本书主要帮助考生达成以下学习目标。
（1）理解数据结构的基本概念和术语，掌握各种数据结构的定义方法和基本操作，能够准确地计算出算法的时间复杂度和空间复杂度。
（2）掌握各种数据结构的程序复现（如利用C语言复现），深刻理解各种数据结构在数据管理方面的优缺点，能够根据数据特性及需要解决的目标问题，选用合理的数据结构予以解决。
（3）能够综合运用数据结构和算法去解决实际问题，并能运用某一种编程语言（如C语言、C++语言）予以实现。
本书主要特色（1）紧扣全国统考的考试大纲，明确复习要点，减少复习时间。
本书深入研究全国统考和院校自主命题考试的相关真题，依据全国统考的考试大纲分类提炼考点，不仅知识结构清晰，而且准确地对各考点进行考情分析，归纳有效的学习方法，帮助考生抓住复习重点，提高复习效率。
（2）详细讲解大量真题和例题，揭示命题思路，点拨应试技巧。
对于每一个考点，注重结合不同的题型，采取以题代点、以点代面的方式进行讲解。所用题目均为精选的历年真题或精心编写的典型例题，考生不仅能在学习解题的过程中巩固所学知识，而且能熟悉各种题型的解题思路与命题特点，从而有效提高应试能力。
（3）提供特色栏目，帮助考生掌握命题规律，提高应试能力。
书中提供“知识链接”“误区警示”“解题技巧”3个特色栏目。其中，“知识链接”栏目主要给出题目涉及知识点的概念、理论，便于考生回顾考点，加深对知识的理解；“误区警示”栏目主要用于提示考生易犯的答题错误；“解题技巧”栏目主要提供快速解题的方法和答题技巧。
（4）章末提供“过关练习”，考生可加以练习，提高解题能力。
在章尾，按该章考点所涉及的不同题型提供“过关练习”。这些练习题是根据章内相应考点在计算机考研中的命题类型及命题方式精心设计的。考生通过完成这些高质量的练习题，并将自己的答案与书中所提供的参考答案进行对照和检验，不仅可以巩固所学知识点，还可以进一步掌握重点、攻克难点，并能举一反三。
怎样使用本书为了更好地使用本书，建议考生阅读以下提示。
（1）充分了解计算机考研的要求，明确复习思路。建议考生在充分了解全国统考的考试大纲的考查要求后， 跟随本书复习考查重点，掌握解题思路和解题技巧，提高应试能力。
（2）抓住计算机考研重点，有的放矢。不主张考生采用题海战术，因为并不是练习题做得越多就越好。考题的形式虽然会千变万化，但是考查的知识点基本不变。考生应注意对各种知识点进行归纳总结，并全面提高自己的记忆能力，这样在复习时才能抓住重点，掌握解题要领，以不变应万变。
说明本书中例题，若无特殊说明，均为单项选择题。
尽管编者精益求精，但由于水平有限，书中难免有不足之处， 恳请广大读者批评指正，联系邮箱为muguiling@ptpress.com.cn。
最后，我们相信一分耕耘，一分收获。衷心祝愿使用本书的读者都能开卷有益，更上一层楼!
编 者
全国硕士研究生招生考试是指教育主管部门和招生机构为选拔研究生而组织的相关考试的总称。考试分初试和复试两个阶段进行。初试由国家统一组织，复试由招生单位自行组织。
初试一般设置4个考试科目，分别是思想政治理论、外语、业务课一和业务课二，满分分别为100分、100分、150分和150分。初试方式均为笔试，考试的第一天上午考查思想政治理论，下午考查外语；第二天上午考查业务课一（数学或专业基础课），下午考查业务课二（专业课）。每一科目考试时长均为180分钟。
对计算机考研而言，业务课一是数学，业务课二则根据学校或专业的不同，考查内容也会不同。目前来看，越来越多的学校对计算机或信息相关专业的业务课二，偏向于选择全国统考，也有少部分学校是自主命题。因此，考生在备考业务课二之前，要先明确所报考院校的考查科目和考查内容。
对计算机考研来说，全国统考主要考查计算机科学与技术领域的核心知识和技能，旨在考查学生在该领域的研究和应用能力。考试内容较为广泛，包括计算机科学与技术的基础理论、专业知识和应用技术。一般而言，主要涉及数据结构、计算机组成原理、操作系统和计算机网络4部分内容。
答题方式为闭卷、笔试；考试时间为180分钟；试卷满分为150分，其中数据结构内容占45分，计算机组成原理内容占45分，操作系统内容占35分，计算机网络内容占25分；试卷题型结构为单项选择题80分（40题，每题2分），综合应用题70分。
本书针对计算机考研中的数据结构部分的内容。在全国统考中，数据结构部分的单项选择题一般为10题左右，分值为20分左右；综合应用题一般为2题左右，分值为25分左右。
一些自主命题的院校会有所不同。例如，在哈尔滨工程大学2024年硕士研究生招生考试中，计算机科学与技术专业的初试业务课二为“计算机专业基础综合”，总分是150分，其中，数据结构部分为90分，计算机组成原理部分为60分。数据结构部分的题型为选择题（20分）、判断题（10分）、填空题（10分）、计算题（35分）、算法题（15分）。
再次强调，考生在备考前一定要了解自己心仪院校相关专业业务课二的考查内容，以及分数的分配情况，从而协调分配自己的复习时间，以达到高效复习的目的。
在全国统考中，数据结构部分主要考查线性表、栈、队列、数组、树、二叉树、图、查找、排序等内容。参照全国统考的考试大纲要求和历年真题的命题特点，本书各章内容在考试中所占分值比例、复习重要程度等如下表所示。
| 章名 |
考试大纲要求 |
历年考查要点 |
分值比例 |
复习重要程度 |
|---|---|---|---|---|
| 第一章 绪论 |
掌握数据结构与算法的基本概念；掌握时间复杂度和空间复杂度的计算 |
① 算法时间复杂度的计算 ② 算法空间复杂度的计算 |
4% |
★ |
| 第二章 线性表 |
掌握线性表的定义与性质；掌握顺序表的结构体定义、插入元素、删除元素的操作方法；掌握链表的结构定义、插入元素、删除元素、翻转链表的操作方法；了解链表中虚拟头结点的作用 |
① 顺序表的性质与操作 ② 单链表的性质与操作 ③ 循环链表的性质与操作 |
8% |
★★ |
| 第三章 栈、队列和数组 |
掌握栈和队列的基本概念与性质，以及顺序存储及链式存储的操作过程；掌握特殊矩阵的压缩存储形式；了解队列和栈的实际应用场景 |
① 栈的性质与操作 ② 队列及循环队列的性质与操作 ③ 特殊矩阵的压缩存储 |
8% |
★★ |
| 第四章 树形结构 |
掌握树、二叉树的基本概念与性质；掌握二叉树的存储与遍历操作；掌握线索化二叉树的构建方法；掌握哈夫曼编码与哈夫曼树；掌握并查集的相关算法；了解森林的基本概念，以及森林和树之间的转换方法 |
① 二叉树的遍历 ② 哈夫曼编码与哈夫曼树 ③ 完全二叉树的相关操作 |
20% |
★★★ |
| 第五章 图 |
掌握图的基本概念与性质、图的存储及基本操作；掌握邻接矩阵、邻接表的存储方式；掌握图的深度优先搜索与广度优 先搜索；掌握最小生成树的概念和相关算法；掌握最短路径的概念及相关算法；掌握拓扑排序的相关算法 |
① 图的邻接矩阵、邻接表的存储方式 ② 图的深度优先搜索和广度优先搜索 ③ 最小生成树的相关算法 ④ 拓扑排序算法 |
20% |
★★★ |
| 第六章 查找 |
掌握线性查找中折半查找和分块查找的算法过程；掌握二叉排序树和平衡二叉树（AVL树）的概念、性质和相关操作；掌握散列（Hash）表的基本概念及性质，并能够熟悉对应的冲突处理方法；掌握基本的字符串匹配算法，如暴力匹配算法、KMP算法 |
① 折半查找算法的操作流程 ② AVL树、B树、B+树的平衡条件及失衡下的调整策略 ③ 散列表的哈希函数及冲突处理方法 ④ 散列表的性能分析 |
30% |
★★★ |
| 第七章 排序 |
掌握各种排序算法的算法思想，能够进行程序设计，完成算法的代码编写；掌握堆排序算法的算法流程，以及每一轮排序调整策略；掌握快速排序算法的算法流程 |
① 各种排序算法的原理 ② 内部排序算法的性能分析 ③ 快速排序算法流程 |
10% |
★★★ |
考生可以根据上表安排复习时间和侧重点。
考生若想在考试中取得好成绩，除了需要牢固掌握知识点，还需要快速、准确地对一些题目做出判断和处理，因此，考生平时要善于归纳和总结一些通用的答题技巧，这有助于考生更好地应对考试，提高复习效率。
（1）直接挑选法。
对于考查概念或性质的试题，考生只要掌握相应的知识点就能直接做出正确的选择。
例1．下列对顺序存储的有序表 (长度为n)实现给定操作的算法中，平均时间复杂度为 O(1)的是（ ）。【2023年全国统考】
A．查找包含指定值元素的值
B．插入包含指定值元素的算法
C．删除第i个元素的算法
D．获取第i个值的算法
【答案】D
解题技巧
本题考查顺序表的基本性质。对于本题，考生只需要掌握顺序表的基本性质即可作答。由于顺序表的删除和插入元素操作都需要移动元素，故直接排除B选项和C选项。又因为顺序表的存储结构在内存上是完全连续的，所以可以通过计算直接得到第i个元素的地址，故可以直接获取第i个元素的值。
（2）还原法。
对于类似二叉树中遍历的题目，可以先根据已知条件，还原出满足条件的数据结构，再进行后续问题的求解。
例2．表达式 x+y*(z-u)/v 的等价后缀是（ ）。【2024年全国统考】
A．xyzu-*v/+
B．xuzu-V*+
C．+x/y-zuv
D．+x*y/-zuv
【答案】A
解题技巧
本题考查后缀表达式。可以根据给出的表达式还原出一棵表达式树，然后对这棵树进行后序遍历就能够得到等价后缀。
（3）带入模拟法。
对于类似队列的入队、出队合法性的问题，可以根据队列的性质，将选项依次带入模拟操作流程，进而找到满足或者违反该队列性质的答案。
例3．已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是（ ）。【2021年全国统考】
A．5, 4, 3, 1, 2
B．5, 3, 1, 2, 4
C．4, 2, 1, 3, 5
D．4, 1, 3, 2, 5
【答案】D
解题技巧
本题考查队列的性质。可以根据队列的性质，将选项依次带入队列中模拟入队、出队过程。对于A选项，依次从右端入队1, 2，再从左端入队3, 4, 5，即可得到此出队序列。对于B选项，从右端入队1, 2，然后从左端入队3，再从右端入队4，最后从左端入队5，即可得到此出队序列。对于C选项，从左端入队1, 2,然后从右端入队3，再从左端入队4，最后从右端入队5，即可得到此出队序列。用排除法，可知D选项为本题答案。
（1）熟悉考试大纲。全面了解考查范围和要求，明确复习的重点和难点，有的放矢地备考效率会更高。
（2）多做真题和模拟题。虽不建议采用题海战术，但多做典型的真题和模拟题，有助于熟悉考试的出题方式，掌握解题思路和答题技巧。同时，可以发现自己的薄弱环节，有针对性地进行复习和提高。
（3）掌握数据结构的基本原理和基本操作。理解各种数据结构的基本原理和基本操作是解题的基础。因此，考生要牢固掌握各种数据结构的特点、存储结构和基本操作，能够灵活运用它们解决问题。
（4）掌握常见的算法和操作。数据结构和算法是密不可分的，掌握一些常见的算法和操作，如排序、查找、遍历等，能够帮助你更好地解决与数据结构相关的问题。
（5）保持思路清晰，注意细节。在解题过程中，可以通过在纸上画图、列出关键点的方式，帮助自己厘清思路，避免遗漏。同时，要注意代码书写的正确性和规范性，避免因为细节问题失分。
记住，数据结构是一个需要理解和实践的学科，通过多做题、总结经验和不断提高解题能力，相信你能够在考试中取得好成绩！
