1、数据结构算法与应用习题参考答案doc第1章 概 论1.数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。数据元素：数据的根本单位，在计算机程序中通常作为一个整体考虑。数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和根本运算等概念。2.什么是
2、数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息：数据元素的信息；各数据元素之间的关系。物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。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、转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述。一个有效的算法必须满足的五个重要特性：有穷性：算法必须能在有限的时间内做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。确定性：算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许有二义性。输入：算法有0个或多个输入值，来描述算法开始前运算对象的初始情况，这是算法执行的起点或是依据。0个输入是指算法本身给出了运算对象的初始条件。输出：算法至少有1个或多个输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。可行性：算法中要做的运算都是根
6、本运算，能够被精确地进行。即算法中执行的任何计算都可以被分解为根本的运算步，每个根本的运算步都可以在有限的时间内完成。6.什么是算法分析？算法分析主要考虑哪几方面的内容？算法的研究与实际问题直接相关，用来解一个问题可以有很多不同的算法，他们之间的效果可能会有很大差异。算法设计者最关心的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中选择好的算法。除了要首先考虑算法的正确性外，还要分析和评价算法的性能。分析和评价算法的性能主要要考虑以下两个方面：时间代价：执行算法所消耗的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。空间代价：
7、执行算法所消耗的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。7.分析下面算法的时间复杂度。1答：时间复杂度为n22时间复杂度：n3时间复杂度：4时间复杂度：n25时间复杂度：O(log2n)8.算法设计中的递归、穷举、递推和迭代等算法的根本思想是什么？递推法：是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成假设干步，找出相邻几步的关系，从而到达求解问题的目的。具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i
8、=1出发，由i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。递归法：递归策略是利用函数直接或间接地调用自身来完成某个计算过程。能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。穷举法：穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行 逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。迭代法：数值分析中通过从一个初始估计出发寻找一系列近似解来
9、解决问题一般是解方程或者方程组的过程，为实现这一过程所使用的方法统称为迭代法。9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的根本思想是什么？分治策略的根本思想是把一个规模为n的问题划分为假设干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。贪心策略的根本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过假设干次的贪心选择而得出最优解或较优解的一种解题策略。动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过
10、对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准那么便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规那么进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。回溯策略也叫试探法，它的根本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最正确选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。分支定界策略也经常被称为分支限界策略，它的根本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不
11、可能产生最优解的分支，提高搜索效率。第二章 线性表1具有什么特征的数据结构被称为线性表？线性表是一种最常用、最简单的典型线性数据结构，应用非常广泛。线性表是由nn0个数据元素组成的一个有限序列，线性表中数据元素的个数n称为线性表的长度。当n=0时，称为空表。对于非空线性表，数据元素之间存在一对一的关系，具体特性如下：第一个数据元素没有前驱；最后一个数据元素没有后继外；其他数据元素都是首尾相接、有且只有一个前驱和后继。2如何实现线性表的顺序存储结构？把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特
12、点：线性表中所有元素所占的存储空间是连续的；线性表的逻辑顺序与物理顺序一致；数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的存储地址指第一个字节的地址，即首地址为 LOC(e1)，每一个数据元素占k个字节，那么线性表中第i个元素ei在计算机存储空间中的存储地址为：LOC(ei)=LOC(e1)+(i-1)k3如何实现线性表的4种链式存储结构？数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。每个结点分为两局部：一局部用于存放数据元素的值，称为数据域；另一局部是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。对于线性表，指针域用于
13、指向该结点的前一个或后一个结点即前驱结点或后继结点。通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为链式存储结构。单向链表：在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空用NULL或0表示，表示链表终止，这样的线性链表称为单向链表。下列图是单向链表示意图。线性表的单向链式存储循环链表：将单向链表最后一个结点的指针指向头结点，这样整个链表就构成一个循环，这种链式存储结构称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL，而是指
14、向头结点。只有头结点的循环链表称为空循环链表。下列图是带头结点的非空循环链表和空循环链表示意图。带头结点的循环链表双向链表：双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下列图a所示。双向循环链表：如果将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的next指针与指向第一个结点，就构成了双向循环链表。下列图b和c是双向链表和双向循环表的逻辑结构示意图。图 双向链表结点结构及双向链表4顺序表和线性链表分别有哪些优点和缺点？线性表的顺序存储与链式存储比拟比拟内容顺序存储链式存储结点存储空间少不需要为表示结点的逻辑关系增加开
15、销多需要增加指针域来表示结点之间的逻辑关系空间利用率低采用数组，按表的最大长度静态分配存储空间高根据表的实际长度动态分配存储空间插入、删除操作慢需要大量移动元素快仅更改指针指向，不需要移动元素访问元素快直接访问慢通过指针移动才能访问实现难易程度相对容易基于数组操作，一般高级语言都提供数组类型相对困难基于指针操作5请列举出一些线性表问题的实例。按员工号排序的员工根本情况表；奥运会各项比赛日程；按学号记录的学生的成绩单；等等。6. 对于顺序表和单向链表，如何实现统计重复元素个数的操作？在顺序表中实现统计重复元素个数的操作：在教材的【描述2-1】中，增加一个统计重复元素个数的成员函数： int Co
16、unt(const T&x); /返回x出现的次数在教材的【描述2-2】中，增加查找重复元素个数的成员函数的实现：/实现统计重复元素个数templateint LinearList:Count(const T& x) int count=0; for (int i=0; ilength; i+) if(elementi=x) count+; return count;在顺序表中实现统计重复元素个数的操作：在教材的【描述2-3】中，增加一个统计重复元素个数的成员函数： int Count(const T&x); /返回x出现的次数在教材的【描述2-4】中，增加查找重复元素个数的成员函数的实现：/
17、实现统计重复元素个数templateint LinkList:Count(const T& x) LinkNode * p=head-next; int count=0; while (p!=NULL & ) if (p-data =x) count+; p=p-next; return count;第3章 栈和队列1具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？栈：一种插入和删除都只能在表的同一端进行的线性表。队列：一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。先进后出：元素是以e1，e2，en顺序进入数据结构，以相反的
18、顺序即en，en-1，e1离开数据结构。栈顶：允许进行插入和删除操作的一端。栈底：栈中与栈顶相对的另一端。先进先出：元素是以e1，e2，en顺序进入数据结构，以相同的顺序即e1，e2，en。 离开数据结构。队头：允许删除操作的一端。队尾：允许插入操作的一端。 2简述在顺序栈的栈顶插入一个元素的操作过程。在插入元素之前，首先要判断栈是否为满，如果栈满，返回“沾满无法插入等错误提示信息；否那么让top指针指向当前顺序栈的栈顶向后移动一个元素空间元素大小，将要插入的元素放入top指针指向的内存单元中。3. 一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。可分为三种情况：、当只有一个存储空间时
19、，只有一种出栈序列：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. 简述在链接栈中插入一个元素的操作过程。链接栈的插入操作，先将待进
20、栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。6请列举出一些可以用栈和队列表示的实际问题。所有“后进先出(LIFO，Last In First Out的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。所有“先进先出(FIFO，First In First Out的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等
21、。第4章 数组、字符串与广义表1.具有什么特征的数据结构被称为数组？数组可以看成是形如index，value的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；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.请简述数组和矩阵的关系。矩阵是指纵横排列的二维数
22、据表格。在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。但矩阵的索引通常从1而不是像数组那样从0开始，并且使用Ai，j而不是Ai，j的形式来引用矩阵中的元素。4.矩阵有哪些根本运算？矩阵的操作包括转置、加法、减法和乘法等。5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储技术？稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。采用压缩存储技术主要是为了节省空间。6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+B。/稀疏矩阵的三元组表示#include using namespace std;#define M 50#
23、define N 50#define MaxSize 20typedef int ElemType; typedef struct int r; int c; ElemType d; TupNode;typedef struct int rows; int cols; int nums; TupNode dataMaxSize; TSMatrix;int AMN,BMN;/建立三元组void CreateMat(int AMN,TSMatrix &t,int row,int col) int i,j; t.rows=row;t.cols=col;t.nums=0; for(i=0;iM;i+)
24、 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(TSMatrix &a,TSMatrix &b,TSMatrix &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.d
25、atai.cb.dataj.c) c.datak.r=b.dataj.r; c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; j+;k+; else v=a.datai.d+b.dataj.d; if(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+; else c.datak
26、.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.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 DispMa
27、t(TSMatrix 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.datai.dendlendl; /主函数int main() int row,col,i,j; TSMatrix 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相加后得到的三元组表示为：n; DispMat(c); return 0;7.简述字符串与一维字符型数组的区别与联系。字符串简称串，它是一种以字符为元素的特殊线性表。字符串可以看成是以字
