数据结构、算法及应用C++语言描述习题答案doc

1、-. z.第1章 概 论1.数据、数据元素、数据构造、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。数据元素：数据的根本单位，在计算机程序常作为一个整体考虑。数据构造：数据元素之间的关系+运算，是以数据为成员的构造，是带构造的数据元素的集合，数据元素之间存在着一种或多种特定的关系。数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不一样，不同的数据就必须要分配不同大小的存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值围和根本运算等概念。2.什么是数据的逻辑构造？什么是数据的物理构

2、造？数据的逻辑构造与物理构造的区别和联系是什么？逻辑构造：数据的逻辑构造定义了数据构造中数据元素之间的相互逻辑关系。数据的逻辑构造包含下面两个方面的信息： = 1 * GB3 数据元素的信息； = 2 * GB3 各数据元素之间的关系。物理构造：也叫储存构造，是指逻辑构造的存储表示，即数据的逻辑构造在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。数据的逻辑构造和存储构造是密不可分的，一个操作算法的设计取决于所选定的逻辑构造，而算法的实现依赖于所采与的存储构造。采用不同的存储构造，其数据处理的效率是不同的。因此，在进展数据处理时，针对不同问题，选择合理的逻辑构造和存储构造非常

3、重要。3.数据构造的主要操作包括哪些？对于各种数据构造而言，他们在根本操作上是相似的，最常用的操作有：创立：建立一个数据构造；去除：去除一个数据构造；插入：在数据构造中增加新的结点；删除：把指定的结点从数据构造中删除；访问：对数据构造中的结点进展访问；更新：改变指定结点的值或改变指定的*些结点之间的关系；查找：在数据构造中查找满足一定条件的结点；排序：对数据构造中各个结点按指定数据项的值，以升序或降序重新排列。4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型Abstract Data Type 简称ADT是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的

4、数据类型，因此，不管ADT的部构造如何变化，只要其数据构造的特性不变，都不影响其外部使用。对抽象数据类型的描述一般用D,R,P)三元组表示，抽象数据类型的定义格式为：ADT数据对象D：数据关系R：根本操作P：ADT其中，D是数据对象，R是D上的关系集，P是对D的根本操作集。数据对象和数据关系的定义用伪代码来描述。根本操作的定义格式为：根本操作名参数表初始条件：操作结果：初始条件说明操作执行之前数据构造和参数应满足的条件；操作结果说明操作完成后，数据构造的变化状况和应返回的结果。5.什么是算法？算法的根本特征是什么？算法：是在有限的步骤解决数学问题的过程，是以一步接一步的方式来详细描述计算机如何

5、将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述。一个有效的算法必须满足的五个重要特性： = 1 * GB3 有穷性：算法必须能在有限的时间做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。 = 2 * GB3 确定性：算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许有二义性。 = 3 * GB3 输入：算法有0个或多个输入值，来描述算法开场前运算对象的初始情况，这是算法执行的起点或是依据。0个输入是指算法本身给出了运算对象的初始条件。 = 4 * GB3 输出：算法至少有1个或多个

6、输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。 = 5 * GB3 可行性：算法中要做的运算都是根本运算，能够被准确地进展。即算法中执行的任何计算都可以被分解为根本的运算步，每个根本的运算步都可以在有限的时间完成。6.什么是算法分析？算法分析主要考虑哪几方面的容？算法的研究与实际问题直接相关，用来解一个问题可以有很多不同的算法，他们之间的效果可能会有很大差异。算法设计者最关心的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中选择好的算法。除了要首先考虑算法的正确性外，还要分析和评价算法的性能。分析和评价算法的性能主要要考虑以下两个方面： = 1 * GB3 时间代

7、价：执行算法所消耗的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。 = 2 * GB3 空间代价：执行算法所消耗的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。7.分析下面算法的时间复杂度。1答：时间复杂度为n22时间复杂度：n3时间复杂度：4时间复杂度：n25时间复杂度：O(log2n)8.算法设计中的递归、穷举、递推和迭代等算法的根本思想是什么？递推法：是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成假设干步，找出相邻几步的关系，从而

8、到达求解问题的目的。具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i=1出发，由i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。递归法：递归策略是利用函数直接或间接地调用自身来完成*个计算过程。能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。穷举法：穷举搜索法也称穷举法或搜索法是对

9、可能是解的众多候选解按*种顺序进展 逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。迭代法：数值分析过从一个初始估计出发寻找一系列近似解来解决问题一般是解方程或者方程组的过程，为实现这一过程所使用的方法统称为迭代法。9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的根本思想是什么？分治策略的根本思想是把一个规模为n的问题划分为假设干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。贪心策略的根本思想是把一个整体最优问题分解为一系列的最优选择问题，决

