作者：王苗 刘一凡 石强
出版社：中国铁道出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据结构习题解答与实验指导(第四版)试读：
版权信息书名：数据结构习题解答与实验指导（第四版）
作者： 王苗,刘一凡,石强
排版：中国铁道出版社
出版社：中国铁道出版社
出版时间：2016.04
ISBN：978-7-113-21688-7
本书由中国铁道出版社授权北京当当科文电子商务有限公司制作与发行。
— · 版权所有 侵权必究 · —内容简介
本书是普通高等教育“十一五”国家级规划教材《数据结构（第四版）》的配套用书，集作者多年讲授“数据结构”课程及指导学生实验的教学实践经验编写而成。
全书由两篇组成：第一篇为学习提要和习题解答，主要内容为数据结构各部分的重点难点指导、典型例题解析和主教材习题解答，其中典型例题以选择题、判断题、填空题、简答题和算法设计题等各种题型进行汇编，并提供分析过程和参考算法，帮助学生提纲挈领地掌握知识重点、巩固所学内容；第二篇为课程实验与设计指导，根据数据结构课程的教学重点，给出多个课程实验与设计题目，每个题目都有明确的要求，同时给出了规范的课程实验与设计步骤。希望学生通过课程实验与设计对理论知识有更深的理解，同时提高算法的分析和设计能力。本书配合主教材使用，起到衔接课堂教学、课程实验与设计教学以及课下辅导的作用。
本书适合作为高等院校“数据结构”课程的参考书，也可作为研究生入学考试的辅导材料，对于从事计算机应用及开发的技术人员以及广大的计算机及相关专业的自学者也具有一定的参考价值。第四版前言
数据结构是计算机科学与技术及相关信息类专业的一门核心基础课程。本书将主教材各章的知识要点进行归纳和总结，着重讲述原理、概念和实例，对重点难点问题进行讲解和指导，对涉及重要知识点的典型例题进行分析和解答，帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。
数据结构还是一门理论与实践紧密结合的课程，要求学生不仅能理解基础的理论知识，针对具体问题选择和设计出适当的逻辑结构、存储结构及相应的算法，还要在此基础上编写出结构清晰、正确易读、符合软件工程规范的程序。因此，数据结构的学习过程也是进行复杂程序设计的训练过程。为了提高学生的实践技能，培养好的程序设计风格和习惯，本书根据具体的应用，编写了课程实验与设计指导部分，针对性地给出了课程实验与设计题目，明确了实验教学中的具体要求，同时还给出了规范的实验步骤。
本书是《数据结构（第四版）》（书号：ISBN 978-7-113-21417-3，中国铁道出版社出版，刘振鹏、王苗、赵红编著）的配套用书，按照最新考研大纲修订，在内容上力图具有一定的先进性和较强的适应性。本书是编者在总结多年指导学生实验课教学和讲授数据结构课程经验的基础上编写的。作为普通高等教育“十一五”国家级规划教材《数据结构（第四版）》的配套用书，全书在保持前三版的基本框架基础上进行了修订，进一步完善和优化了数据结构课程的体系内容。主要有：简化一些数据结构的描述方式，增加一些算法的举例等，规范化全书的算法描述；丰富典型例题的题型和内容，并对主教材习题进行了分析或解答；针对性地给出线性结构、树形结构、图形结构、查找和排序这4个知识单元的课程实验与设计题目。全书的修订着重强调课程内容与考研大纲的一致性，强调了C++中面向对象思想在算法中的体现，进一步细化和完善验证性实验的实现过程和综合性实验的设计细节。
本书分为两篇：第一篇是学习提要和习题解答，第二篇是课程实验与设计指导。第一篇由王苗、刘一凡修订，第二篇由石强修订。全书由王苗统稿。
在本书的编写过程中，参考了一些国内外的优秀教材，在此表示感谢。刘振鹏、劼张小莉、罗文等老师对本书的再版提出了许多宝贵意见，并给予了大力支持，对此表示衷心的感谢。
我们力求语言表述精练，解题思路清晰，算法描述规范严谨，但是限于编者水平，书中难免有疏漏与不妥之处，恳请读者批评指正。
编 者2016年2月第三版前言
数据结构是计算机科学与技术等电气信息类相关专业的一门核心基础课程。本书将各章的知识要点进行归纳和总结，对难以理解的问题进行通俗的讲解和指导，对涉及重要知识点的典型题目进行分析解答，目的是帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。此外，数据结构是一门理论与实践紧密结合的课程，不仅要能够理解基础理论知识，针对具体问题选择和设计出适当的逻辑结构、存储结构及相应的算法，还要能在此基础上编写出结构清晰、正确易读、符合软件工程规范的程序。在数据结构的教学中，除了课堂教学外，每周还应有不少于两个学时的实验课程。
本书根据国内数据结构的实际教学情况，在内容上力图具有一定的先进性和较大的适应性。遵循这一原则，在编写中着重讲述原理、概念和实例。为了提高学生实践技能，编写了实验指导部分。根据数据结构课程内容，给出了7个实验题目，对每个题目给出了明确的实验要求，同时还给出了规范的实验步骤和实验报告范例。
本书与中国铁道出版社出版的《数据结构（第三版）》教材相配套，按照最新考研大纲修订，实验部分都是根据作者指导本校学生实验课教学内容总结而成，是作者多年讲授操作系统课程和指导学生实验经验的积累。主要内容由两部分组成：理论知识与习题解答部分和实验题目与指导部分。作为普通高等教育“十一五”国家级规划教材《数据结构（第三版）》的配套教材，本书在第二版的基础上按照第三版教材进行了修改补充。本书保持了前一版的基本框架，内容上进行了进一步修订、调整和扩充，进一步完善了算法，增加和改善了重点算法的注释。在保持整体结构不变的情况下，对各章节内容进行了扩充和修正，增加了链表、栈、树、图、排序中的一些必要知识点，试图做到尽可能细致而全面。增加了近几年硕士研究生入学考试中的一些经典题目，并进行了详细而全面的解析。在本次修订过程中，作者着重强调了与考研大纲的一致性，强调了C++中面向对象思想在算法中的体现，进一步细化验证性实验的实现过程，进一步细化完善综合性实验的设计细化。书中所有程序都在VC++ 6.0环境下调试通过。
在本书的编写过程中，参考了一些国内外优秀教材及数据结构习题集和实验教程。刘振鹏、张小莉等老师对本书的编写提出了许多宝贵意见。对此表示衷心的感谢。
尽管我们做了很大的努力，但由于水平有限，书中难免有不妥之处，恳请读者予以指正。
编 者2009年12月第二版前言
数据结构是计算机科学与技术等电子信息类相关专业的一门重要的基础课程。通过对数据结构相关知识的理论学习，学生可以较全面地理解算法和数据结构的概念，掌握各种数据结构和算法的实现方式，比较不同的数据结构和算法的特点。数据结构是一门理论与实践紧密结合的课程，不仅要能够理解基础理论知识，针对具体问题选择和设计出适当的逻辑结构、存储结构及相应的算法，还要能在此基础上编写出结构清晰、正确易读、符合软件工程规范的程序，从而为进一步学习后继专业课程和软件开发打下良好的基础。
为了帮助读者提高求解数据结构习题的能力，作者结合多年讲授数据结构课程的经验编写了本书的理论知识与习题解答部分。将各章的知识要点进行了归纳总结，对重点和难点进行了再次阐述，精心选择了许多典型例题进行了解析，并且对配套教材上的课后习题给予了详细的解答。本据使计算情容定先较应
书根国内用机的况，在内上力图具有一的进性和大的适性。遵循这一原则，在编写中着重讲述原理、概念和实例。为了帮助读者提高应用数据结构、通过程序设计解决实际应用问题的能力，作者编写了实验指导部分。根据数据结构课程内容的需要，给出了7个实验题目，对每个题目给出了明确的实验要求，同时还给出了规范的实验步骤和实验报告范例。
本书与入选普通高等教育“十一五”国家级规划教材的《数据结构（第二版）》相配套。在第一版的基础上按照第二版教材进行了修改。本书保持了前一版的基本框劼架，进一步完善了算法，增加和改善了重点算法的注释。第一部分由罗文、王苗修订，第二部分由石强修订，全书由石强统稿。
本书分为两部分：第一部分是理论知识与习题解答，第二部分是实验指导。第一部分的内容与《数据结构（第二版）》一书相对应，也分为10章，每一章都由内容概述、重点难点指导、典型例题解析、课后习题选解等部分组成；第二部分的内容根据数据结构课程的重点，给出了7个实验题目，每个实验题目采用了统一的格式，由问题描述、数据结构设计、功能（函数）设计、界面设计、编码实现、运行与测试几个部分组成，为学生提出了明确的实验要求，并对实验步骤给予指导。
本书在写作和修订过程中，参考了一些国内外教材及数据结构习题集和辅导书，并且从互联网中汲取了不少数据结构方面的精华题目，得到了许多专家和众多院校数据结构任课教师的大力支持和帮助，他们提出了许多中肯的意见和很好的建议，对本书的修订起到了很大的指导作用。对此作者表示衷心的感谢。
在本书的编写过程中，刘振鹏、张小莉等老师对本书的编写提出了许多宝贵意见，并给予了大力支持，在此表示诚挚谢意。感谢作者的多位同事和学生，许百成、史青宣、苗秀芬、王硕等老师和许多学生对本书的内容提出了很多的修改意见，在使用本书的过程中指出了书中的一些不足，使得本书更为完善。
由于编者水平有限，书中难免有不妥之处，恳请读者批评指正，编者不胜感激。
编 者2007年11月第一版前言
数据结构是计算机专业的一门核心课程。在应用计算机解决实际问题时，首先要解决的就是如何将问题以计算机能接受的形式表示出来，然后再将解决问题的方法步骤用计算机能识别的形式告诉计算机，让计算机自动执行求解。这一过程就是人们所说的程序设计过程。“数据结构”课程的内容正是在长期的程序设计实践中提炼、升华而成的，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现，是计算机科学的算法理论基础和软件设计的技术基础。在计算机专业中数据结构是操作系统、数据库原理、编译原理等后续课程的基础，在计算机专业课程的学习中起着承上启下的作用。
由于数据结构具有概念性强，内容灵活，所涉及数据的组织、存储以及操作的方法比较抽象等特点，因此，对于初学者来说，往往找不到感觉，不知道如何学习这门课，面对习题更是无从下手。作者想借编写本书的机会结合多年讲授本门课程的经验，将各章的知识要点进行归纳和总结，对难以理解的问题进行通俗的讲解和指导，对涉及到重要知识点的典型题目进行分析解答，目的是帮助读者理解数据结构的内容，尽快掌握各种数据结构的表示方法及应用实现，同时求解数据结构习题的能力也能有一个明显的提高。
此外，数据结构还是一门实践性很强的课程，只是看书本、做习题是绝对不够的。因此，在数据结构的教学中，除了课堂教学外，每周还应有不少于两个学时的实验课。在数据结构的课程实验中要解决的问题更接近于实际，不同于平时的编写功能单一的“小”算法的练习，实验是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。为此，作者根据数据结构课程内容的需要，给出7个实验题目，并对每个题目提出明确的实验要求，同时还对实验步骤和实验报告进行了规范。
本书与中国铁道出版社出版的《数据结构》教材相配套，主要内容由两部分组成：理论知识与习题解答部分和实验题目与指导部分。其中理论知识与习题解答部分与《数据结构》一书相对应，也分10章，每一章都由内容概述、重点难点指导、典型例题解析以及课后习题选解等部分组成；实验题目与指导部分根据数据结构课程的教学重点，给出7个实验题目，每个实验题目采取了统一的格式，由问题描述、数据结构设计、功能（函数）设计、界面设计、编码实现、运行与测试几个部分组成，为学生提出明确的实验要求，并对实验步骤给予指导。
在本书的编写过程中，参考了一些国内外优秀教材及数据结构习题集和辅导书。刘振鹏、张小莉等老师对本书的编写提出了许多宝贵意见，并给予大力支持，在此表示诚挚谢意。
本书在编写过程中力求概念清晰，表述正确，通俗易懂，便于自学。希望读者通过对本书的学习，能够更全面、更透彻地理解和掌握数据结构这门课程。但由于编者水平有限，书中难免存在疏漏或不妥之处，恳请读者批评指正，编者不胜感激。
编 者2004年10月第一篇学习提要和习题解答第1章绪论
本章主要介绍一些关于数据结构的概念、学习数据结构的意义，以及描述算法和分析算法的方法。
重点与难点
● 数据结构的基本概念、抽象数据类型；
● 数据结构的逻辑结构、存储结构及运算；
● 算法、算法的特性和目标；
● 算法的时间复杂度、空间复杂度及其分析方法。1.1重点难点指导
数据是计算机化的信息，是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制，还是文件的存储和检索及数据库技术等计算机应用，都是对数据进行加工处理的过程。1.1.1 相关术语
1.数据、数据元素、数据项和数据对象
数据：信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。
数据项：具有独立含义的最小单位。有些数据元素是由若干数据项组成的。数据项有名和值之分：数据项名是一个数据项的标识，用变量定义；数据项值是它的一个可能取值。数据项具有一定的类型，依数据项的取值类型而定。
数据元素：数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。一个数据元素可由若干数据项组成，这些数据项可以分为两种：一种称为初等项，这些数据项是在数据处理时不能再分割的最小单位；另一种称为组合项。
数据对象或数据元素类：具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类）。数据元素是数据元素类的一个实例。
2.数据类型
数据类型是一个值的集合以及在这些值上定义的一组操作的集合。
在高级程序设计语言中，数据类型可分为如下两类：
①原子类型：其值是不可分解的。例如，C++语言中的整型、字符型、浮点型、双精度型等基本类型，分别用关键字int、char、float、double标识。
②结构类型：其值是由若干成分按某种结构组成的，是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。
3.抽象数据类型
抽象数据类型是指抽象数据的组织和与之相关的操作。它可以看作数据的逻辑结构及其在逻辑结构上定义的操作。
抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。也就是说，在设计抽象数据类型时，把类型的定义与其实现分离开。
4.数据结构
数据结构是指互相之间存在着一种或多种关系的数据元素的集合，是指数据元素之间的相互关系，即数据的组织形式。它包括以下3方面的内容：
①逻辑结构：数据之间的逻辑关系。
②存储结构：数据元素及其关系在计算机存储器内的表示。
③数据的运算：对数据对象施加的操作。
5.两类逻辑结构（1）线性结构
线性结构的逻辑特点：若结构为非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和直接后继，如线性表。（2）非线性结构
非线性结构的逻辑特点：一个结点可能有多个直接前驱和直接后继，如树形结构和图形结构。
6.数据逻辑结构的4种基本形态
①集合结构：数据元素间的关系是“属于同一个集合”。
②线性结构：数据元素之间存在着一对一的关系。
③树形结构：数据元素之间存在着一对多的关系。
④图形结构：数据元素之间存在着多对多的关系。
7.4种常见的存储结构（1）顺序存储
顺序存储方法是将逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。（2）链式存储
链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针类型来实现。（3）索引存储方式
索引存储方式是通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地址信息，可通过该地址找到结点的其他信息。（4）散列存储方式
散列存储方式是根据结点的关键字直接计算出该结点的存储地址的方法。1.1.2 算法的描述和分析
1.算法
算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：
①有穷性：一个算法必须在有穷步之后结束，即必须在有限时间内完成。
②确定性：算法的每一步必须有确切的定义，无二义性。
③可行性：算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。
④输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。
⑤输出：一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。
2.对算法的设计要求
①正确：算法的执行结果应当满足预先规定的功能和性能要求。
②可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂。
③健壮：当输入不合法数据时，应能进行适当处理，不至于引起严重后果。
④高效：有效地使用存储空间和有较高的时间效率。
3.算法的性能分析与度量（1）时间复杂度
①某算法的时间复杂度是执行该算法所耗费的时间。通常某算法的时间复杂度是问题规模n的函数T（n）。
②大Ο记法：表示算法的渐近时间复杂度。
③常见的渐近时间复杂度有：
O（1）＜O（log n）＜O（n）＜O（nlog n）＜O（n 2 ）＜22O（n 3 ）＜O（2 n ）（2）空间复杂度
一个算法的空间复杂度是指该算法所耗费的存储空间。它通常也是问题规模n的函数T（n）。1.2典型例题解析1.2.1 选择题
1.数据结构是一门研究非数值计算程序设计中计算机的（①）以及它们之间的（②）和运算的学科。
①A.操作对象 B.计算方法 C.逻辑存储 D.数据映像
②A.结构 B.关系 C.操作 D.算法【分析】 数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。【答案】 ①A ②B
2.从逻辑上可以把数据结构分为（ ）两大类。
A.动态结构、静态结构 B.顺序结构、链式结构
C.线性结构、非线性结构 D.初等结构、构造型结构【分析】 数据的逻辑结构可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。数据的逻辑结构有两类，分别是线性结构和非线性结构。【答案】 C
3.线性结构的顺序存储结构是一种（①）的存储结构，线性结构的链式存储是一种（②）的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取【分析】 顺序存储结构是一种随机存取结构，链式存储结构是一种顺序存取结构。【答案】 ①A ②B
4.计算机算法指的是（ ）。
A.计算方法 B.排序方法
C.解决问题的步骤序列 D.调度方法【分析】 算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。【答案】 C
5.算法必须具备（ ）这3个特性。
A.可执行性、可移植性、可扩充性 B.可行性、确定性、有穷性
C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性【分析】 一个算法应该具有下列特性：有穷性、确定性、可行性、输入、输出。【答案】 B
6.算法的时间复杂度取决于（ ）。
A.问题的规模 B.待处理数据的初态
C.A和B D.机器的运行速度【分析】 某算法的时间复杂度是执行该算法所耗费的时间，通常某算法的时间复杂度是问题规模n的函数T（n）。【答案】 A
7.下面程序的时间复杂度为（ ）。
A.O（m 2 ） B.O（n 2 ） C.O（m×n） D.O（m+n）【分析】 第一个for循环执行m次，第二个for循环执行n次，两个for循环嵌套起来共执行m×n次。【答案】 C
8.在下面的程序段中，最后一行的语句频度在最坏情况下是（ ）。
A.O（n） B.O（nlog n） C.O（n 3 ） D.O（n 2 ）2【分析】 第一个for循环执行n-1次，第二个for循环分别执行n-1、n-2、…、1次，两个for循环嵌套起来在最坏情况下共执行n×（n-1）/2次。【答案】 D1.2.2 判断题
1.数据元素是数据的最小单位。【分析】 数据元素是数据的基本单位，一个数据元素可由若干数据项组成。【答案】 错误
2.顺序存储方式只能用于线性结构，不能用于非线性结构。【分析】 顺序存储方式能用于存储非线性结构。例如，存储树形结构中，完全二叉树的数组存储和堆排序中堆的存储。【答案】 错误
3.基于某种逻辑结构之上的运算，其实现是唯一的。【分析】 基于某种逻辑结构，其存储结构不唯一，因此运算实现也就不唯一。【答案】 错误
4.抽象数据类型只是一个数学模型。【分析】 抽象数据类型是指一个数学模型及定义在该模型上的一组操作。【答案】 错误
5.数据的逻辑结构是指数据的各数据项之间的逻辑关系。【分析】 数据的逻辑结构是指数据之间的逻辑关系。数据元素是数据的基本单位，数据项是数据的最小单位。【答案】 错误
6.数据结构是带有结构的数据元素的集合。【分析】 若对数据结构进行形式化描述，则可从逻辑上认为数据结构DS是数据元素的集合D和D上关系的集合R所构成的二元组：DS=（D，R）。这里的关系R用于描述数据之间的逻辑关系，即数据的结构。【答案】 正确
7.算法可以用不同的语言描述，如果用C语言或Pascal等高级语言来描述，则算法实际上就是程序。【分析】 算法用各种计算机语言描述表现为一个程序但并不等同于程序，因为程序的逻辑不一定能满足有穷性。【答案】 错误
8.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。【分析】 算法的健壮性是指当输入不合法数据时，应能进行适当处理，不至于导致严重后果。【答案】 正确1.2.3 填空题
1.线性结构中元素的关系是_______，树形结构中元素的关系是_______，图形结构中元素的关系是_______。【分析】 线性结构数据元素之间存在着一对一的关系；树形结构数据元素之间存在着一对多的关系；图形结构数据元素之间存在着多对多的关系。【答案】 一对一；一对多；多对多
2.抽象数据类型的定义仅取决于它的一组_______，而与_______无关，即不论其内部结构如何变化，只要它的_______不变，都不影响其外部使用。【分析】 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。【答案】 逻辑特性；表示和实现；数学特性
3.数据的逻辑结构是指_______。【分析】 数据的逻辑结构可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。【答案】 数据之间的逻辑关系
4.一个数据结构在计算机中的_______称为存储结构。【分析】 数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称为存储结构。【答案】 标识（或映像）
5.算法的5个重要特性是_______、_______、_______、_______和_______。【分析】 一个算法应该具有下列特性：有穷性；确定性；可行性；输入；输出。【答案】 有穷性；确定性；可行性；输入；输出1.2.4 简答题
1.说明数据结构的概念与程序设计语言中数据类型概念的区别和联系。【解答】 数据类型是一个值的集合以及在这些值上定义的一组运算的集合。例如，C语言中的int类型，表示集合{x|x是整数且-32 768≤x≤32 767}，其运算包括“+”“-”“×”“/”和“％”等。
数据结构指存在特定关系的数据元素的集合。数据结构包括3方面的内容：①数据的逻辑结构，指数据元素之间的逻辑关系；②数据的存储结构，指数据元素及其关系在计算机中的实现方法；③数据的运算，指对数据元素施加的操作。
二者都是数据元素和运算的集合，但是数据结构还涉及数据元素之间的逻辑关系。
2.编写一个程序，计算一元多项式P （x）=P +P x+P x 2 +n012…+P x n 的值P （x ），设n、x 和P （0≤i≤n）均为已知量，从nn00i键盘读入。程序中P （0≤i≤n）的值是采用什么结构存储的？i【分析】 将一元多项式改写为如下形式：
P （x）=P +P x+P x 2 +…+P x n =（…（（P x+P ）xn012nnn-1+P ）x+…+P ）x+P n-210
程序中P 的值可以采用顺序结构进行存储。i【算法】
P 的读入次序为：P ，P ，…，P ，P 。inn-1101.3主教材习题解答1.3.1 选择题
1.从逻辑上可以把数据结构分为（ ）两大类。
A.动态结构、静态结构 B.顺序结构、链式结构
C.线性结构、非线性结构 D.初等结构、构造型结构【答案】 C
2.在下面的程序段中，对x的赋值语句的频度为（ ）。
A.O（2 n ） B.O（n） C.O（n 2 ） D.O（log n）2【答案】 C
3.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ ）。
A.一定连续 B.一定不连续
C.不一定连续 D.部分连续，部分不连续【答案】 A
4.下面关于算法说法正确的是（ ）。
A.算法的时间复杂度一般与算法的空间复杂度成正比
B.解决某问题的算法可能有多种，但肯定采用相同的数据结构
C.算法的可行性是指算法的指令不能有二义性
D.同一个算法，实现语言的级别越高，执行效率就越低【答案】 D
5.在发生非法操作时，算法能够做出适当处理的特性称为（ ）。
A.正确性 B.健壮性 C.可读性 D.可移植性【答案】 B1.3.2 简答题
1.解释下列术语：数据、数据元素、数据对象、数据结构、存储结构、线性结构、算法、数据类型。【解答】 数据：数据是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。它可以是数值数据，也可以是非数值数据。
数据元素：数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。一个数据元素可由若干数据项组成，这些数据项可以分为两种：一种称为初等项，这些数据项是在数据处理时不能再分割的最小单位；另一种称为组合项。
数据对象：数据对象（或数据元素类）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类）。数据元素是数据元素类的一个实例。
数据结构：数据结构是指互相之间存在着一种或多种关系的数据元素的集合，是指数据元素之间的相互关系，即数据的组织形式。
存储结构：存储结构指数据元素及其关系在计算机存储器内的表示。
线性结构：线性结构是一个有序数据元素的集合。线性结构的逻辑特点：若结构为非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和直接后继。常用的线性结构有线性表、栈、队列。
算法：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。
数据类型：数据类型是一个值的集合以及在这些值上定义的一组操作的集合。
2.说明数据结构的概念与程序设计语言中数据类型概念的区别和联系。【解答】 参考1.2.4节简答题中的第1题。
3.讨论顺序存储结构和链式存储结构各自的特点、适用范围，并说明在实际应用中应如何选取数据存储结构。【解答】 顺序存储结构用存储位置的相邻表示逻辑关系的相邻，需要占用连续的存储单元，可以随机访问数据元素。
链式存储结构用附加的指针表示逻辑关系，不需要占用连续的存储空间，只能顺序地访问数据元素。链式存储结构是动态分配内存的方式，它在需要时分配存储单元，不需要时释放存储单元。当对于数据元素需要频繁地插入、删除时应采用链式存储结构。
顺序存储结构是静态分配内存的方式；当对于数据元素不需要频繁地插入、删除时，应采用顺序存储结构。
4.设n为正整数，利用大O记号将下列程序段的执行时间表示为n的函数。【答案】（1）O（n）（2）O（n）（3）O（n）（4）O（1）（5）O（n 2 ）（6）O（n 3 ）
5.试写一算法，从大到小依次输出顺序读入的3个整数x、y和z的值。【提示】 通过比较和交换使得3个数从大到小有序输出。【参考算法】
6.已知k阶斐波那契序列的定义为：
f（0）=0，f（1）=0，…，f（k-2）=0，f（k-1）=1；
f（n）=f（n-1）+f（n-2）+…+f（n-k）（n=k，k+1，…）
试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以参数的形式在参量表中出现。【提示】 采用递归的方法实现。【参考算法】
7.试编写算法，计算i！×2i的值并存入数组a[Arrsize]的第i个分量中（i=1，2，…，n）。假设计算机中允许的整数最大值为Maxint，则当n>Arrsize或对某个k（1≤k≤n）使k！×2k>Maxint时，应按出错处理。可有下列3种不同的处理方式：
①用ERROR语句终止执行并报告错误。
②用返回值0或1实现算法以区别正确返回或错误返回。
③在参数表中设置一个整型变量以区别正确返回或某种错误返回。
试讨论这3种方法各自的优缺点，并以自己认为较好的方式实现。【提示】 采用第2种处理方式。【参考算法】第2章线性表
本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点与难点
● 线性表的逻辑结构；
● 顺序表的特点、基本运算的实现及时空性能分析；
● 链表的特点、基本运算的实现及时空性能分析；
● 循环链表、双向链表、静态链表；
● 顺序表和链表的优缺点及适应情况。2.1重点难点指导
线性表是一种线性结构，是最简单、最基本、也是最常用的一种线性结构。它有两种存储结构——顺序表和链表。线性表用途广泛，应用于信息检索、存储管理、模拟技术和通信等领域。2.1.1 相关术语
1.线性表
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为（a ，a ，…，a ），其中n为表长，n=0时称为空表。12n
线性表是一种逻辑结构，其数据元素属于相同数据类型，数据元素之间的关系是线性关系。
2.顺序表
顺序表是顺序存储的线性表。
顺序表按线性表中元素的逻辑顺序依次存储在地址连续的存储单元里，其存储特点是用物理上的相邻实现逻辑上的相邻。
3.链表
链表是用链式存储的线性表。
链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4.单链表
单链表的每个结点除了数据域外还有一个指向其后继的指针域。
通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5.头指针
头指针是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。如链表H、链表L等，表示链表中第一个结点的地址存放在指针变量H和L中。通常用头指针来唯一标识一个链表。
6.头结点
头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7.头结点的作用
头结点的作用有两个：一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无须特殊处理。2.1.2 线性表的顺序存储
1.顺序表
顺序存储的线性表称为顺序表。其特点是用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
具体实现：在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等，即表长是可变的，因此，数组的容量需设计得足够大。设用data[MaxSize]来表示数组容量，其中MaxSize是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0]开始依次顺序存储，但当前线性表中的实际元素个数可能未达到MaxSize，因此需用一个变量last记录当前线性表中最后一个元素在数组中的位置，即last起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。
这种存储思想的具体实现可以是多样的。
方法一：可以用一个数组和表示长度的变量共同完成上述思想。例如：
这样表示的顺序表如图2-1所示。数据元素分别存储在data[0]～data[last]中。
这样使用简单方便，但有时不便于管理。
图2-1 线性表的顺序存储示意图1
方法二：从结构上考虑，通常将data和last封装成一个结构作为顺序表的类型：
定义一个顺序表变量：
这样表示的线性表如图2-2（a）所示。表长为L.last+1，线性表中的数据元素a ～a 分别存储在L.data[0]～L.data[L.last]中。1n
有时定义一个指向SeqList类型的指针更为方便：
L是一个指针变量，线性表的存储空间通过L=new SeqList操作（Visual C++语句，不同的语言版本可能有所不同）来获得。
L中存储的是顺序表的地址，这样表示的线性表如图2-2（b）所示。表长表示为（*L）.last+1或L->last+1，线性表中数据元素的存储空间为L->data[0]～L->data[L->last]。
图2-2 线性表的顺序存储示意图2
方法三：采用C++语言描述数据的存储及算法的实现，从结构性上考虑，通常将data和last封装在一起，考虑线性表上的基本操作，可定义顺序表的类模板如下：
读者通过上述介绍的几种表示方式，进一步体会顺序存储的“理念”，做题时根据题意灵活掌握，在读写算法时注意相关数据结构的类型说明。
2.顺序表的优缺点（1）优点
①顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。
设a 的存储地址为Loc（a ），每个数据元素占d个存储地址，11则第i个数据元素的地址为：
Loc（a ）=Loc（a ）+（i-1）×d（1≤i≤n）i1
这就是说，只要知道顺序表首地址和每个数据元素所占地址单元的个数即可求出第i个数据元素的地址，这就是顺序表具有按数据元素的序号随机存取的特点。
②存储密度高。（2）缺点
①在顺序表中进行插入和删除运算时，平均需移动大约表中一半的元素。
②顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。因此，分配不足则会造成溢出；分配过大，又可能造成存储单元的浪费。2.1.3 链表
1.单链表
链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素a ，除了存放i数据元素自身的信息a 之外，还需要和a 一起存放其后继a 所在iii+1的存储单元的地址，这两部分信息组成一个“结点”。结点的结构如图2-3所示，每个元素都如此。因此，n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。
图2-3 单链表结点结构
链表的结点定义如下：
若有定义LNode*p；，而语句：
即完成了申请一块LNode类型的存储单元的操作。
单链表的类模板定义如下：
作为线性表的一种存储结构，人们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2-4的形式表示。
图2-4 单链表
通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L和H中。头指针为NULL时表示一个空表。
2.单循环链表
对于单链表而言，最后一个结点的指针域是空指针，如果将该链表的头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。
对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，对链表的操作是在表尾、表头进行的，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，这样可以使操作效率得以提高。
3.双向循环链表
在单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next。而找其前驱结点则只能从该链表的头指针开始，顺着各结点的next域进行。也就是说，找后继结点的时间复杂度是O（1），找前驱的时间复杂度是O（n），如果希望找前驱结点的时间复杂度也达到O（1），则只能付出空间的代价：每个结点再加一个指向前驱结点的指针域。结点的结构如图2-5所示，用这种结点组成的链表称为双向链表。
图2-5 双向链表结点结构
双向链表结点的定义如下：
和单链表类似，双向链表通常也是用头指针标识。
通过双向链表中某结点的指针p既可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的指针p->prior。这样在有些操作中需要找前驱结点时，则无须再用循环。
设p指向双向循环链表中的某一结点，即p是该结点的指针，则p->prior->next表示的是p所指结点之前驱结点的后继结点的指针，即与p相等；类似地，p->next->prior表示的是p所指结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式：
4.静态链表
静态链表是指以数组方式存储链表的数据，数组的每个元素包含有数据域data和指针域next，这里的指针域next与链表中的指针域不同的是，其存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），又称静态指针。
在以静态链表方式存储链表时，数组中含有两个单链表：一个是数据元素的链表，一个是空结点的链表。故还需要设置两个整型变量，分别用于存储链表首元素（或头结点）在数组中的位置和空结点链表的首位置。
静态链表存储定义如下：
5.链式存储的优缺点
链式存储的优缺点与顺序存储互补。（1）优点
①对链表进行插入和删除运算时，只需改变指针，不需移动数据。
②不需要事先分配空间，便于表的扩充。（2）缺点
①存储密度降低，因为每个结点中除了存储数据元素的值外还有一个指针域。
②不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。2.1.4 线性表的基本运算
1.基于顺序表的运算
顺序表中常进行的运算有插入、删除、合并和查找等。进行这些运算时，要掌握一个原则：时刻体现顺序存储的思想，即元素之间物理相邻和逻辑相邻的一致性。（1）在顺序表中插入元素
①插入元素时，检查顺序表是否已满，已满则不能进行插入操作。
②根据具体问题确定插入位置。
③移动有关元素，以便为待插入的元素让出位置来。
④将元素插入。
⑤修改表长。（2）在顺序表中删除元素
①检查顺序表是否已空，空则不能进行删除运算。
②根据具体问题确定删除元素的位置。
③将其后面的有关元素移动，“挤掉”被删除的元素。
④修改表长。
结论：
①在顺序表中插入一个数据元素平均需要移动（n+1）/2个元素。在具体某一次的插入中，移动数据元素的个数与表长和插入位置有关。
②在顺序表中删除一个数据元素需要平均移动n/2个元素。在具体某一次的删除中，移动数据元素的个数与表长和删除元素的位置有关。
2.基于链表的运算
在链表操作过程中，主要是指针的变化，因此必须清楚指针和动态结点的问题。（1）头结点的使用
在对不带头结点的单链表进行操作时，对第一个结点的处理和其他结点是不同的。
头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存储的是第一个数据元素结点的地址，空表时为空。（2）插入
①在指定结点后插入新结点（后插）。
设指针p指向单链表中某结点，s指向待插入的值为x的新结点，将s结点插入到p结点的后面，插入示意图如图2-6所示。
操作如下：
要点：两个指针的操作顺序不能交换。
②在指定结点前插入新结点（前插）。
设指针p指向链表中某结点，s指向待插入的值为x的新结点，将s结点插入到p结点的前面，插入示意图如图2-7所示。与后插不同的是：前插首先要找到p结点的前驱结点q，然后完成在q结点之后插入s结点的操作。设单链表头指针为L，操作如下：
在指定结点后插入新结点操作的时间复杂性为O（1），在指定结点前插入新结点操作，因为要找p结点的前驱结点，时间复杂度为O（n）。其实人们更关心的是数据元素之间的逻辑关系，所以仍然可以将s结点插入到p结点的后面，然后将p->data与s->data交换即可。这样既满足了逻辑关系，也能使得时间复杂度为O（1）。
图2-6 在p结点之后插入s结点
图2-7 在p结点之前插入s结点
由此得知：在单链表中插入一个结点必须知道其前驱结点。
③在单链表第i个元素之前插入元素x。
试读结束[说明：试读内容隐藏了图片]