数据结构算法与应用习题参考答案.docx
《数据结构算法与应用习题参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构算法与应用习题参考答案.docx（46页珍藏版）》请在冰点文库上搜索。
数据结构算法与应用习题参考答案
第1章概论
1.数据、数据元素、数据结构、数据类型的含义分别是什么？
数据：
对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。
数据元素：
数据的基本单位，在计算机程序中通常作为一个整体考虑。
数据结构：
数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。
数据类型：
数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。
数据类型包含取值范围和基本运算等概念。
2.什么是数据的逻辑结构？
什么是数据的物理结构？
数据的逻辑结构与物理结构的区别和联系是什么？
逻辑结构：
数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。
数据的逻辑结构包含下面两个方面的信息：
数据元素的信息；
各数据元素之间的关系。
物理结构：
也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。
数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。
采用不同的存储结构，其数据处理的效率是不同的。
因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。
3.数据结构的主要操作包括哪些？
对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：
创建：
建立一个数据结构；
清除：
清除一个数据结构；
插入：
在数据结构中增加新的结点；
删除：
把指定的结点从数据结构中删除；
访问：
对数据结构中的结点进行访问；
更新：
改变指定结点的值或改变指定的某些结点之间的关系；
查找：
在数据结构中查找满足一定条件的结点；
排序：
对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。
4.什么是抽象数据类型？
如何定义抽象数据类型？
抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。
对抽象数据类型的描述一般用（D,R,P）三元组表示，抽象数据类型的定义格式为：
ADT<抽象数据类型名>
{
数据对象D：
<数据对象的定义>
数据关系R：
<数据关系的定义>
基本操作P：
<基本操作的定义>
｝ADT<抽象数据类型名>
其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。
数据对象和数据关系的定义用伪代码来描述。
基本操作的定义格式为：
基本操作名（参数表）
初始条件：
<初始条件描述>
操作结果：
<操作结果描述>
初始条件说明操作执行之前数据结构和参数应满足的条件；操作结果说明操作完成后，数据结构的变化状况和应返回的结果。
5.什么是算法？
算法的基本特征是什么？
算法：
是在有限的步骤内解决数学问题的过程，是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述。
一个有效的算法必须满足的五个重要特性：
有穷性：
算法必须能在有限的时间内做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。
确定性：
算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许有二义性。
输入：
算法有0个或多个输入值，来描述算法开始前运算对象的初始情况，这是算法执行的起点或是依据。
0个输入是指算法本身给出了运算对象的初始条件。
输出：
算法至少有1个或多个输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。
可行性：
算法中要做的运算都是基本运算，能够被精确地进行。
即算法中执行的任何计算都可以被分解为基本的运算步，每个基本的运算步都可以在有限的时间内完成。
6.什么是算法分析？
算法分析主要考虑哪几方面的内容？
算法的研究与实际问题直接相关，用来解一个问题可以有很多不同的算法，他们之间的效果可能会有很大差异。
算法设计者最关心的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中选择好的算法。
除了要首先考虑算法的正确性外，还要分析和评价算法的性能。
分析和评价算法的性能主要要考虑以下两个方面：
时间代价：
执行算法所耗费的时间。
一个好的算法首先应该比其他算法的运行时间代价要小。
算法的时间代价的大小用算法的时间复杂度来度量。
空间代价：
执行算法所耗费的存储空间，主要是辅助空间。
算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。
算法的空间代价的大小用算法的空间复杂度来度量。
7.分析下面算法的时间复杂度。
（1）答：
时间复杂度为n2
（2）时间复杂度：
n
（3）时间复杂度：
（4）时间复杂度：
n2
（5）时间复杂度：
O（log2n）
8.算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？
递推法：
是利用问题本身所具有的一种递推关系求解问题的一种方法。
它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。
具有如下性质的问题可以采用递推法：
当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。
因此，程序可以从i=0或i=1出发，由已知i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。
递归法：
递归策略是利用函数直接或间接地调用自身来完成某个计算过程。
能采用递归描述的算法通常有这样的特征：
为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。
穷举法：
穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。
迭代法：
数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。
9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。
分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。
它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。
不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。
而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
回溯策略也叫试探法，它的基本思想是：
在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略，它的基本思想是：
首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。
第二章线性表
1．具有什么特征的数据结构被称为线性表？
线性表是一种最常用、最简单的典型线性数据结构，应用非常广泛。
线性表是由n（n
0）个数据元素组成的一个有限序列，线性表中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
对于非空线性表，数据元素之间存在一对一的关系，具体特性如下：
第一个数据元素没有前驱；
最后一个数据元素没有后继外；
其他数据元素都是首尾相接、有且只有一个前驱和后继。
2．如何实现线性表的顺序存储结构？
把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺序表。
线性表的顺序存储结构有如下特点：
线性表中所有元素所占的存储空间是连续的；
线性表的逻辑顺序与物理顺序一致；
数组中的每一个元素的位置可以用公式来确定。
假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为LOC（e1），每一个数据元素占k个字节，则线性表中第i个元素ei在计算机存储空间中的存储地址为：
LOC（ei）=LOC（e1）+（i-1）k
3．如何实现线性表的4种链式存储结构？
数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。
每个结点分为两部分：
一部分用于存放数据元素的值，称为数据域；另一部分是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。
对于线性表，指针域用于指向该结点的前一个或后一个结点（即前驱结点或后继结点）。
通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为链式存储结构。
单向链表：
在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空（用NULL或0表示），表示链表终止，这样的线性链表称为单向链表。
下图是单向链表示意图。
线性表的单向链式存储
循环链表：
将单向链表最后一个结点的指针指向头结点，这样整个链表就构成一个循环，这种链式存储结构称为单向循环链表，简称循环链表。
头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL，而是指向头结点。
只有头结点的循环链表称为空循环链表。
下图是带头结点的非空循环链表和空循环链表示意图。
带头结点的循环链表
双向链表：
双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。
双向链表结点的结构下图（a）所示。
双向循环链表：
如果将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的next指针与指向第一个结点，就构成了双向循环链表。
下图（b）和（c）是双向链表和双向循环表的逻辑结构示意图。
图双向链表结点结构及双向链表
4．顺序表和线性链表分别有哪些优点和缺点？
线性表的顺序存储与链式存储比较
比较内容
顺序存储
链式存储
结点存储空间
少（不需要为表示结点的逻辑关系增加开销）
多（需要增加指针域来表示结点之间的逻辑关系）
空间利用率
低（采用数组，按表的最大长度静态分配存储空间）
高（根据表的实际长度动态分配存储空间）
插入、删除操作
慢（需要大量移动元素）
快（仅更改指针指向，不需要移动元素）
访问元素
快（直接访问）
慢（通过指针移动才能访问）
实现难易程度
相对容易（基于数组操作，一般高级语言都提供数组类型）
相对困难（基于指针操作）
5．请列举出一些线性表问题的实例。
按员工号排序的员工基本情况表；
奥运会各项比赛日程；
按学号记录的学生的成绩单；
等等。
6.对于顺序表和单向链表，如何实现统计重复元素个数的操作？
在顺序表中实现统计重复元素个数的操作：
在教材的【描述2-1】中，增加一个统计重复元素个数的成员函数：
intCount（constT&x）;一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。
可分为三种情况：
①、当只有一个存储空间时，只有一种出栈序列：
1、2、3.
②、当有两个存储空间时，有：
1、2、3，2、1、3，2、3、1等3种出栈序列
③、当存储空间大于等于三个时，有：
1、2、3，2、1、3，2、3、1，3、2、1等4种出栈序列。
4．循环队列的优点是什么？
在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。
要解决这个问题，常用的两种方法是什么？
循环队列的优点有两点：
一是可以避免发生顺序队列的“假上溢”现象；二是充分利用队列的存储空间。
两种判断队列是“空”还是“满”的方法：
一是约定少用一个元素空间；二是使用计数器size记录当前队列的实际长度。
5.简述在链接栈中插入一个元素的操作过程。
链接栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。
6．请列举出一些可以用栈和队列表示的实际问题。
所有“后进先出”（LIFO，LastInFirstOut）的实际问题都可以用栈表示。
栈的应用主要有：
数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。
所有“先进先出”（FIFO，FirstInFirstOut）的实际问题都可以用队列表示。
如日常中的排队问题，队列的应用主要有：
操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等。
第4章数组、字符串与广义表
1.具有什么特征的数据结构被称为数组？
数组可以看成是形如（index，value）的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；value表示数据元素的值。
2.设有二维数组a[5][6]，每个元素占相邻的8个字节，存储器按字节编址，已知a的起始地址是1000，试计算：
（1）数组a的最后一个元素起始地址；
1000+（30-1）*8=1232。
（2）按行序优先时，元素a[3][5]的起始地址；
1000+（3*6+5）*8=1184
（3）按行列序优先时，元素a[4][3]的起始地址。
1000+（3*5+4）*8=1152
3.请简述数组和矩阵的关系。
矩阵是指纵横排列的二维数据表格。
在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。
但矩阵的索引通常从1而不是像数组那样从0开始，并且使用A（i，j）而不是A[i，j]的形式来引用矩阵中的元素。
4.矩阵有哪些基本运算？
矩阵的操作包括转置、加法、减法和乘法等。
5.稀疏矩阵的特点是什么？
为什么要对稀疏矩阵采用压缩存储技术？
稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。
采用压缩存储技术主要是为了节省空间。
6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+B。
=i;[].c=j;
[].d=A[i][j];++;
}
}
}
}
==[j].r）
{
if[i].c<[j].c）
{
[k].r=[i].r;
[k].c=[i].c;
[k].d=[i].d;
i++;k++;
}
elseif[i].c>[j].c）
{
[k].r=[j].r;
[k].c=[j].c;
[k].d=[j].d;
j++;k++;
}
else
{
v=[i].d+[j].d;
if（v!
=0）
{
[k].r=[i].r;
[k].c=[i].c;
[k].d=v;
k++;
}
i++;j++;
}
}
elseif[i].r<[j].r）
{
[k].r=[i].r;
[k].c=[i].c;
[k].d=[i].d;
i++;k++;
}
else
{
[k].r=[j].r;
[k].c=[j].c;
[k].d=[j].d;
j++;k++;
}
}
if（i==
while（j<
{
[k].r=[j].r;
[k].c=[j].c;
[k].d=[j].d;
j++;k++;
}
if（j==
while（i<
{
[k].r=[i].r;
[k].c=[i].c;
[k].d=[i].d;
i++;k++;
}
=k;
return1;
}
<<'\t'<<[i].c<<'\t'<<[i].d<}
述字符串与一维字符型数组的区别与联系。
字符串简称串，它是一种以字符为元素的特殊线性表。
字符串可以看成是以字符为元素的一维数组。
具体实现时，在C/C++中的字符串使用为字符型数组来表示。
为了便于确定字符串的结尾，在字符型数组中使用\0（就是0）作为字符串的截止符。
8.列举一些需要进行字符串模式匹配的应用场景。
例如，在文本编辑中经常要查找某一特定单词或者一段话在整篇文章中出现的位置，按照姓名查找某个学生、员工、居民。
有效的模式匹配能极大地提高文本编辑程序的能力。
9.列举几个字符串的其他操作。
求字符串中某个子串出现的次数，删除满足条件的子串，字符串字符移位等。
10.什么是广义表？
广义表与线性表的区别是什么？
广义表又称列表，是由n（n≥0）个元素组成的有穷序列：
GL=（e1，e2，……en），但与线性表不同的是，广义表中的元素允许以不同的形式出现：
它可以是一个原子（逻辑上不能再分解的元素），也可以是另一个广义表。
11.一个广义表是（a,（a,b,c）,d,e,（m,n）,（w,（i,j）,x）），请问该广义表的长度、深度分别是多少？
请画出该广义表的单链表存储结构示意图。
该广义表的深度是3，长度是6。
该广义表的单链表存储结构示意图如下：
12．请列举出一些可以归纳成数组、矩阵、字符串和广义表数据结构的实际问题。
线性表的顺序存储、学生编号和姓名的问题、各班级的学生编号和姓名的问题等，都可以归结为数组。
不同物品所需原材料的数量、不同产地原材料的价格、不同类型的住宅需要的物品数量等，不同学生的计算机成绩，不同职工的工资等都可以归结为矩阵。
学生的姓名和学号、学校或各单位的名称、国家名称、一篇文章、一个高级语言源程序等，都可归结为字符串。
应用高斯消元法求解方程组可以归结为广义表。
第5章树和二叉树
1.请简述树、二叉树、满二叉树和完全二叉树的结构特性。
树：
只有最顶层的结点没有前驱，其余结点都有且只有一个前驱；一个结点可以没有后继，也可以有一个或多个后继。
二叉树：
一种特殊形态的树，每个结点至多有两个后继。
满二叉树：
一种特殊形态的二叉树，除了最后一层的结点为叶子结点外其它结点都有左、右两棵子树的二叉树。
完全二叉树：
一种特殊形态的二叉树，其结点与相同深度的满二叉树中的结点编号完全一致，即对于深度为k的完全二叉树，其前k-1层与深度为k的满二叉树的前k-1层完全一样，只是在第k层上有可能缺少右边若干个结点。
2.请解释结点的度、树的度、结点的层、树的深度、分支、路径、路径长度、树的路径长度、叶子结点、分支结点、内部结点、孩子、双亲、兄弟、堂兄弟、祖先、子孙、有序树、无序树和森林等基本术语的含义。
结点的度和树的度：
一个结点的后继的数目称为该结点的度，树中各结点度的最大值称为树的度。
结点的层和树的深度：
树的根结点所在的层为第1层，其余结点的层等于其前驱结点的层加1，树中各结点的层的最大值称为树的深度。
分支、路径、路径长度和树的路径长度：
从一个结点到其后继结点之间的连线称为一个分支，从一个结点X到另一个结点Y所经历的所有分支构成结点X到结点Y的路径，一条路径上的分支数目称为路径长度，从树的根结点到其他各个结点的路径长度之和称为树的路径长度。
叶子结点、分支结点和内部结点：
树中度为0的结点称为叶子结点（或终端结点），度不为0的结点称为分支结点（或非终端结点），除根结点以外的分支结点也称为内部结点。
孩子和双亲：
在树中，一个结点的后继结点称为该结点的孩子，相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩子结点的双亲、其双亲结点的孩子。
兄弟和堂兄弟：
同一双亲的孩子结点之间互称为兄弟，不同双亲但在同一层的结点之间互称为堂兄弟。
祖先和子孙：
从树的根结点到某一个结点X的路径上经历的所有结点（包括根结点但不包括结点X）称为结点X的祖先，以某一结点X为根的子树上的所有非根结点（即除结点X外）称为结点X的子孙。
有序树和无序树：
对于树中的任一结点，如果其各棵子树的相对次序被用来表示数据之间的关系，即交换子树位置会改变树所表示的内容，则称该树为有序树；否则称为无序树。
森林：
m（m≥0）棵互不相交的树的集合就构成了森林。
3.请简述二叉树的五条基本性质。
性质1：
在二叉树的第i层上至多有2i-1个结点（i≥1）。
性质2：
深度为k的二叉树至多有2k-1个结点。
性质3：
在二叉树中，若度为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.请简述二叉树的常用操作及各操作的含义。
创建一棵空二叉树：
创建一棵没有任何结点的二叉树。
在顺序表示中，根据树的深度为结点分配内存；在二叉链表表示中，将指向根结点的指针赋值为NULL。
删除一棵二叉树：
将二叉树各结点所占据的内存释放。
清空二叉树：
将二叉树的所有结点删除，使之成为一棵空二叉树。
以指定元素值创建根结点：
创建根结点，并以指定值作为根结点的元素值。
将一个结点作为指定结点的左孩子插入：
根据指定元素值生成一个新结点，并将其作为指定结点的左孩子。
将一个结点作为指定结点的右孩子插入：
根据指定元素值生成一个新结点，并将其作为指定结点的右孩子。
先序遍历二叉树：
也称为先根遍历，其访问方式递归定义如下：
对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。
中序遍历二叉树：
也称为中根遍历，其访问方式递归定义如下：
对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。
后序遍历二叉树：
也称为后根遍历，其访问方式递归定义如下：
对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。
逐层遍历二叉树：
从第1层开始依次对每层中的结点按照从左至右的顺序进行访问。
获取指定结点的双亲结点：
根据指定结点获取其双亲结点。
在顺序表示中，可以直接根据指定结点的位置计算双亲结点的位置；在二叉链表表示中，则需要从根结点开始遍历二叉树直至找到指定结点的双亲结点。
删除以指定结点为根的子树：
将以指定结点为根结点的子树上的所有结点（包括指定结点）删除。
按关键字查找结点：
按照某种规则（先序、中序、后序或逐层）依次访问二叉树中的
升级会员 