10、策一旦做出，就不能再更改。它是通过假设干次的贪心选择而得出最优解或较优解的一种解题策略。动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对一样子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照*种规则进展选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。回溯策略也叫试探法，它的根本思想是：在一些问题求解进程中，先选择*一种可能情况向前探索，当发现所选用的试探性操作不是最正确选择，需退回一步，重新选择继续进展试探，

11、直到找到问题的解或者证明问题无解。分支定界策略也经常被称为分支限界策略，它的根本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的*些不可能产生最优解的分支，提高搜索效率。-. z.第二章 线性表1具有什么特征的数据构造被称为线性表？线性表是一种最常用、最简单的典型线性数据构造，应用非常广泛。线性表是由nn0个数据元素组成的一个有限序列，线性表中数据元素的个数n称为线性表的长度。当n=0时，称为空表。对于非空线性表，数据元素之间存在一对一的关系，具体特性如下：第一个数据元素没有前驱；最后一个数据元素没有后继外；其他数据元素都是首尾相接、有且只有一个前驱和后继。2如何实现线性表的顺序存

12、储构造？把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储构造的线性表简称顺序表。线性表的顺序存储构造有如下特点：线性表中所有元素所占的存储空间是连续的；线性表的逻辑顺序与物理顺序一致；数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的存储地址指第一个字节的地址，即首地址为 LOC(e1)，每一个数据元素占k个字节，则线性表中第i个元素ei在计算机存储空间中的存储地址为：LOC(ei)=LOC(e1)+(i-1)k3如何实现线性表的4种链式存储构造？数据构造中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结

13、点。每个结点分为两局部：一局部用于存放数据元素的值，称为数据域；另一局部是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。对于线性表，指针域用于指向该结点的前一个或后一个结点即前驱结点或后继结点。通过结点的指针域将n个结点按其逻辑构造连接在一起的数据存储构造，称为链式存储构造。单向链表：在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空用NULL或0表示，表示链表终止，这样的线性链表称为单向链表。下列图是单向链表示意图。firste1e2 ei en NULLNULL NULL线性表的单向链式存储循环链表：

14、将单向链表最后一个结点的指针指向头结点，这样整个链表就构成一个循环，这种链式存储构造称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL，而是指向头结点。只有头结点的循环链表称为空循环链表。下列图是带头结点的非空循环链表和空循环链表示意图。e1headen 头结点head头结点a带头结点的非空循环链表 b带头结点的空循环链表带头结点的循环链表双向链表：双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的构造下列图a所示。e2enb双向链表e1e2enc双向循环链表prev data

15、 ne*ta双向链表结点构造firstfirste1end双向循环链表：如果将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的ne*t指针与指向第一个结点，就构成了双向循环链表。下列图b和c是双向链表和双向循环表的逻辑构造示意图。图双向链表结点构造及双向链表4顺序表和线性链表分别有哪些优点和缺点？线性表的顺序存储与链式存储比拟比拟容顺序存储链式存储结点存储空间少不需要为表示结点的逻辑关系增加开销多需要增加指针域来表示结点之间的逻辑关系空间利用率低采用数组，按表的最大长度静态分配存储空间高根据表的实际长度动态分配存储空间插入、删除操作慢需要大量移动元素快仅更改指针指向，不需要移

16、动元素访问元素快直接访问慢通过指针移动才能访问实现难易程度相对容易基于数组操作，一般高级语言都提供数组类型相对困难基于指针操作5请列举出一些线性表问题的实例。= 1 * GB3按员工号排序的员工根本情况表；= 2 * GB3奥运会各项比赛日程；= 3 * GB3按*记录的学生的成绩单；等等。6. 对于顺序表和单向链表，如何实现统计重复元素个数的操作？在顺序表中实现统计重复元素个数的操作：在教材的【描述2-1】中，增加一个统计重复元素个数的成员函数：int Count(const T&*); /返回*出现的次数在教材的【描述2-2】中，增加查找重复元素个数的成员函数的实现：/实现统计重复元素个数

17、templateint LinearList:Count(const T& *)int count=0;for (int i=0; ilength; i+)if(elementi=*)count+;return count;在顺序表中实现统计重复元素个数的操作：在教材的【描述2-3】中，增加一个统计重复元素个数的成员函数：int Count(const T&*); /返回*出现的次数在教材的【描述2-4】中，增加查找重复元素个数的成员函数的实现：/实现统计重复元素个数templateint LinkList:Count(const T& *)LinkNode * p=head-ne*t;int

