《数据结构、算法和应用(C++语言描述)》习题参考答案解析doc

第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〔n0个数据元素组成的一个有限序列,线性表中数据元素的个数n称为线性表的长度。当n=0时,称为空表。对于非空线性表,数据元素之间存在一对一的关系,具体特性如下：第一个数据元素没有前驱；最后一个数据元素没有后继外；其他数据元素都是首尾相接、有且只有一个前驱和后继。2．如何实现线性表的顺序存储结构？把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储,采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特点：●线性表中所有元素所占的存储空间是连续的；●线性表的逻辑顺序与物理顺序一致；●数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的存储地址〔指第一个字节的地址,即首地址为LOC<e1>,每一个数据元素占k个字节,则线性表中第i个元素ei在计算机存储空间中的存储地址为：LOC<ei>=LOC<e1>+<i-1>k3．如何实现线性表的4种链式存储结构？数据结构中的每一个数据元素对应于一个存储单元,这种存储单元称为存储结点,简称结点。每个结点分为两部分：一部分用于存放数据元素的值,称为数据域；另一部分是指针,用于指向与该结点在逻辑上相连的其他结点,称为指针域。对于线性表,指针域用于指向该结点的前一个或后一个结点〔即前驱结点或后继结点。通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构,称为链式存储结构。单向链表：在线性链表中,用一个专门的指针指向线性表中第一个结点,每一个结点的指针都指向它的下一个逻辑结点,线性链表的最后一个结点的指针为空〔用NULL或0表示,表示链表终止,这样的线性链表称为单向链表。下图是单向链表示意图。线性表的单向链式存储循环链表：将单向链表最后一个结点的指针指向头结点,这样整个链表就构成一个循环,这种链式存储结构称为单向循环链表,简称循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL,而是指向头结点。只有头结点的循环链表称为空循环链表。下图是带头结点的非空循环链表和空循环链表示意图。带头结点的循环链表双向链表：双向链表的每个结点含有两个指针域,一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下图〔a所示。双向循环链表：如果将双向链表第一个结点的prev指针指向最后一个结点,将最后一个结点的next指针与指向第一个结点,就构成了双向循环链表。下图〔b和〔c是双向链表和双向循环表的逻辑结构示意图。图双向链表结点结构及双向链表4．顺序表和线性链表分别有哪些优点和缺点？线性表的顺序存储与链式存储比较比较内容顺序存储链式存储结点存储空间少〔不需要为表示结点的逻辑多〔需要增加指针域来表示结关系增加开销点之间的逻辑关系空间利用率低〔采用数组,按表的最大长高〔根据表的实际长度动态分度静态分配存储空间配存储空间插入、删除操慢〔需要大量移动元素作快〔仅更改指针指向,不需要移动元素访问元素快〔直接访问慢〔通过指针移动才能访问实现难易程度相对容易〔基于数组操作,一相对困难〔基于指针操作般高级语言都提供数组类型5．请列举出一些线性表问题的实例。按员工号排序的员工基本情况表；奥运会各项比赛日程；按学号记录的学生的成绩单；等等。6.对于顺序表和单向链表,如何实现统计重复元素个数的操作？在顺序表中实现统计重复元素个数的操作：在教材的[描述2-1]中,增加一个统计重复元素个数的成员函数：intCount<constT&x>;//返回x出现的次数在教材的[描述2-2]中,增加查找重复元素个数的成员函数的实现：//实现统计重复元素个数template<classT>intLinearList<T>::Count<constT&x>{intcount=0;for<inti=0;i<length;i++>if<element[i]==x>count++;returncount;}在顺序表中实现统计重复元素个数的操作：在教材的[描述2-3]中,增加一个统计重复元素个数的成员函数：intCount<constT&x>;//返回x出现的次数在教材的[描述2-4]中,增加查找重复元素个数的成员函数的实现：//实现统计重复元素个数template<classT>intLinkList<T>::Count<constT&x>{LinkNode<T>*p=head->next;intcount=0;while<p!=NULL&&>{if<p->data==x>count++;p=p->next;}returncount;}第3章栈和队列1．具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？栈：一种插入和删除都只能在表的同一端进行的线性表。队列：一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。nn-1,……e离开数据结构。先进后出：元素是以e1,e2,……en顺序进入数据结构,以相反的顺序即e,e1栈顶：允许进行插入和删除操作的一端。栈底：栈中与栈顶相对的另一端。先进先出：元素是以e1,e2,……en顺序进入数据结构,以相同的顺序即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、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=11523.请简述数组和矩阵的关系。矩阵是指纵横排列的二维数据表格。在高级语言编程中,通常用二维数组来描述一个矩阵,从而可以对矩阵中的元素进行随机存取。但矩阵的索引通常从1而不是像数组那样从0开始,并且使用A〔i,j而不是A[i,j]的形式来引用矩阵中的元素。4.矩阵有哪些基本运算？矩阵的操作包括转置、加法、减法和乘法等。5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储技术？稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。采用压缩存储技术主要是为了节省空间。6.设A和B是稀疏矩阵,都以三元组作为存储结构,请写出矩阵相加的算法C=A+B。//稀疏矩阵的三元组表示#include<iostream>usingnamespacestd;#defineM50#defineN50#defineMaxSize20typedefintElemType;typedefstruct{intr;intc;ElemTyped;}TupNode;typedefstruct{introws;intcols;intnums;TupNodedata[MaxSize];}TSMatrix;intA[M][N],B[M][N];//建立三元组voidCreateMat<intA[M][N],TSMatrix&t,introw,intcol>{inti,j;t.rows=row;t.cols=col;t.nums=0;for<i=0;i<M;i++>{for<j=0;j<N;j++>{if<A[i][j]!=0>{t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}}//矩阵相加intMatAdd<TSMatrix&a,TSMatrix&b,TSMatrix&c>{inti=0,j=0,k=0;ElemTypev;if<a.rows!=b.rows||a.cols!=b.cols>return0;c.rows=a.rows;c.cols=a.cols;while<i<a.nums&&j<b.nums>{if<a.data[i].r==b.data[j].r>{if<a.data[i].c<b.data[j].c>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}elseif<a.data[i].c>b.data[j].c>{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}else{v=a.data[i].d+b.data[j].d;if<v!=0>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}}elseif<a.data[i].r<b.data[j].r>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}else{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}}if<i==a.nums>while<j<b.nums>{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}if<j==b.nums>while<i<a.nums>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}c.nums=k;return1;}//输出三元组voidDispMat<TSMatrixt>{inti;if<t.nums<=0>{cout<<"此矩阵所有元素都为"<<endl;return;}cout<<t.rows<<'\t'<<t.cols<<'\t'<<t.nums<<endl;cout<<"-----------------"<<endl;for<i=0;i<t.nums;i++>cout<<t.data[i].r<<'\t'<<t.data[i].c<<'\t'<<t.data[i].d<<endl<<endl;}//主函数intmain<>{introw,col,i,j;TSMatrixa,b,c;cout<<"请输入矩阵的行、列数：\n";cin>>row>>col;cout<<"请输入矩阵A的元素：\n";for<i=0;i<row;i++>for<j=0;j<col;j++>cin>>A[i][j];cout<<"请输入矩阵B的元素：\n";for<i=0;i<row;i++>for<j=0;j<col;j++>cin>>B[i][j];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>;}return0;}7.简述字符串与一维字符型数组的区别与联系。字符串简称串,它是一种以字符为元素的特殊线性表。字符串可以看成是以字符为元素的一维数组。具体实现时,在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层开始依次对每层中的结点按照从左至右的顺序进行访问。获取指定结点的双亲结点：根据指定结点获取其双亲结点。在顺序表示中,可以直接根据指定结点的位置计算双亲结点的位置；在二叉链表表示中,则需要从根结点开始遍历二叉树直至找到指定结点的双亲结点。删除以指定结点为根的子树：将以指定结点为根结点的子树上的所有结点〔包括指定结点删除。按关键字查找结点：按照某种规则〔先序、中序、后序或逐层依次访问二叉树中的每一结点,直至找到与关键字匹配的结点。判断二叉树是否为空：判断一棵二叉树是否为空二叉树。修改指定结点的元素值：将指定结点的元素值修改为指定值。计算二叉树的深度：按照某种规则依次访问二叉树中的每一结点,计算各结点所在层的最大值。计算二叉树的叶子结点数：按照某种规则依次访问二叉树中的每一结点,计算度为0的结点数。5.请简述顺序表示的二叉树中各结点的编号规则。顺序表示的二叉树中各结点的编号与相同深度的完全二叉树中对应结点的编号相同。6.请简述二叉链表表示和三叉链表表示的二叉树中结点的结构。在二叉链表表示中,双亲结点有指向其孩子结点的指针,而孩子结点不包含指向其双亲结点的指针；在三叉链表表示中,双亲结点有指向其孩子结点的指针,而孩子结点也包含指向其双亲结点的指针。7.请简述二叉树的四种遍历方式及每一种遍历方式中结点的访问顺序。先序遍历二叉树：也称为先根遍历,其访问方式递归定义如下：对于一棵二叉树,先访问其根结点,再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问,即先访问根结点,再访问根结点的左、右子树。中序遍历二叉树：也称为中根遍历,其访问方式递归定义如下：对于一棵二叉树,先访问根结点左子树,再访问根结点,最后访问右子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。后序遍历二叉树：也称为后根遍历,其访问方式递归定义如下：对于一棵二叉树,先访问根结点的左子树,后访问右子树,最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。逐层遍历二叉树：从第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,请给出该二叉树的先序遍历结果。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.请简述结点的权、结点的带权路径长度、树的带权路径长度等基本术语的含义。结点的权和结点的带权路径长度：在实际应用中,往往给树中的结点赋予一个具有某种意义的实数,该实数就称为是结点的权。结点的带权路径长度是指从树根到该结点的路径长度与结点的权的乘积。树的带权路径长度：是指树中所有叶子结点的带权路径长度之和,记为〔其中,n为叶子结点的数目,Wi为第i个叶子结点的权,Li为根结点到第i个叶子结点的路径长度,可知WiLi为第i个叶子结点的带权路径长度。13.请简述哈夫曼树的构造方法。哈夫曼树的构造方法如下：〔a已知n个权值为Wi〔i=1,2,…,n的结点,将每个结点作为根结点生成n棵只有根结点的二叉树Ti,形成森林F={T1,T2,…,Tn}。〔b从森林F中选出根结点权值最小的两棵二叉树Tp和Tq,并通过添加新的根结点将它们合并为一棵新二叉树,新二叉树中Tp和Tq分别作为根结点的左子树和右子树,且根结点的权值等于Tp和Tq两棵二叉树的根结点权值之和。以合并后生成的新二叉树替代森林F中的原有二叉树Tp和Tq。重复该步骤直至森林F中只存在一棵二叉树。14.请简述哈夫曼码的作用及其编码方法。哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间,其具体方法为：〔a以要编码的字符集C={c1,c2,…,cn}作为叶子结点、字符出现的频度或次数W={w1,w2,…,wn}作为结点的权,构造哈夫曼树。〔b规定哈夫曼树中,从根结点开始,双亲结点到左孩子结点的分支标为0,双亲结点到右孩子结点的分支标为1。从根结点到某一叶子结点经过的分支形成的编码即是该叶子结点所对应字符的哈夫曼码。15.请简述树的四种常用表示方式。双亲表示法：在孩子结点中设置一个指针域记录其双亲结点的存储位置。孩子表示法：在双亲结点中设置指向孩子结点的指针域来表示一棵树。孩子双亲表示法：综合了孩子表示法和双亲表示法的特点,既在孩子结点中设置记录双亲结点位置的指针域,又在双亲结点中设置记录孩子结点位置的指针域。孩子兄弟表示法：又称为二叉链表表示法,与二叉树的二叉链表表示法存储结构完全相同,只是结点中指针域的含义有所不同〔一个指针域指向该结点的第一个孩子结点,另一个指针域指向该结点的下一个兄弟结点。16.请简述森林转换为二叉树的具体步骤。将森林中的每棵树都用二叉链表表示法表示,并将各棵二叉树的根结点看做是兄弟结点,在它们之间加上连线；将结点到第一个孩子结点的连线作为左子树的边,结点到兄弟结点的连线作为右子树的边。17.请简述二叉树转化为树或森林的具体步骤。将一个结点左子树的边作为该结点指向第一个孩子结点的连线,右子树的边作为该结点到兄弟结点的连线；在双亲结点和它的各孩子结点之间加上连线,并删除兄弟结点之间的连线,得到一棵树或一个包含若干棵树的森林。第6章图1.请简述图的结构特性。图G由顶点〔图中通常将结点称为顶点的非空有限集合V和边的集合E组成,记为G=<V,E>。每一个顶点偶对就是图中的一条边,所以,E用于表示V上的连接关系。在一个图中,至少要包含一个顶点,但可以没有任何边。2.请解释有向图、无向图、弧、弧尾、弧头、顶点的度、顶点的入度、顶点的出度、路径、路径长度、回路、简单回路、连通图、单向连通图、强连通图、子图、连通分量、强连通分量、权、带权图、生成树、最小生成树等基本术语的含义。有向图、弧、弧尾和弧头：若E<G>中的顶点偶对是有序的,则这些有序偶对就形成了有向边,此时图G称为有向图。其中,有向边也简称为弧。在有向图G中,对于一条从顶点vi到顶点vj的弧,记为<vi,vj>并有<vi,vj>∈E<G>,称vi为弧尾,vj为弧头。无向图：若E<G>中的顶点偶对是无序的,则这些无序偶对就形成了无向边,此时图G称为无向图。顶点的度、顶点的入度和顶点的出度：在无向图中,与顶点vi相关联的边的数目称为顶点vi的度。在有向图中,以顶点vi为弧头的弧的数目称为顶点vi的入度；以顶点vi为弧尾的弧的数目称为vi的出度；顶点vi的入度和出度之和称为vi的度。路径和路径长度：在图G中,若存在一个顶点序列<〔若G为有向图或,,…,>,使得对于任意0≤j<n-1有〔若G为无向图,则该序列是从顶点到顶点的一条路径。一条路径中边的数目称为路径长度。回路和简单回路：在一条路径中,若组成路径的顶点序列中第一个顶点与最后一个顶点相同,则该路径称为回路〔或环；在一个回路中,若除第一个顶点与最后一个顶点外,其他顶点只出现一次,则该回路称为简单回路〔或简单环。连通图：无向图G中,若任意两个顶点都是连通的,则称G为连通图。单向连通图和强连通图：有向图G中,若任意两个顶点都是单向连通的,则称G是单向连通图；若任意两个顶点都是强连通的,则称G为强连通图。子图：对于图G、G',若满足且,则G'是G的子图。连通分量和强连通分量：一个无向图的极XX通子图称为该无向图的连通分量；一个有向图的极大强连通子图称为该有向图的强连通分量。权和带权图：可以为一个图中的每条边标上一个具有某种意义的实数,该实数就称为是边的权。边上带权的图就称为带权图。生成树和最小生成树：若无向图G的一个子图G'是一棵包含图G所有顶点的树,则G'称为图G的生成树。在所有形式的生成树中,边上的权之和最小的生成树,称为最小生成树。3.请列举可以用图来描述的实际问题。请参考例6-1和例6-2。4.请简述图的基本操作及各操作的含义。创建图：创建不包含任何顶点和边的空图。对图作深度优先遍历：类似于树的先序遍历,即从某一个顶点开始访问,访问后将该顶点去除得到若干子图,对每个子图再依次进行深度优先遍历。对图作广度优先遍历：类似于树的逐层遍历,即先从某一个顶点开始访问,然后访问与该顶点相邻接且未被访问过的顶点集V1<G>,再访问与V1<G>中顶点相邻接且未被访问过的顶点集V2<G>,重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图,还要从某一个未被访问的顶点开始重复上一过程,直至所有顶点访问完毕。获取顶点数目：获取图中所包含的顶点的数目。获取边的数目：获取图中所包含的边的数目。获取与指定顶点相关联的第一条边：对无向图,获取到与指定顶点相关联的第一条边；对有向图,获取到以指定顶点作为弧尾的第一条弧。不同表示方法获取到的结果会有所不同〔邻接矩阵法按顶点编号顺序,邻接压缩表和邻接链表按边的添加顺序。获取与指定边有相同关联顶点的下一条边：对无向图,获取到与指定边<nV1,nV2>有相同关联顶点nV1的下一条边；对有向图,获取到与指定弧<nV1,nV2>有相同弧尾nV1的下一条弧。不同表示方法获取到的结果会有所不同〔邻接矩阵法按顶点编号顺序,邻接压缩表和邻接链表按边的添加顺序。添加一个顶点：向图中添加一个新顶点。添加一条边：对无向图,向图中添加一条新边；对有向图,向图中添加一条新弧。获取一个顶点中存储的数据：根据顶点编号获取该顶点中存储的数据。判断一条边是否存在：对无向图,判断两个顶点nV1和nV2之间是否存在边；对有向图,判断是否存在从顶点nV1到顶点nV2的弧。设置一条边的权：对无向图,设置指定边<nV1,nV2>上的权；对有向图,设置指定弧<nV1,nV2>上的权。获取一条边的权：对无向图,获取指定边<nV1,nV2>上的权；对有向图,获取指定弧<nV1,nV2>上的权。5.请简述图的三种常用表示方法。邻接矩阵法：用矩阵来表示各顶点之间的连接关系。对于有n个顶点的图G=<V,E>,其邻接矩阵A为n*n的方阵,元素A[i][j]〔0≤i,j<n定义为：其中,wij为边<vi,vj>或<vi,vj>上的权。邻接压缩表：邻接矩阵的一种压缩表示形式,使用3个顺序表来表示图中顶点之间的连接关系和权。设图中共有n个顶点{v0,v1,…,vn-1},3个顺序表分别为s、w和h。在s中依次记录与顶点vi〔i=0,1,…,n-1相关联的顶点；在w中依次记录s中存储的各条边的权；在h中依次记录与顶点vi相关联的顶点在s中的起始存储位置。邻接链表：图的一种链式存储结构。每个顶点中设置一个指向链表头的指针,在链表中保存与该顶点相邻接的顶点信息〔包括顶点位置及两个顶点形成的边的权。6.请简述图的两种常用遍历方法及每一种遍历方法中结点的访问顺序。广度优先遍历：类似于树的逐层遍历,即先从某一个顶点开始访问,然后访问与该顶点相邻接且未被访问过的顶点集V1<G>,再访问与V1<G>中顶点相邻接且未被访问过的顶点集V2<G>,重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图,还要从某一个未被访问的顶点开始重复上一过程,直至所有顶点访问完毕。深度优先遍历：类似于树的先序遍历,即从某一个顶点开始访问,访问后将该顶点去除得到若干子图,对每个子图再依次进行深度优先遍历。7.请列举最小生成树和最短路径可以用于解决什么应用问题。请参考例6-1和例6-2。8.请简述Prim算法的作用和具体步骤。Prim算法用于最小生成树问题求解。对于有n个顶点的图G=<V,E>,Prim算法从空树T开始,按照以下规则将n个顶点和n-1条边依次添加到树中,形成最小生成树：〔a从某一顶点v0'开始,将该顶点作为树的根结点加入到T中,使得T中的数据元素集合D={v0'},数据元素关系集合R={}。〔b对于一个顶点在集合D中、另一个顶点在集合V-D中的那些边,找出权最小的一条边,将该边在集合V-D中的顶点vi'〔i=1,2,…,n-1加入到集合D中,并将顶点间关系<vj',vi'>〔j<i加入到关系集合R中。〔c重复上一步骤直至集合D中包括图G中所有n个顶点〔此时关系集合R中包括n-1条边。若在某一步骤中找不到边,则说明图G是一个非连通图或非强连通图,在这种情况下不存在最小生成树。9.请简述Kruskal算法的作用和具体步骤。Kruskal算法用于最小生成树问题求解。对于有n个顶点的图G=<V,E>,Kruskal算法根据图G中所有n个顶点生成一个包括n棵只有根结点的树Ti〔i=0,1,…,n-1的森林F,并按照以下规则森林F中的树合并,形成最小生成树：〔a从边集合E中选取未被访问过且具有最小权的边,置该边状态为已访问。判断该边的两个顶点是否属于不同的树,若属于不同的树则使用该边将两棵树合并为一棵；若属于同一棵树则不做任何处理。〔b重复上一步骤直至森林F中只剩下一棵树,该树即是图G的最小生成树。若最后森林F中剩下不止一棵树,则说明图G是非连通图或非强连通图,在这种情况下不存在最小生成树。10.请简述Dijkstra算法的作用和具体步骤。Dijkstra算法用于计算从某个顶点到其余各顶点的最短路径。对于有n个顶点的图G=<V,E>,若要计算从顶点v0'到其余各顶点vi'〔i=1,2,…,n-1的最短路径,则其计算步骤为：〔a令集合S为已计算出最短路径的顶点集合〔初始时S={v0'},w<vj',vi'>表示从顶点vj'到顶点vi'的边的权〔这里为方便计算,令w<vi',vi'>=0,D<v0',vi'>表示当前计算得到的从顶点v0'到顶点vi'的最短路径长度〔初始D<v0',vi'>=w<v0',vi'>。〔b将顶点加入到集合S中,并将从顶点v0'到顶点vm'的最短路径记录下来。若仍有顶点没有加到集合S中,则对集合V-S中的顶点vi'计算。〔c重复上一步骤直至图中所有顶点都加到集合S中。11.请简述Floyd算法的作用和具体步骤。Floyd算法用于计算每一对顶点之间的最短路径。对于有n个顶点的图G=<V,E>,若要计算任意两个顶点vj'和vk'〔j,k为[0,n-1]区间上的整数且j≠k之间的最短路径,则其计算步骤为：〔a令w<vj',vk'>表示连接顶点vj'和顶点vk'的边的权〔这里为方便计算,令w<vj',vj'>=0,D<vj',vk'>表示当前计算得到的从顶点vj'到顶点vk'的最短路径长度〔初始D<vj',vk'>=w<vj',vk'>。〔b对于图中每一个顶点vi'〔i依次取值为0,1,…,n-1,若D<vj',vk'>>D<vj',vi'>+D<vi',vk'>,则表明路径<vj',…,vi',…,vk'>的长度更短,此时令D<vj',vk'>=D<vj',vi'>+D<vi',vk'>并更新从顶点vj'到顶点vk'的路径。第7章排序算法1.请简述排序的作用。排序的作用是将一个待排序元素集合按关键字递增〔或递减顺序整理为一个有序序列。2.请简述稳定排序和不稳定排序的含义。若采用某种排序算法对任一组元素进行排序,在排序前后,那些具有相同关键字值的元素之间的相对次序都保持不变,则将这种排序算法称为是稳定的,否则称为是不稳定的。3.请简述各种排序算法的适用范围。排序算法的适用范围如下：〔a直接插入排序、简单选择排序和冒泡排序都是简单排序算法,它们的时间复杂度和空间复杂度分别为O<n2>和O<1>。若待排序元素数量n较小,可以选用直接插入排序和冒泡排序。另外,当待排序元素基本有序时,也应选用直接插入排序和冒泡排序,此时时间复杂度都能达到O<n>。若元素本身数据量较大,元素移动操作代价较高,则应选用平均移动元素次数最少的简单选择排序。希尔排序是对直接插入排序算法的改进,大大降低了时间复杂度,但它是一种不稳定的排序算法。〔b堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况,当待排序元素数量n较小时,它们的性能有可能劣于简单排序算法。因此,在实际应用时,快速排序算法和归并排序算法经常与简单排序算法结合使用〔例如,可以先用快速排序算法将集合划分为规模更小的子集合,对于元素数量较小的子集合,则用直接插入排序算法进行排序。在所有平均时间复杂度为O<nlog2n>的算法中,尽管快速排序在最坏情况下时间复杂度较高,但它通常被认为是平均性能最好的一种算法,并且通过优化可以降低最坏情况出现的概率。归并排序是一种稳定的排序算法,其时间性能一般要优于堆排序,但它所需要的辅助空间较多,当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以考虑使用。堆排序所需的辅助空间最少,当可用空间非常有限时可以考虑使用。〔c箱排序和基数排序的时间复杂度最低,但它们的空间复杂度最高。箱排序主要适用于待排序元素长度〔即d值较小的情况,在实际中应用不多；基数排序是箱排序的改进,主要适用于整数或字符串的排序,或者与其他排序算法结合进行实数的排序〔例如,可以先用基数排序算法按整数部分将元素分成若干个子集合,再对每个子集合应用直接插入排序算法进行排序。5.请简述插入排序、选择排序、交换排序、归并排序和分配排序的原理。插入排序：按关键字大小每次将一个待排序的元素插入到已排序的序列中,直至所有元素都插入完毕。选择排序：每次从待排序的元素中选择具有最小〔或最大关键字的元素放到已排序序列的尾部〔或头部,直至所有元素都排序完毕。交换排序：从待排序的元素中选择两个次序相反的元素进行交换,直至任意两个元素的次序都正确。K路归并排序：每次将K〔K≥2个已排序的子序列组合在一起,形成一个有序的序列,重复该过程直至得到一个包含所有待排序元素的有序序列。分配排序：根据元素本身所具有的值将各元素逐一映射到一组有序空间中,最后再依次从有序空间中将各元素取出即形成了排序结果。5.请简述直接插入排序的具体步骤。直接插入排序是一种简单排序算法,其具体步骤为：〔a初始已排序区为空,将第一个待排序的元素插入到已排序区中。〔b将后继每一个待排序的元素依次取出,并按照关键字大小将其插入到已排序区中的适当位置,使该序列仍然有序。〔c重复上一步骤直至将待排序的元素都插入到已排序序列中。6.请简述希尔排序的具体步骤。希尔排序,又称为"缩小增量排序",其具体步骤为：〔a令n为待排序元素数目,设置增量序列{d0,d1,…,dk},其中n>d0>d1>…>dk=1。〔b按增量di〔i依次取值为0,1,…,k将待排序元素分为di组,将所有下标距离为di的倍数的元素放在同一组中,即R[1],R[1+di],R[1+2*di],…在第一组中,R[2],R[2+di],R[2+2*di],……在第二组中,……,依此类推。然后分别在各组内进行直接插入排序。〔c重复上一步骤直至最后以1为增量对所有待排序元素进行直接插入排序。7.请简述简单选择排序的具体步骤。简单选择排序是一种简单排序算法,其具体步骤为：〔a初始已排序区为空,待排序区包含所有待排序元素。〔b从待排序区中选择具有最小关键字的元素,将其与待排序区的第一个元素交换位置,并将该位置加到已排序区中。〔c重复上一步骤直至所有元素都排序完毕。8.请简述堆的定义和堆的构建过程。堆的定义：对于包含n个元素的集合R={R[1],R[2],…,R[n]},若满足：〔1R[i]≤R[2*i]且R[i]≤R[2*i+1]〔即R所表示的完全二叉树中每一棵子树的根结点的值均不大于其孩子结点的值。〔2或R[i]≥R[2*i]且R[i]≥R[2*i+1]〔即R所表示的完全二叉树中每一棵子树的根结点的值均不小于其孩子结点的值。则称集合R为堆。若满足前一个条件则称R为小根堆,满足后一个条件则称R为大根堆。堆的构建过程：堆一般采用自底向上的构建方法,即在将以某一结点为根结点的二叉树构建成堆之前,先将其左子树和右子树构建成堆。以叶子结点为根的子树必然是堆,因此,对于由n个元素构成的完全二叉树,其对应的堆的构建过程从R[⎣n/2⎦]作为根结点的子树开始,依次对R[⎣n/2⎦-1]、R[⎣n/2⎦-2]、…、R[1]作为根结点的树进行堆的构建。在将一棵R[i]作为根结点的子树整理为堆时,只有根结点不满足堆的条件,因此,需将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件,这里以大根堆构建为例介绍其具体过程：〔a若R[i]存在左孩子R[2*i],则令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i],则令j=2*i+1。将R[j]与R[i]比较,若R[i]较小,则将R[i]和R[j]交换,并令i=j。〔b重复上述步骤直至R[i]无孩子结点或R[i]比其孩子结点都大,此时该子树即为堆。9.请简述堆排序的具体步骤。堆排序的具体过程：〔a采用自底向上的方法将包含n个元素的待排序集合R={R[1],R[2],…,R[n]}整理为大根堆,其元素数目i=n,初始时已排序集合R'为空集；〔b将R[1]与R[i]交换,并将i算作已排序集合中的元素位置,更新待排序集合中最后一个元素的位置i=i-1,此时待排序集合R={R[1],R[2],…,R[i]},已排序集合R'={R[i+1],R[i+2],…,R[n]}。显然,待排序集合R={R[1],R[2],…,R[i]}中只有根结点R[1]不满足大根堆的条件,通过下移R[1]重新将R整理为大根堆；〔c重复上一步骤直至待排序集合R={R[1]},此时直接将R[1]作为已排序集合R'中的元素,堆排序过程结束。10.请简述冒泡排序的具体步骤。冒泡排序是一种简单排序算法,其具体步骤为：〔a初始已排序区为空,待排序区包含所有待排序元素。〔b在一轮排序中,对待排序区所有相邻元素从前至后进行两两比较,若相邻两个元素次序相反〔即前一个元素的关键字值大于后一个元素的关键字值,则交换它们的位置。每轮排序后,待排序区中的最大元素会移到待排序区的尾部,将待排序区的最后一个元素放到已排序区的头部。〔c重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元素交换的情况,此时直接将待排序区中的所有元素按原次序放到已排序区的头部,冒泡排序结束。11.请简述快速排序中划分的含义和过程。划分的含义：划分是以指定元素x为基准将一个集合R分为两个子集R1和R2,其中R1中的元素都小于或等于x,R2中的元素都大于或等于x。划分的过程：对于包含<high-low+1>个元素的待排序集合R={R[low],R[low+1],…,R[high]},以R[k]〔low≤k≤high为基准对其进行划分的具体过程为：〔a令i、j分别指向集合R的第一个元素和最后一个元素〔即i=low、j=high,并将R[k]与R[i]交换〔即初始基准元素在i所指向的位置,此时基准元素前面没有任何元素,下面对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素。〔b若j!=i且R[j]≥R[i],则令j=j-1,重复直至R[j]<R[i]或j==i。上述处理后,若j!=i〔即通过R[j]<R[i]这个条件退出循环则将R[j]与R[i]交换、i=i+1,并转到下一步〔该步处理结束后,基准元素在j所指向的位置,此时基准元素后面的元素都大于或等于基准元素,而位置i前面的元素都小于或等于基准元素,下面对基准元素前面、位置在i到j-1之间的元素按照从前至后的顺序逐一检查其是否小于或等于基准元素。〔c若i!=j且R[i]≤R[j],则令i=i+1,重复直至R[i]>R[j]或i==j。上述处理后,若i!=j〔即通过R[i]>R[j]这个条件退出循环则将R[i]与R[j]交换、j=j-1,并回到上一步〔该步处理结束后,基准元素在i所指向的位置,此时基准元素前面的元素都小于或等于基准元素,而位置j后面的元素都大于或等于基准元素,下面继续对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素；否则集合划分操作结束。12.请简述快速排序的具体步骤。快速排序就是对集合不断划分的过程：通过划分可以将一个集合分为两个子集合,若子集合中元素数目大于1则再对子集合分别进行划分,重复该过程直至最终每个子集合中元素数目都小于或等于1时快速排序结束。13.请简述二路归并排序的具体步骤。二路归并排序的具体步骤为：〔a对于包含n个元素的待排序集合,将其分为n个长度为1的子序列。〔b将每两个相邻的子序列进行归并,得到⎣n/2⎦个长度为2的子序列和0或1个长度为1的子序列。〔c在此基础上,再对每两个相邻的子序列进行归并,得到⎣n/4⎦个长度为4的子序列和0或1个长度小于4的子序列。〔d重复该过程直至得到一个长度为n的有序序列为止。14.请简述箱排序的具体步骤。箱排序的具体步骤为：〔1假设待排序元素的取值范围为m~m+n-1,则箱子数量为n,设置包含n个元素的队列集合B={B[0],B[1],…,B[n-1]}代表n个箱子。〔2依次取出每一个待排序元素,若其值为m+i〔i=0,1,…,n-1,则通过入队操作将其放在箱子B[i]中。〔3从B[0]开始,依次检查集合B中每一个队列所代表的箱子,若箱子不为空,则通过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。15.请简述基数排序的具体步骤。基数排序是对箱排序的改进和推广,它先将待排序元素按规则分解得到多个分量、再根据每一个分量对元素进行多次箱排序。〔a对于数字排序问题,基数排序方法先将每一个数字写成以r为基数的按权展开式形式：N=an-1*rn-1+a0*r0+a-1*r-1+…+a-m*r-m；再按照从低位到高位〔即从r-m开始到rn-1的顺序进行n+m次箱排序。+…〔b对于字符串排序问题,基数排序方法按照从后至前的顺序对字符串中的每个字符分别进行箱排序。若待排序字符串中最长的字符串长度为n,则需进行n次箱排序；若某一字符串长度为m〔0≤m≤n,则该字符串在前<n-m>次箱排序中对应的字符值为'\0'。第8章查找算法1.请简述查找的作用。查找的作用是根据给定值从一个数据集合中搜索某个元素。若某个元素的关键字值与给定值相等,则查找成功；否则查找失败。2.请简述静态查找和动态查找的含义。静态查找只根据给定值在数据集合中按关键字查找匹配元素、访问匹配元素的属性,而不对数据集合进行插入元素、删除元素等操作；而动态查找可能会在查找过程中向数据集合中插入一个新元素或从数据集合中删除一个已有元素。3.请简述各种查找算法的适用范围。各种查找算法的适用范围：〔a顺序查找虽然查找效率最低,但其对待查找数据集合的存储结构无特别要求,在对数据集合进行增、删、改等操作时效率较高,因此,根据那些不需要经常作查找操作的关键字进行查找时,一般采用顺序查找算法。若经常作查找操作,则应使用效率较高的其他查找算法。〔b折半查找和分块查找主要适用于数据集合增、删、改等操作较少的情况；二叉排序树查找则适用于数据集合变化较频繁的情况。〔c哈希查找虽然在理论上具有最短的平均查找长度,但它占用的存储空间较多,且在实际中只有哈希函数构造得好才能达到常量级的平均查找长度。而要想构造出好的哈希函数,必须以大量数据为基础,因此,哈希查找主要适用于数据分布已知的情况。4.请简述顺序查找对待查找数据集合的要求及顺序查找的具体步骤。顺序查找是一种最简单、直观的查找算法,适用于采用任何存储结构的数据集合,其具体步骤为：〔a按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比较,若某个元素的关键字与给定值相同,则查找成功；〔b若遍历所有元素后,仍没有找到关键字与给定值相同的元素,则查找失败。5.请简述折半查找对待查找数据集合的要求及折半查找的具体步骤。折半查找,又称二分查找,它要求数据集合采用顺序表存储结构,且数据集合中的元素是按关键字大小有序排列的。假设数据集合的元素按关键字递增排列,折半查找算法的具体步骤为：〔a对于包含n个元素的递增数据集合R={R[1],R[2],…,R[n]}〔R[i]≤R[i+1],根据给定元素K进行折半查找,初始化待查找数据集合的下标起始位置low=1和结束位置high=n。〔b计算中间元素下标mid=⎣<low+high>/2⎦,若R[mid]==K,则查找成功,折半查找算法结束；若R[mid]<K,则令low=mid+1；否则,若R[mid]>K,则令high=mid-1。〔c若新的待查找数据集合不为空,即low≤high,则返回到上一步在新的数据集合〔R[low],R[low+1],…,R[high]上继续进行折半查找；否则查找失败。6.请简述分块查找对待查找数据集合的要求及分块查找的具体步骤。在分块查找算法中,除了待查找的数据集合外,还需建立一个索引表。待查数据集合与索引表的关系描述如下：〔a将包含n个元素的待查找数据集合均匀分为b块〔即b个子集合,前b-1块中元素数目s=⎣n/b⎦,最后一块中元素数目小于等于s。〔b分块后块内元素可以无序,但块间必须有序,这里假设块间为递增排列,即第i+1块中的任一元素大于第i块中的任一元素〔i<b。〔c构造一个包含b个元素的索引表,用于记录每块的起始位置和最大元素值。分块查找算法的具体步骤为：〔a在索引表中查找,确定待查找元素在哪一块,由于索引表有序,因此可以使用二分查找算法。〔b在已确定的块中,进行顺序查找。7.请简述二叉排序树的定义。二叉排序树,又称二叉查找树,它或者是一棵空树,或者是具有如下性质的二叉树：〔a若它的左子树非空,则左子树上所有结点的值均小于根结点的值。〔b若它的右子树非空,则右子树上所有结点的值均大于根结点的值。〔c左、右子树也分别是二叉排序树。8.请简述二叉排序树的插入和创建过程。二叉排序树的插入过程：在二叉排序树中插入一个新结点,应保证插入新结点后的二叉树仍然是一棵二叉排序树。对于一个给定元素K,将其插入到二叉排序树中的具体步骤如下：〔a若二叉排序树为一棵空树,则将元素K作为二叉排序树的根结点。〔b若K等于根结点的值,则该元素已经是二叉排序树中的结点,不需重复插入,直接返回；若K小于根结点的值,则将K插入到左子树中；若K大于根结点的值,则将K插入到右子树中。重复该步骤,直至要插入的子树为空,此时将K作为该子树的根结点。二叉排序树的创建过程就是不断插入新结点的过程。9.请简述二叉排序树的查找过程。对于给定值K,先将K与根结点的值比较,若相等则查找成功；若K小于根结点的值,则在左子树中继续进行二叉排序树的查找；否则,若K大于根结点的值,则在右子树中继续进行二叉排序树的查找。重复该过程,直至找到匹配的结点,查找成功；或者子树为空,查找失败。10.请简述哈希表的元素存储原理。确定一函数h,对于关键字值是k的元素,以k为自变量计算函数值h<k>,这个函数值被解释为一片连续存储空间中的一个地址〔即数组中的一个下标值,元素即被存入到这个地址中。11.请简述常用的四种哈希函数及其计算规则。除余法：选取一个适当的正整数p〔通常p为不大于哈希表存储空间尺寸的最大素数,以元素的关键字值k除以p,得到的余数作为元素的存储地址,即h<k>=k%p。数字分析法：若元素的关键字由多位组成,且关键字的位数比存储空间地址码位数多、每一位的取值范围及关键字的取值分布情况预先知道,则可以对元素关键字的各位进行分析,去掉分布较集中的位、保留分布较均匀的位。折叠法：若元素的关键字由多位组成,且关键字的位数比存储空间地址码位数多,但关键字的取值分布情况未知,则可以用折叠法将关键字分为几段〔除了最后一段位数可以少一些,其他各段的位数均等于存储空间地址码位数,并将所有段的值做叠加求和运算,将叠加和的最高位进位舍去后取剩余部分作为元素的存储地址。平方取中法：对元素的关键字值求平方,并取中间几位作为元素的存储地址。12.请简述常用的两种哈希表冲突处理方法。开放定址法：按照某个探查序列在哈希表中进行搜索,直至找到一个空闲的地址,将发生冲突的新元素存储在该地址中。拉链法：将所有同义词存储在一个线性链表中,从而避免开放定址法中的"二次聚集"现象。用拉链法构造的哈希表,若其有m个存储地址〔下标为0,1,…,m-1,则每个地址存储一个线性链表的头指针,映射到地址i的元素以结点的方式插入到地址i所对应的链表中。第9章文件1.请简述文件的定义。文件,是由大量具有相同性质的记录组成的集合。2.请简述文件的组成。文件是大量性质相同的数据记录的集合,即一个文件包含一条或多条记录。记录是一个实体的所有数据项的集合,即一条记录包含一个或多个数据项。数据项〔也称为字段或属性是反映实体某一方面属性的数据表示,是文件存取最基本的操作对象。3.请简述文件的分类。按文件中记录的信息长度,可以将文件分为定长记录文件和不定长记录文件。若每个记录含有相同长度的信息,则称这类记录为定长记录；否则,若每个记录含有不同长度的信息,则称这类记录为不定长记录。由定长记录组成的文件称为定长文件；由不定长记录组成的文件则称为不定长文件。按记录中关键字的数目,可以将文件分为单关键字文件和多关键字文件。若文件中的记录只有一个用于唯一标识记录的主关键字,则这类文件称为单关键字文件；若文件中的记录除了含有一个主关键字之外,还包含若干次关键字,则这类文件称为多关键字文件。4.请简述文件检索操作中的四种查询方式。根据检索条件的不同可以分为以下4种查询方式：〔a简单查询：根据给定值x按单个关键字查询关键字值k等于x的记录。〔b区域查询：根据给定取值范围按单个关键字查询满足条件的记录。〔c函数查询：根据统计函数计算的值查询记录。〔d布尔查询：将以上3种查询用逻辑运算符<包括逻辑与、逻辑或、逻辑非>连接起来所形成的查询。5.请简述文件各维护操作的含义和过程。文件维护是指对文件中记录所进行的插入、删除、修改等操作。这些操作的具体含义和操作过程描述如下：〔a插入：向文件中添加一条新的记录。若文件按某个关键字顺序排列,则插入记录前一般要先通过检索确定插入点的位置。〔b删除：从文件中删除一条记录。删除记录前一般要先通过检索确定所要删除记录的位置。〔c修改：对记录中的一个或多个数据项进行修改。若文件按某个关键字顺序排列,且对关键字值进行了修改操作,则修改后还需将记录移动到正确的位置〔一般采用先删除再插入的方式实现。6.请简述文件的四种基本组织方式。顺序结构、索引结构、散列结构和链式结构。7.请简述磁盘的逻辑结构。磁盘的结构如下：〔a一个磁盘包含若干个盘片,所有盘片组成了盘片组；每个盘片有上下两面,称为盘面；每个盘面上有很多同心圆形式的磁道,数据就存放在这些磁道上；每个磁道又可以划分为若干段,称为扇区,一个扇区就是一次读写的最小数据量。〔b每个盘面都配有一个读写磁头,通过读写磁头可以对磁道上的数据进行读写操作；所有读写磁头都安装在动臂上,通过动臂可以将读写磁头移动到任一磁道上；所有盘面上具有相同半径的磁道就构成了圆柱面,一个磁盘上圆柱面的个数就是一个盘面上的磁道数,同一时刻所有读写磁头都位于一个圆柱面上。〔c主轴带动所有盘面高速旋转,使得读写磁头可以访问到一个磁道上的所有扇区。8.请简述对磁盘存储器进行一次读写操作的具体过程。对磁盘存储器进行一次读写操作的具体步骤为：〔a根据待读写数据所处的柱面,用动臂将读写磁头移动到此柱面上。〔b根据待读写数据所处的扇区,用主轴带动盘面将该扇区转到读写磁头下面。〔c用指定盘面上的读写磁头读写所需数据。9.请简述在磁盘上存储信息的原则。盘面的转速很快,磁盘读写数据的时间大部分花在柱面定位上。寻查时间的长短取决于读写磁头移过的柱面数,所以在磁盘上存储信息时应尽量将相关的信息放在同一柱面或者邻近柱面上,以减少寻查时间。10.请简述顺序文件的定义和分类。顺序文件的定义：顺序文件是结构最简单的文件,文件中记录的物理顺序与逻辑顺序一致,即记录按其逻辑顺序依次存放在文件中。顺序文件的分类：按照存储方式的不同,顺序文件可以分为连续顺序文件和串联顺序文件。在连续顺序文件中,全部记录顺序地存放在外存的一片连续存储空间中。连续顺序文件的优点是存取速度快,缺点是存储空间尺寸需预先确定。在串联顺序文件中,以块为单位将记录存储在外存上,块中的各记录顺序存放在一片连续存储空间中,但块与块之间可以不连续,通过链指针将各块按一定顺序连接起来。串联顺序文件的优点是文件便于扩充,缺点是存取速度慢。按照记录是否有序,顺序文件可以分为有序顺序文件和无序顺序文件。在有序顺序文件中,全部记录按主关键字有序排列；在无序顺序文件中,记录按实际插入顺序排列。有序顺序文件的优点是若记录定长则按主关键字检索时速度较快,无序顺序文件的优点是插入记录时效率较高。