数据结构习题参考答案

第1章概论1.数据、数据元素、数据构造、数据类型的含义分别是什么？数据：对客观事物的符号表达，在计算机科学中是指全部能输入到计算机中并由计算机程序解决的符号的总称。数据元素：数据的基本单位，在计算机程序中普通作为一种整体考虑。数据构造：数据元素之间的关系+运算，是以数据为组员的构造，是带构造的数据元素的集合，数据元素之间存在着一种或多个特定的关系。数据类型：数据类型是用来辨别不同的数据；由于数据在存储时所需要的容量各不相似，不同的数据就必须要分派不同大小的内存空间来存储，全部就要将数据划分成不同的数据类型。数据类型包含取值范畴和基本运算等概念。2.什么是数据的逻辑构造？什么是数据的物理构造？数据的逻辑构造与物理构造的区别和联系是什么？逻辑构造：数据的逻辑构造定义了数据构造中数据元素之间的互相逻辑关系。数据的逻辑构造包含下面两个方面的信息：=1\*GB3①数据元素的信息；=2\*GB3②各数据元素之间的关系。物理构造：也叫储存构造，是指逻辑构造的存储表达，即数据的逻辑构造在计算机存储空间中的寄存形式，涉及结点的数据和结点间关系的存储表达。数据的逻辑构造和存储构造是密不可分的，一种操作算法的设计取决于所选定的逻辑构造，而算法的实现依赖于所采与的存储构造。采用不同的存储构造，其数据解决的效率是不同的。因此，在进行数据解决时，针对不同问题，选择合理的逻辑构造和存储构造非常重要。3.数据构造的重要操作涉及哪些？对于多个数据构造而言，他们在基本操作上是相似的，最惯用的操作有：创立：建立一种数据构造；去除：去除一种数据构造；插入：在数据构造中增加新的结点；删除：把指定的结点从数据构造中删除；访问：对数据构造中的结点进行访问；更新：变化指定结点的值或变化指定的某些结点之间的关系；查找：在数据构造中查找满足一定条件的结点；排序：对数据构造中各个结点按指定数据项的值，以升序或降序重新排列。4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型（AbstractDataType简称ADT）是指一种数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不管ADT的内部构造如何变化，只要其数据构造的特性不变，都不影响其外部使用。对抽象数据类型的描述普通用（D,R,P)三元组表达，抽象数据类型的定义格式为：ADT<抽象数据类型名>{数据对象D：<数据对象的定义>数据关系R：<数据关系的定义>基本操作P：<基本操作的定义>｝ADT<抽象数据类型名>其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。数据对象和数据关系的定义用伪代码来描述。基本操作的定义格式为：基本操作名（参数表）初始条件：<初始条件描述>操作成果：<操作成果描述>初始条件阐明操作执行之前数据构造和参数应满足的条件；操作成果阐明操作完毕后，数据构造的变化状况和应返回的成果。5.什么是算法？算法的基本特性是什么？算法：是在有限的环节内解决数学问题的过程，是以一步接一步的方式来具体描述计算机如何将输入转化为所规定的输出的过程，即算法是对计算机上执行的计算过程的具体描述。一种有效的算法必须满足的五个重要特性：=1\*GB3①有穷性：算法必须能在有限的时间内做完，即在任何状况下，算法必须能在执行有限个环节之后终止，都不能陷入无穷循环中。=2\*GB3②拟定性：算法中的每一种环节，必须通过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和含糊的概念，更不允许有二义性。=3\*GB3③输入：算法有0个或多个输入值，来描述算法开始前运算对象的初始状况，这是算法执行的起点或是根据。0个输入是指算法本身给出了运算对象的初始条件。=4\*GB3④输出：算法最少有1个或多个输出值，反映对运算对象的解决成果，没有输出的算法没有任何意义。=5\*GB3⑤可行性：算法中要做的运算都是基本运算，能够被精确地进行。即算法中执行的任何计算都能够被分解为基本的运算步，每个基本的运算步都能够在有限的时间内完毕。6.什么是算法分析？算法分析重要考虑哪几方面的内容？算法的研究与实际问题直接有关，用来解一种问题能够有诸多不同的算法，他们之间的效果可能会有很大差别。算法设计者最关心的就是什么是有效的算法，如何评价一种算法的优劣，如何从多个算法中选择好的算法。除了要首先考虑算法的对的性外，还要分析和评价算法的性能。分析和评价算法的性能重要要考虑下列两个方面：=1\*GB3①时间代价：执行算法所耗费的时间。一种好的算法首先应当比其它算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。=2\*GB3②空间代价：执行算法所耗费的存储空间，重要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一种重要因素。算法的空间代价的大小用算法的空间复杂度来度量。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表达），表达链表终止，这样的线性链表称为单向链表。下图是单向链表达意图。firstefirste1e2eienNULLNULLNULL…………循环链表：将单向链表最后一种结点的指针指向头结点，这样整个链表就构成一种循环，这种链式存储构造称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一种元素的结点；循环链表中最后一种结点的指针域不再是NULL，而是指向头结点。只有头结点的循环链表称为空循环链表。下图是带头结点的非空循环链表和空循环链表达意图。e1e1……headen头结点head头结点（a）带头结点的非空循环链表（b）带头结点的空循环链表双向链表：双向链表的每个结点含有两个指针域，一种指针指向其前驱结点；另一种指针指向其后继结点。双向链表结点的构造下图（a）所示。e2…en（b）双向链表e1ee2…en（b）双向链表e1e2…en（c）双向循环链表prevdatanext（a）双向链表结点构造firstfirste1end图双向链表结点构造及双向链表4．次序表和线性链表分别有哪些优点和缺点？线性表的次序存储与链式存储比较比较内容次序存储链式存储结点存储空间少（不需要为表达结点的逻辑关系增加开销）多（需要增加指针域来表达结点之间的逻辑关系）空间运用率低（采用数组，按表的最大长度静态分派存储空间）高（根据表的实际长度动态分派存储空间）插入、删除操作慢（需要大量移动元素）快（仅更改指针指向，不需要移动元素）访问元素快（直接访问）慢（通过指针移动才干访问）实现难易程度相对容易（基于数组操作，普通高级语言都提供数组类型）相对困难（基于指针操作）5．请列举出某些线性表问题的实例。=1\*GB3①按员工号排序的员工基本状况表；=2\*GB3②奥运会各项比赛日程；=3\*GB3③按学号统计的学生的成绩单；等等。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．含有什么特性的数据构造被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？栈：一种插入和删除都只能在表的同一端进行的线性表。队列：一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。先进后出：元素是以e1，e2，……en次序进入数据构造，以相反的次序即en，en-1，……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中，若存在一种顶点序列(,,…,)，使得对于任意0≤j<n-1有（若G为有向图）或（若G为无向图），则该序列是从顶点到顶点的一条途径。一条途径中边的数目称为途径长度。回路和简朴回路：在一条途径中，若构成途径的顶点序列中第一种顶点与最后一种顶点相似，则该途径称为回路（或环）；在一种回路中，若除第一种顶点与最后一种顶点外，其它顶点只出现一次，则该回路称为简朴回路（或简朴环）。连通图：无向图G中，若任意两个顶点都是连通的，则称G为连通图。单向连通图和强连通图：有向图G中，若任意两个顶点都是单向连通的，则称G是单向连通图；若任意两个顶点都是强连通的，则称G为强连通图。子图：对于图G、G'，若满足且，则G'是G的子图。连通分量和强连通分量：一种无向图的极大连通子图称为该无向图的连通分量；一种有向图的极大强连通子图称为该有向图的强连通分量。权和带权图：可觉得一种图中的每条边标上一种含有某种意义的实数，该实数就称为是边的权。边上带权的图就称为带权图。生成树和最小生成树：若无向图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]}，若满足：（1）R[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）每个盘面都配有一种读写磁头，通过读写磁头能够对磁道上的数据进行读写操作；全部读写磁头都安装在动臂上，通过动臂能够将读写磁头移动到任一磁道上；全部盘面上含有相似半