18、 count=0;while (p!=NULL & )if (p-data =*)count+;p=p-ne*t;return count;-. z.第3章 栈和队列1具有什么特征的数据构造被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？栈：一种插入和删除都只能在表的同一端进展的线性表。队列：一种只允许在表的一端进展插入操作，而在表的另一端进展删除操作的线性表。先进后出：元素是以e1，e2，en顺序进入数据构造，以相反的顺序即en，en-1，e1离开数据构造。栈顶：允许进展插入和删除操作的一端。栈底：栈中与栈顶相对的另一端。先进先出：元素是以e1，e2，en顺序进入数据

19、构造，以一样的顺序即e1，e2，en。 离开数据构造。队头：允许删除操作的一端。队尾：允许插入操作的一端。 2简述在顺序栈的栈顶插入一个元素的操作过程。在插入元素之前，首先要判断栈是否为满，如果栈满，返回沾满无法插入等错误提示信息；否则让top指针指向当前顺序栈的栈顶向后移动一个元素空间元素大小，将要插入的元素放入top指针指向的存单元中。3. 一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。可分为三种情况：、当只有一个存储空间时，只有一种出栈序列：1、2、3.、当有两个存储空间时，有：1、2、3， 2、1、3， 2、3、1等3种出栈序列、当存储空间大于等于三个时，有：1、2、3， 2

