数据结构习题参考答案讲述.doc

第1章 概 论 1.数据数据元素数据结构数据类型的含义分别是什么？数据对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。数据元素数据的基本单位在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。数据类型：取值范围基本运算2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构数据的逻辑结构定义了数据中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ① 数据元素的信息； ② 各数据元素之间的关系。物理结构也叫储存结构是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式包括结点数据和关系的表示。3.数据结构的主要操作包括哪些？对于各种数据结构而言，在基本操作是相似的，最常用的操作有： 创建：建立一个数据结构； 除：除一个数据结构； 插入：在数据结构中增加新的结点 删除：把指定的结点从数据结构中 访问：对数据结构中的结点进行访问 更新：改变指定结点的值或改变指定的某些结点之间的关系 查找：在数据结构中查找满足一定条件的结点 排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？5.什么是算法？算法的基本特征是什么？算法是在有限的步骤内解决数学问题的过程，是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述。一个有效的算法必须满足的五个重要特性： ① 有穷性：算法必须能在有限的时间内做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。 ② 确定性：算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不是抽象和模糊的概念，更不允许有二义性。 ③ 输入：算法有0个或多个输入值，来描述算法开始前运算对象的初始情况，这是算法执行的起点或是依据。0个输入是指算法本身给出了运算对象的初始条件。 ④ 输出：算法至少有1个或多个输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。 ⑤ 可行性：算法中要做的运算都是基本运算，能够被精确地进行。即算法中执行的任何计算都可以被分解为基本的运算步，每个基本的运算步都可以在有限的时间内完成。6.什么是算法分析？算法分析主要考虑哪几方面的内容？①时间代价：执行算法所耗费的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。 ②空间代价：执行算法所耗费的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。 7.分析下面算法的时间复杂度。 （1）（2） （3） （4）（5）O(log2n) 8.算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？第二章 线性表 1．具有什么特征的数据结构被称为线性表？2．如何实现线性表的顺序存储结构？把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特点： 线性表中所有元素所占的存储空间是连续的； 线性表的逻辑顺序与物理顺序一致； 数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为 LOC(e1)，每一个数据元素占k个字节，则线性表中第i个元素ei在计算机存储空间中的存储地址为： LOC(ei)=LOC(e1)+(i-1)k 3．如何实现线性表的4种链式存储结构？数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。每个结点分为两部分：一部分用于存放数据元素的值，称为数据域；另一部分是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。对于线性表，指针域用于指向该结点的前一个或后一个结点（即前驱结点或后继结点）。通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为链式存储结构。在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空（用NULL或0表示），表示链表终止，这样的线性链表称为单向链表。图是单向链表示意图。 线性表的单向链式存储 将单向链表最后一个结点的指针指向头结点，这样整个链表就构成一个循环，这种链式存储结构称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一