数据结构实用教程习题答案.doc

《数据结构实用教程习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1绪论1.1回答下列概念：数据结构，数据的逻辑结构，数据的存储结构，算法数据结构:按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构。数据的逻辑结构:数据元素之间的逻辑关系，是根据实际问题抽象出来的数学模型。数据的存储结构:是指数据的逻辑结构到计算机存储器的映射。算法:是指对数据元素进行加工和处理1.2数据结构研究的三方面内容是什么？它们之间有什么联系和区别？三方面内容:数据的逻辑结构、数据的存储结构和数据运算的集合。联系和区别

2、：数据的逻辑结构是数学模型，数据的存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.3简述数据结构中讨论的三种经典结构及其逻辑特征。三种经典结构：线性表、树和图。线性表：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，数据元素间存在着一对一的相互关系。树：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，数据元素间存在着一对多的层次关系。图：可有若干个开始结点和终端结点，其余的内部

3、结点可以有若干个前趋结点和若干个后继结点，数据元素间存在着多对多的网状关系。1.4实现数据存储结构的常用存储方法有哪几种？简述各种方法的基本思想。常用存储方法有四种：顺序存储、链接存储、索引存储、散列存储。各种方法的基本思想：顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加索引表来标识数据元素的地址。散列存储：根据数据元素的关键字直接计算出该结点的存储地址，称为关键字－地址转换法。1.5算法的特性是什

4、么？如何定性的评价一个算法的优劣？算法的特性：有穷性、确定性、可行性、输入、输出。算法的定性评价标准有：正确性、可读性、健壮性、简单性。1.6算法的定量评价标准是什么？算法的定量评价标准有：时间复杂度和空间复杂度。时间复杂度：是一个算法运行时所耗费的系统时间，也就是算法的时间效率。空间复杂度：是一个算法运行时所耗费的存储空间，也就是算法的空间效率。1.7写出下列程序段中带标号语句的频度，并给出执行各程序段的时间复杂度（n为整数）。（1）i=1;（2）s=1;while（i

5、;i++)【1】i++;【1】s=s*i;（3）s=0;（4）i=1;for(i=l;i=i;j--)【1】i++;【1】s=s+i+j;（5）i=1；（6）x=1;y=100;while（i

6、概念：线性结构，线性表，顺序表，单链表，静态链表线性结构：设Data_Structure=（D，S），r∈S，相对r，D中有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋和一个后继，则称Data_Structure是相对r的线性结构。线性表：是具有相同属性的n（n≥0）个数据元素的有限序列。顺序表：顺序表（SequentialList）是采用顺序存储结构的线性表。单链表：每个结点只附加一个指向后继的指针域，这样的链表称为单链表（SingleLinkedList）静态链表：用数组实现的链

7、表，指针就变换为数组的下标，结点即为数组中的下标变量，由于需要预先分配一个较大的数组空间，因此这种链表称之为静态链表。2.2比较顺序表和链表这两种线性表不同存储结构的特点。１．逻辑关系的表示：顺序表隐含表示关系，链表显示表示关系。2．存储密度：顺序表的存储密度大，而链表的存储密度小。3．存储分配方式：顺序表的存储空间是预先静态分配的一块连续存储空间，在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模，动态分配和释放存储空间，存储空间可连续也可不连续。4．存取方法：顺序表可以随机存取，链表必须

8、顺序存取。5．插入、删除操作：在顺序表中做插入、删除时平均移动表中一半的元素；在链表中作插入、删除时，只要修改指针域，而不需要移动元素。所以顺序表的插入、删除效率低，链表的插入、删除效率高。6．实现语言：顺序表容易实现，任何高级语言中都有数组类型。而链表的操作是基于指针的，对于没有提供指针类型的高级语言，必须采用静态链表。总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频