20、、1、3， 2、3、1， 3、2、1等4种出栈序列。4循环队列的优点是什么？在循环队列中，仅依据头尾指针相等，无法判断队列是空还是满。要解决这个问题，常用的两种方法是什么？循环队列的优点有两点：一是可以防止发生顺序队列的假上溢现象；二是充分利用队列的存储空间。两种判断队列是空还是满的方法：一是约定少用一个元素空间；二是使用计数器size记录当前队列的实际长度。5. 简述在栈中插入一个元素的操作过程。栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。6请列举出一些可以用栈和队列表示的实际问题。所有后进先出(LIFO，Las

21、t In First Out的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。所有先进先出(FIFO，First In First Out的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等。第4章 数组、字符串与广义表1.具有什么特征的数据构造被称为数组？数组可以看成是形如inde*，value的数据集合，其中，inde*是元素的索引，表示数据的逻辑位置，任意两个数

22、据的inde*都不一样；value表示数据元素的值。2.设有二维数组a56，每个元素占相邻的8个字节，存储器按字节编址，a的起始地址是1000，试计算：1数组a的最后一个元素起始地址；1000+30-1*8=1232。2按行序优先时，元素a35的起始地址；1000+3*6+5*8=11843按行列序优先时，元素a43的起始地址。1000+3*5+4*8=11523.请简述数组和矩阵的关系。矩阵是指纵横排列的二维数据表格。在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进展随机存取。但矩阵的索引通常从1而不是像数组那样从0开场，并且使用Ai，j而不是Ai，j的形式来引用矩阵

23、中的元素。4.矩阵有哪些根本运算？矩阵的操作包括转置、加法、减法和乘法等。5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储技术？稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。采用压缩存储技术主要是为了节省空间。6.设A和B是稀疏矩阵，都以三元组作为存储构造，请写出矩阵相加的算法C=A+B。/稀疏矩阵的三元组表示#include using namespace std;#define M 50#define N 50#define Ma*Size 20typedef int ElemType; typedef structint r;int c;ElemType d; Tup

24、Node;typedef structint rows;int cols;int nums;TupNode dataMa*Size; TSMatri*;int AMN,BMN;/建立三元组void CreateMat(int AMN,TSMatri* &t,int row,int col)int i,j;t.rows=row;t.cols=col;t.nums=0;for(i=0;iM;i+) for(j=0;jN;j+)if(Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+; /矩阵相加int MatAdd

25、(TSMatri* &a,TSMatri* &b,TSMatri* &c) int i=0,j=0,k=0;ElemType v;if(a.rows!=b.rows|a.cols!=b.cols) return 0;c.rows=a.rows;c.cols=a.cols;while(ia.nums & jb.nums)if(a.datai.r=b.dataj.r)if(a.datai.cb.dataj.c) c.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;j+;k+; elsev=a.datai.d+b.dataj.d;i

26、f(v!=0)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=v;k+;i+;j+; else if(a.datai.rb.dataj.r)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+; elsec.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;j+;k+; if (i=a.nums)while (jb.nums)c.datak.r=b.dataj.r;c.datak.c=b.dataj.

27、c;c.datak.d=b.dataj.d;j+;k+;if (j=b.nums)while (ia.nums)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+;c.nums=k; return 1; /输出三元组void DispMat(TSMatri* t) int i;if(t.nums=0) cout此矩阵所有元素都为endl;return;coutt.rowstt.colstt.numsendl;cout-endl;for(i=0;it.nums;i+)coutt.datai.rtt.datai.ctt

28、.datai.dendlendl; /主函数int main()int row,col,i,j;TSMatri* a,b,c;coutrowcol;cout请输入矩阵A的元素：n;for(i=0;irow;i+)for(j=0;jAij; cout请输入矩阵B的元素：n;for(i=0;irow;i+)for(j=0;jBij; CreateMat(A,a,row,col);CreateMat(B,b,row,col); cout矩阵A的三元组表示为：n;DispMat(a);cout矩阵B的三元组表示为：n;DispMat(b);if(MatAdd(a,b,c) cout矩阵A、B相加后得到

29、的三元组表示为：n;DispMat(c);return 0;7.简述字符串与一维字符型数组的区别与联系。字符串简称串，它是一种以字符为元素的特殊线性表。字符串可以看成是以字符为元素的一维数组。具体实现时，在C/C+中的字符串使用为字符型数组来表示。为了便于确定字符串的结尾，在字符型数组中使用0就是0作为字符串的截止符。8.列举一些需要进展字符串模式匹配的应用场景。例如，在文本编辑中经常要查找*一特定单词或者一段话在整篇文章中出现的位置，按照查找*个学生、员工、居民。有效的模式匹配能极提高文本编辑程序的能力。9.列举几个字符串的其他操作。求字符串中*个子串出现的次数，删除满足条件的子串，字符串字

30、符移位等。10.什么是广义表？广义表与线性表的区别是什么？广义表又称列表，是由nn0个元素组成的有穷序列：GL=e1，e2，en，但与线性表不同的是，广义表中的元素允许以不同的形式出现：它可以是一个原子逻辑上不能再分解的元素，也可以是另一个广义表。11.一个广义表是(a, (a, b, c), d, e, (m, n),(w, (i, j), *)，请问该广义表的长度、深度分别是多少？请画出该广义表的单链表存储构造示意图。该广义表的深度是3，长度是6。该广义表的单链表存储构造示意图如下：12请列举出一些可以归纳成数组、矩阵、字符串和广义表数据构造的实际问题。线性表的顺序存储、学生编号和的问题、

31、各班级的学生编号和的问题等，都可以归结为数组。不同物品所需原材料的数量、不同产地原材料的价格、不同类型的住宅需要的物品数量等，不同学生的计算机成绩，不同职工的工资等都可以归结为矩阵。学生的和*、学校或各单位的名称、国家名称、一篇文章、一个高级语言源程序等，都可归结为字符串。应用高斯消元法求解方程组可以归结为广义表。-. z.第5章 树和二叉树1. 请简述树、二叉树、满二叉树和完全二叉树的构造特性。树：只有最顶层的结点没有前驱，其余结点都有且只有一个前驱；一个结点可以没有后继，也可以有一个或多个后继。二叉树：一种特殊形态的树，每个结点至多有两个后继。满二叉树：一种特殊形态的二叉树，除了最后一层的

32、结点为叶子结点外其它结点都有左、右两棵子树的二叉树。完全二叉树：一种特殊形态的二叉树，其结点与一样深度的满二叉树中的结点编号完全一致，即对于深度为k的完全二叉树，其前k-1层与深度为k的满二叉树的前k-1层完全一样，只是在第k层上有可能缺少右边假设干个结点。2. 请解释结点的度、树的度、结点的层、树的深度、分支、路径、路径长度、树的路径长度、叶子结点、分支结点、部结点、孩子、双亲、兄弟、堂兄弟、祖先、子、有序树、无序树和森林等根本术语的含义。结点的度和树的度：一个结点的后继的数目称为该结点的度，树中各结点度的最大值称为树的度。结点的层和树的深度：树的根结点所在的层为第1层，其余结点的层等于其前

33、驱结点的层加1，树中各结点的层的最大值称为树的深度。分支、路径、路径长度和树的路径长度：从一个结点到其后继结点之间的连线称为一个分支，从一个结点*到另一个结点Y所经历的所有分支构成结点*到结点Y的路径，一条路径上的分支数目称为路径长度，从树的根结点到其他各个结点的路径长度之和称为树的路径长度。叶子结点、分支结点和部结点：树中度为0的结点称为叶子结点或终端结点，度不为0的结点称为分支结点或非终端结点，除根结点以外的分支结点也称为部结点。孩子和双亲：在树中，一个结点的后继结点称为该结点的孩子，相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩子结点的双亲、其双亲结点的孩子。兄弟和堂兄弟：

34、同一双亲的孩子结点之间互称为兄弟，不同双亲但在同一层的结点之间互称为堂兄弟。祖先和子：从树的根结点到*一个结点*的路径上经历的所有结点包括根结点但不包括结点*称为结点*的祖先，以*一结点*为根的子树上的所有非根结点即除结点*外称为结点*的子。有序树和无序树：对于树中的任一结点，如果其各棵子树的相对次序被用来表示数据之间的关系，即交换子树位置会改变树所表示的容，则称该树为有序树；否则称为无序树。森林：mm0棵互不相交的树的集合就构成了森林。3. 请简述二叉树的五条根本性质。性质1：在二叉树的第i层上至多有2i-1个结点i1。性质2：深度为k的二叉树至多有2k-1个结点。性质3：在二叉树中，假设度

35、为0的结点即叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。性质4：具有n个结点的完全二叉树其深度为log2n+1其中log2n表示不大于log2n的最大整数。性质5：采用顺序编号的完全二叉树具有如下性质：假设一个分支结点的编号为i，则其左子树的根结点即左孩子结点编号为2*i，右子树的根结点即右孩子结点编号为2*i+1；反之，假设一个非根结点的编号为i，则其双亲结点的编号为i/2其中i/2表示不大于i/2的最大整数。4. 请简述二叉树的常用操作及各操作的含义。创立一棵空二叉树：创立一棵没有任何结点的二叉树。在顺序表示中，根据树的深度为结点分配存；在二叉链表表示中，将指向根结点的指针赋

36、值为NULL。删除一棵二叉树：将二叉树各结点所占据的存释放。清空二叉树：将二叉树的所有结点删除，使之成为一棵空二叉树。以指定元素值创立根结点：创立根结点，并以指定值作为根结点的元素值。将一个结点作为指定结点的左孩子插入：根据指定元素值生成一个新结点，并将其作为指定结点的左孩子。将一个结点作为指定结点的右孩子插入：根据指定元素值生成一个新结点，并将其作为指定结点的右孩子。先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。中序遍历二叉树：也称为

37、中根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。后序遍历二叉树：也称为后根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。逐层遍历二叉树：从第1层开场依次对每层中的结点按照从左至右的顺序进展访问。获取指定结点的双亲结点：根据指定结点获取其双亲结点。在顺序表示中，可以直接根据指定结点的位置计算双亲结点的位置；在二叉链表表示中，则需要从根结点开场遍历二叉树直至找到指定结点的双亲结点。删除以指定结点为

38、根的子树：将以指定结点为根结点的子树上的所有结点包括指定结点删除。按关键字查找结点：按照*种规则先序、中序、后序或逐层依次访问二叉树中的每一结点，直至找到与关键字匹配的结点。判断二叉树是否为空：判断一棵二叉树是否为空二叉树。修改指定结点的元素值：将指定结点的元素值修改为指定值。计算二叉树的深度：按照*种规则依次访问二叉树中的每一结点，计算各结点所在层的最大值。计算二叉树的叶子结点数：按照*种规则依次访问二叉树中的每一结点，计算度为0的结点数。5. 请简述顺序表示的二叉树中各结点的编号规则。顺序表示的二叉树中各结点的编号与一样深度的完全二叉树中对应结点的编号一样。6. 请简述二叉链表表示和三叉链

39、表表示的二叉树中结点的构造。在二叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点不包含指向其双亲结点的指针；在三叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点也包含指向其双亲结点的指针。7. 请简述二叉树的四种遍历方式及每一种遍历方式中结点的访问顺序。先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。中序遍历二叉树：也称为中根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右子树；对

40、于左、右子树中的结点仍然是按照中序遍历方式访问。后序遍历二叉树：也称为后根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。逐层遍历二叉树：从第1层开场依次对每层中的结点按照从左至右的顺序进展访问。8. 一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、H、I，中序遍历结果为D、G、B、A、E、C、H、F、I，请给出该二叉树的后序遍历结果。G、D、B、E、H、I、F、C、A9. 一棵二叉树的中序遍历结果为D、G、B、A、E、C、H、F、I，后序遍历结果为G、D、B、E、H、I、F、C、A，请给

41、出该二叉树的先序遍历结果。A、B、D、G、C、E、F、H、I10. 一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、H、I，后序遍历结果为G、D、B、E、H、I、F、C、A，请给出该二叉树的中序遍历结果。D、G、B、A、E、C、H、F、I11. 请简述哈夫曼树的构造特性。哈夫曼树，又称最优二叉树，是指在由n个叶子结点构成的一类二叉树中具有最短带权路径长度的二叉树。12. 请简述结点的权、结点的带权路径长度、树的带权路径长度等根本术语的含义。结点的权和结点的带权路径长度：在实际应用中，往往给树中的结点赋予一个具有*种意义的实数，该实数就称为是结点的权。结点的带权路径长度是指从树根到该结点的

42、路径长度与结点的权的乘积。树的带权路径长度：是指树中所有叶子结点的带权路径长度之和，记为其中，n为叶子结点的数目，Wi为第i个叶子结点的权，Li为根结点到第i个叶子结点的路径长度，可知WiLi为第i个叶子结点的带权路径长度。13. 请简述哈夫曼树的构造方法。哈夫曼树的构造方法如下：an个权值为Wii=1, 2, , n的结点，将每个结点作为根结点生成n棵只有根结点的二叉树Ti，形成森林F=T1, T2, , Tn。b从森林F中选出根结点权值最小的两棵二叉树Tp和Tq，并通过添加新的根结点将它们合并为一棵新二叉树，新二叉树中Tp和Tq分别作为根结点的左子树和右子树，且根结点的权值等于Tp和Tq两

43、棵二叉树的根结点权值之和。以合并后生成的新二叉树替代森林F中的原有二叉树Tp和Tq。重复该步骤直至森林F中只存在一棵二叉树。14. 请简述哈夫曼码的作用及其编码方法。哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间，其具体方法为：a以要编码的字符集C=c1, c2, ,作为叶子结点、字符出现的频度或次数W=w1, w2, , wn作为结点的权，构造哈夫曼树。b规定哈夫曼树中，从根结点开场，双亲结点到左孩子结点的分支标为0，双亲结点到右孩子结点的分支标为1。从根结点到*一叶子结点经过的分支形成的编码即是该叶子结点所对应字符的哈夫曼码。15. 请简述树的四种常用表示方式。

44、双亲表示法：在孩子结点中设置一个指针域记录其双亲结点的存储位置。孩子表示法：在双亲结点中设置指向孩子结点的指针域来表示一棵树。孩子双亲表示法：综合了孩子表示法和双亲表示法的特点，既在孩子结点中设置记录双亲结点位置的指针域，又在双亲结点中设置记录孩子结点位置的指针域。孩子兄弟表示法：又称为二叉链表表示法，与二叉树的二叉链表表示法存储构造完全一样，只是结点中指针域的含义有所不同一个指针域指向该结点的第一个孩子结点，另一个指针域指向该结点的下一个兄弟结点。16. 请简述森林转换为二叉树的具体步骤。将森林中的每棵树都用二叉链表表示法表示，并将各棵二叉树的根结点看做是兄弟结点，在它们之间加上连线；将结点

45、到第一个孩子结点的连线作为左子树的边，结点到兄弟结点的连线作为右子树的边。17. 请简述二叉树转化为树或森林的具体步骤。将一个结点左子树的边作为该结点指向第一个孩子结点的连线，右子树的边作为该结点到兄弟结点的连线；在双亲结点和它的各孩子结点之间加上连线，并删除兄弟结点之间的连线，得到一棵树或一个包含假设干棵树的森林。-. z.第6章 图1. 请简述图的构造特性。图G由顶点图常将结点称为顶点的非空有限集合V和边的集合E组成，记为G=(V, E)。每一个顶点偶对就是图中的一条边，所以，E用于表示V上的连接关系。在一个图中，至少要包含一个顶点，但可以没有任何边。2. 请解释有向图、无向图、弧、弧尾、

46、弧头、顶点的度、顶点的入度、顶点的出度、路径、路径长度、回路、简单回路、连通图、单向连通图、强连通图、子图、连通分量、强连通分量、权、带权图、生成树、最小生成树等根本术语的含义。有向图、弧、弧尾和弧头：假设E(G)中的顶点偶对是有序的，则这些有序偶对就形成了有向边，此时图G称为有向图。其中，有向边也简称为弧。在有向图G中，对于一条从顶点vi到顶点vj的弧，记为并有E(G)，称vi为弧尾，vj为弧头。无向图：假设E(G)中的顶点偶对是无序的，则这些无序偶对就形成了无向边，此时图G称为无向图。顶点的度、顶点的入度和顶点的出度：在无向图中，与顶点vi相关联的边的数目称为顶点vi的度。在有向图中，以顶

47、点vi为弧头的弧的数目称为顶点vi的入度；以顶点vi为弧尾的弧的数目称为vi的出度；顶点vi的入度和出度之和称为vi的度。路径和路径长度：在图G中，假设存在一个顶点序列(, , )，使得对于任意0jn-1有假设G为有向图或假设G为无向图，则该序列是从顶点到顶点的一条路径。一条路径中边的数目称为路径长度。回路和简单回路：在一条路径中，假设组成路径的顶点序列中第一个顶点与最后一个顶点一样，则该路径称为回路或环；在一个回路中，假设除第一个顶点与最后一个顶点外，其他顶点只出现一次，则该回路称为简单回路或简单环。连通图：无向图G中，假设任意两个顶点都是连通的，则称G为连通图。单向连通图和强连通图：有向图

48、G中，假设任意两个顶点都是单向连通的，则称G是单向连通图；假设任意两个顶点都是强连通的，则称G为强连通图。子图：对于图G、G，假设满足且，则G是G的子图。连通分量和强连通分量：一个无向图的极通子图称为该无向图的连通分量；一个有向图的极大强连通子图称为该有向图的强连通分量。权和带权图：可以为一个图中的每条边标上一个具有*种意义的实数，该实数就称为是边的权。边上带权的图就称为带权图。生成树和最小生成树：假设无向图G的一个子图G是一棵包含图G所有顶点的树，则G称为图G的生成树。在所有形式的生成树中，边上的权之和最小的生成树，称为最小生成树。3. 请列举可以用图来描述的实际问题。请参考例6-1和例6-

49、2。4. 请简述图的根本操作及各操作的含义。创立图：创立不包含任何顶点和边的空图。对图作深度优先遍历：类似于树的先序遍历，即从*一个顶点开场访问，访问后将该顶点去除得到假设干子图，对每个子图再依次进展深度优先遍历。对图作广度优先遍历：类似于树的逐层遍历，即先从*一个顶点开场访问，然后访问与该顶点相邻接且未被访问过的顶点集V1(G)，再访问与V1(G)中顶点相邻接且未被访问过的顶点集V2(G)，重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图，还要从*一个未被访问的顶点开场重复上一过程，直至所有顶点访问完毕。获取顶点数目：获取图中所包含的顶点的数目。获取边的数目：获取图

50、中所包含的边的数目。获取与指定顶点相关联的第一条边：对无向图，获取到与指定顶点相关联的第一条边；对有向图，获取到以指定顶点作为弧尾的第一条弧。不同表示方法获取到的结果会有所不同邻接矩阵法按顶点编号顺序，邻接压缩表和邻接链表按边的添加顺序。获取与指定边有一样关联顶点的下一条边：对无向图，获取到与指定边(nV1,nV2) 有一样关联顶点nV1的下一条边；对有向图，获取到与指定弧有一样弧尾nV1的下一条弧。不同表示方法获取到的结果会有所不同邻接矩阵法按顶点编号顺序，邻接压缩表和邻接链表按边的添加顺序。添加一个顶点：向图中添加一个新顶点。添加一条边：对无向图，向图中添加一条新边；对有向图，向图中添加一

51、条新弧。获取一个顶点中存储的数据：根据顶点编号获取该顶点中存储的数据。判断一条边是否存在：对无向图，判断两个顶点nV1和nV2之间是否存在边；对有向图，判断是否存在从顶点nV1到顶点nV2的弧。设置一条边的权：对无向图，设置指定边(nV1,nV2)上的权；对有向图，设置指定弧上的权。获取一条边的权：对无向图，获取指定边(nV1,nV2)上的权；对有向图，获取指定弧上的权。5. 请简述图的三种常用表示方法。邻接矩阵法：用矩阵来表示各顶点之间的连接关系。对于有n个顶点的图G=(V, E)，其邻接矩阵A为n*n的方阵，元素Aij0i,jn定义为：其中，wij为边(vi, vj)或上的权。邻接压缩表：

52、邻接矩阵的一种压缩表示形式，使用3个顺序表来表示图中顶点之间的连接关系和权。设图中共有n个顶点v0, v1, , vn-1，3个顺序表分别为s、w和h。在s中依次记录与顶点vii = 0, 1, , n-1相关联的顶点；在w中依次记录s中存储的各条边的权；在h中依次记录与顶点vi相关联的顶点在s中的起始存储位置。邻接链表：图的一种链式存储构造。每个顶点中设置一个指向链表头的指针，在链表中保存与该顶点相邻接的顶点信息包括顶点位置及两个顶点形成的边的权。6. 请简述图的两种常用遍历方法及每一种遍历方法中结点的访问顺序。广度优先遍历：类似于树的逐层遍历，即先从*一个顶点开场访问，然后访问与该顶点相邻

53、接且未被访问过的顶点集V1(G)，再访问与V1(G)中顶点相邻接且未被访问过的顶点集V2(G)，重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图，还要从*一个未被访问的顶点开场重复上一过程，直至所有顶点访问完毕。深度优先遍历：类似于树的先序遍历，即从*一个顶点开场访问，访问后将该顶点去除得到假设干子图，对每个子图再依次进展深度优先遍历。7. 请列举最小生成树和最短路径可以用于解决什么应用问题。请参考例6-1和例6-2。8. 请简述Prim算法的作用和具体步骤。Prim算法用于最小生成树问题求解。对于有n个顶点的图G=(V, E)，Prim算法从空树T开场，按照以下规则

54、将n个顶点和n-1条边依次添加到树中，形成最小生成树：a从*一顶点v0开场，将该顶点作为树的根结点参加到T中，使得T中的数据元素集合D=v0，数据元素关系集合R=。b对于一个顶点在集合D中、另一个顶点在集合V-D中的那些边，找出权最小的一条边，将该边在集合V-D中的顶点vii=1,2,n-1参加到集合D中，并将顶点间关系jD(vj,vi)+D(vi,vk)，则说明路径(vj, , vi, , vk)的长度更短，此时令D(vj,vk)=D(vj,vi)+D(vi,vk)并更新从顶点vj到顶点vk的路径。-. z.第7章 排序算法1. 请简述排序的作用。排序的作用是将一个待排序元素集合按关键字递增

55、或递减顺序整理为一个有序序列。2. 请简述稳定排序和不稳定排序的含义。假设采用*种排序算法对任一组元素进展排序，在排序前后，那些具有一样关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。3. 请简述各种排序算法的适用围。排序算法的适用围如下：a直接插入排序、简单项选择择排序和冒泡排序都是简单排序算法，它们的时间复杂度和空间复杂度分别为O(n2)和O(1)。假设待排序元素数量n较小，可以选用直接插入排序和冒泡排序。另外，当待排序元素根本有序时，也应选用直接插入排序和冒泡排序，此时时间复杂度都能到达O(n)。假设元素本身数据量较大，元素移动操作代价较高，则应

56、选用平均移动元素次数最少的简单项选择择排序。希尔排序是对直接插入排序算法的改良，大大降低了时间复杂度，但它是一种不稳定的排序算法。b堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况，当待排序元素数量n较小时，它们的性能有可能劣于简单排序算法。因此，在实际应用时，快速排序算法和归并排序算法经常与简单排序算法结合使用例如，可以先用快速排序算法将集合划分为规模更小的子集合，对于元素数量较小的子集合，则用直接插入排序算法进展排序。在所有平均时间复杂度为O(nlog2n)的算法中，尽管快速排序在最坏情况下时间复杂度较高，但它通常被认为是平均性能最好的一种算法，并且通过优化可以降低最坏情况出

57、现的概率。归并排序是一种稳定的排序算法，其时间性能一般要优于堆排序，但它所需要的辅助空间较多，当应用环境要求排序前后具有一样值的元素相对次序不能改变时可以考虑使用。堆排序所需的辅助空间最少，当可用空间非常有限时可以考虑使用。c箱排序和基数排序的时间复杂度最低，但它们的空间复杂度最高。箱排序主要适用于待排序元素长度即d值较小的情况，在实际中应用不多；基数排序是箱排序的改良，主要适用于整数或字符串的排序，或者与其他排序算法结合进展实数的排序例如，可以先用基数排序算法按整数局部将元素分成假设干个子集合，再对每个子集合应用直接插入排序算法进展排序。5. 请简述插入排序、选择排序、交换排序、归并排序和分

58、配排序的原理。插入排序：按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至所有元素都插入完毕。选择排序：每次从待排序的元素中选择具有最小或最大关键字的元素放到已排序序列的尾部或头部，直至所有元素都排序完毕。交换排序：从待排序的元素中选择两个次序相反的元素进展交换，直至任意两个元素的次序都正确。K路归并排序：每次将KK2个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含所有待排序元素的有序序列。分配排序：根据元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。5. 请简述直接插入排序的具体步骤。直接插入排序是一

59、种简单排序算法，其具体步骤为：a初始已排序区为空，将第一个待排序的元素插入到已排序区中。b将后继每一个待排序的元素依次取出，并按照关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。c重复上一步骤直至将待排序的元素都插入到已排序序列中。6. 请简述希尔排序的具体步骤。希尔排序，又称为缩小增量排序，其具体步骤为：a令n为待排序元素数目，设置增量序列d0, d1, , dk，其中nd0d1dk=1。b按增量dii依次取值为0, 1, , k将待排序元素分为di组，将所有下标距离为di的倍数的元素放在同一组中，即R1, R1+ di, R1+2*di, 在第一组中，R2, R2+ di, R

60、2+2*di, 在第二组中，依此类推。然后分别在各组进展直接插入排序。c重复上一步骤直至最后以1为增量对所有待排序元素进展直接插入排序。7. 请简述简单项选择择排序的具体步骤。简单项选择择排序是一种简单排序算法，其具体步骤为：a初始已排序区为空，待排序区包含所有待排序元素。b从待排序区中选择具有最小关键字的元素，将其与待排序区的第一个元素交换位置，并将该位置加到已排序区中。c重复上一步骤直至所有元素都排序完毕。8. 请简述堆的定义和堆的构建过程。堆的定义：对于包含n个元素的集合R=R1, R2, , Rn，假设满足：1RiR2*i且RiR2*i+1即R所表示的完全二叉树中每一棵子树的根结点的值