数据结构c++版课后习题解析

《数据结构c++版课后习题解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论11.1本章导学11.2习题解析2第2章线性表92.1本章导学92.2习题解析10第3章栈和队列193.1本章导学193.2习题解析20第4章字符串和多维数组264.1本章导学264.2习题解析27第5章树和二叉树325.1本章导学325.2习题解析33第6章图436.1本章导学436.2习题解析44第7章查找技术567.1本章导学567.2习题解析57第8章排序技术678.1本章导学678.2习题解析68第9章索引技术789.1本章导学789.2习题解析7878第1章绪论1.1本章导学1.知识结构图本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。⑴数据⑵数据元

2、素⑶数据结构⑷抽象数据类型⑴逻辑结构⑵数据结构的分类⑴存储结构⑵常用存储方法⑴算法⑵算法特性⑶评价算法⑷描述算法⑴问题规模⑵基本语句⑶时间复杂度⑷大O记号图1-1知识结构图绪论数据结构算法基本概念逻辑结构存储结构基本概念算法分析关系2.学习要点对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中

3、在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法的效率。781.2习题解析1.填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素（2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。（3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构、图结构（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。【解答】顺序存储结构，链

4、接存储结构，数据元素，数据元素之间的关系（5）算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码（7）在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为2n*log25n+8n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，

5、需要将低次幂去掉，将最高次幂的系数去掉。2.选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线性表D集合【

6、解答】B78【分析】将丈夫、妻子和子女分别作为数据元素，根据继承关系画出逻辑结构图如图1-2丈夫妻子子女n子女1图1-2遗产继承逻辑结构图所示。（3）计算机所处理的数据一般具有某种内在联系，这是指（）。A数据和数据之间存在某种关系B元素和元素之间存在某种关系C元素内部具有某种结构D数据项和数据项之间存在某种关系【解答】B【分析】数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。（4）对于数据结构的描述，下列说法中不正确的是（）。A相同的逻辑结构对应的存储结构也必相同B数据结构由逻辑结构、存储结构和基本操作三方面组成C

7、对数据结构基本操作的实现与存储结构有关D数据的存储结构是数据的逻辑结构的机内实现【解答】A【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺序存储也可以链接存储，在顺序存储和链接存储结构下插入操作的实现截然不同。（5）可以用（）定义一个完整的数据结构。A数据元素B数据对象C数据关系D抽象数据类型【解答】D【分析】抽象数据类型是一个数据结构以及定义在该结构上