数据结构(C++版)课后习题答案.pdf 77页

'第1章绪论课后习题讲解1.填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线性表D集合 【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。⑶算法指的是（）。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理【解答】A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。⑷下面（）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性【解答】C【分析】高效性是好算法应具备的特性。⑸算法分析的目的是（），算法分析的两个主要方面是（）。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性【解答】C，E3.判断题⑴算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。⑵每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。⑶所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。⑷逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。⑸基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.分析以下各程序段，并用大O记号表示其执行时间。 【解答】⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。⑶分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n)。⑷设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：(T(n)+1)2≤n，所以T(n)=O(n1/2)。⑸x++是基本语句，所以5．设有数据结构（D，R），其中D={1,2,3,4,5,6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。6.为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下：ADTintegerData整数a：可以是正整数(1,2,3,…)、负整数(-1,-2,-3,…)和零OperationConstructor前置条件：整数a不存在输入：一个整数b功能：构造一个与输入值相同的整数 输出：无后置条件：整数a具有输入的值Set前置条件：存在一个整数a输入：一个整数b功能：修改整数a的值，使之与输入的整数值相同输出：无后置条件：整数a的值发生改变Add前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相加输出：相加后的结果后置条件：整数a的值发生改变Sub前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相减输出：相减的结果后置条件：整数a的值发生改变Multi前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相乘输出：相乘的结果后置条件：整数a的值发生改变Div前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相除输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变Mod前置条件：存在一个整数a输入：一个整数b功能：求当前整数与输入整数的模，即正的余数输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变Equal前置条件：存在一个整数a输入：一个整数b功能：判断整数a与输入的整数b是否相等输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变endADT7.求多项式A(x)的算法可根据下列两个公式之一来设计：⑴A(x)=anxn+an-1xn-1+…+a1x+a0⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0根据算法的时间复杂度分析比较这两种算法的优劣。【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。8.算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度）⑴对一个整型数组A[n]设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的C++描述。分析算法，有两层嵌套的for循环，所以，。⑵找出整型数组A[n]中元素的最大值和次最大值。【解答】算法的伪代码描述如下： 算法的C++描述如下：分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。学习自测及答案1．顺序存储结构的特点是（），链接存储结构的特点是（）。【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。2.算法在发生非法操作时可以作出处理的特性称为（）。【解答】健壮性3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．将下列函数按它们在n时的无穷大阶数，从小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n【解答】log2n,n1/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。6.对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。⑴A=(D，R)，其中D={a1,a2,a3,a4}，R={}⑵B=(D，R)，其中D={a,b,c,d,e,f}，R={,,,,}⑶C=(D，R)，其中D={a，b，c，d，e，f}，R={,,,,,}⑷D=(D，R)，其中D={1,2,3,4,5,6}，R={(1,2)，(1,4)，(2,3)，(2,4)，(3,4)，(3,5)，(3,6)，(4,6)} 【解答】⑴属于集合，其逻辑结构图如图1-4(a)所示；⑵属于线性结构，其逻辑结构图如图1-4(b)所示；⑶属于树结构，其逻辑结构图如图1-4(c)所示；⑷属于图结构，其逻辑结构图如图1-4(d)所示。7.求下列算法的时间复杂度。count=0;x=1;while(x{x*=2;count++;}returncount;【解答】Ｏ(log2n) 第2章线性表课后习题讲解1.填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。【解答】p->next=head【分析】如图2-8所示。⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。【解答】s->next=rear->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;deleteq;【分析】操作示意图如图2-9所示： ⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻可由一个尾指针唯一确定的链表有（）、（）、（）。【解答】循环链表，循环双链表，双链表2.选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A随机存取B顺序存取C索引存取D散列存取【解答】A，B【分析】参见2.2.1。⑵线性表采用链接存储时，其地址（）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。⑶单循环链表的主要优点是（）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，能更好地保证链表不断开。【解答】B⑷链表不具有的特点是（）。A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比【解答】A⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A顺序表B单链表C双链表D单循环链表【解答】A【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表 【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。A单链表B循环双链表C单循环链表D带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。⑻在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)【解答】B【分析】首先应顺序查找新结点在单链表中的位置。⑼对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。⑽使用双链表存储线性表，其优点是可以（）。A提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。⑾在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。As->next=p->next;p->next=s;Bq->next=s;s->next=p;Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;【解答】B【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。⑿在循环双链表的p所指结点后插入s所指结点的操作是（）。Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s【解答】D 【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。3.判断题⑴线性表的逻辑顺序和存储顺序总是一致的。【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。⑵线性表的顺序存储结构优于链接存储结构。【解答】错。两种存储结构各有优缺点。⑶设p，q是指针，若p=q，则*p=*q。【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。⑷线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。⑸在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。⑵如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。⑶描述一个城市的设计和规划。【解答】顺序表的优点：①无需为表示表中元素之间的逻辑关系而增加额外的存储空间；②可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：①插入和删除操作需移动大量元素；②表的容量难以确定；③造成存储空间的“碎片”。单链表的优点：①不必事先知道线性表的长度；②插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：①指针的结构性开销；②存取表中任意元素不方便，只能进行顺序存取。⑴应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。⑵应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 ⑶应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计⑴设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。⑵已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。⑶试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。【解答】参见2.2.3。 ⑷试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：单链表的逆置请参见2.2.4算法2-4和算法2-6。⑸假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：⑹已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下： ⑺设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：⑻判断带头结点的双循环链表是否对称。【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。 学习自测及答案1.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。A108B180C176D112【解答】D2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。AO(0)BO(1)CO(n)DO(n2)【解答】C3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i4．在单链表中，除了头结点以外，任一结点的存储位置由（）指示。【解答】其前趋结点的指针域5．当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻 6．在双链表中，每个结点设置了两个指针域，其中一个指向（）结点，另一个指向（）结点。【解答】前驱，后继7．设A是一个线性表（a1,a2,…,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为，则平均每插入一个元素所要移动的元素个数又是多少？【解答】，。8．线性表存放在整型数组A[arrsize]的前elenum个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下： 9.已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。10．设单循环链表L1，对其遍历的结果是：x1,x2,x3,…,xn-1,xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1,x3,…；L2中含有原L1表中序号为偶数的结点且遍历结果为：…,x4,x2。【解答】算法如下： 第3章特殊线性表——栈、队列和串课后习题讲解1.填空⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。【解答】23，1003H⑵栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶（）可作为实现递归函数调用的一种数据结构。【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。⑷表达式a*(b+c)-d的后缀表达式是（）。【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同⑹循环队列的引入是为了克服（）。【解答】假溢出⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。【解答】（rear-front+n）%n【分析】也可以是（rear-front）%n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。⑼串是一种特殊的线性表，其特殊性体现在（）。【解答】数据元素的类型是一个字符 ⑽两个串相等的充分必要条件是（）。【解答】长度相同且对应位置的字符相等【分析】例如"abc"≠"abc"，"abc"≠"bca"。2.选择题⑴若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。A不确定Bn-iCn-i-1Dn-i+1【解答】D【分析】此时，输出序列一定是输入序列的逆序。⑵设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A6B4C3D2【解答】C【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。⑶一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。A54321B45321C43512D12345【解答】C【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。⑷设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳A顺序表B栈C队列D链表【解答】B【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。⑸在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。A栈B队列C数组D线性表【解答】B【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。⑹一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。A4321B1234C1432D3241【解答】B【分析】队列的入队顺序和出队顺序总是一致的。⑺栈和队列的主要区别在于（）。A它们的逻辑结构不一样B它们的存储结构不一样C所包含的运算不一样D插入、删除运算的限定不一样【解答】D 【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。⑻设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。AS1的栈底位置为0，S2的栈底位置为n-1BS1的栈底位置为0，S2的栈底位置为n/2CS1的栈底位置为0，S2的栈底位置为nDS1的栈底位置为0，S2的栈底位置为1【解答】A【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。⑼设有两个串p和q，求q在p中首次出现的位置的运算称作（）。A连接B模式匹配C求子串D求串长【解答】B3.判断题⑴有n个元素依次进栈，则出栈序列有(n-1)/2种。【解答】错。应该有种。⑵栈可以作为实现过程调用的一种数据结构。【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。⑶在栈满的情况下不能做进栈操作，否则将产生“上溢”。【解答】对。⑷在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。⑸空串与空格串是相同的。【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。4.设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。⑴C，E，A，B，D⑵C，B，A，D，E【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。 5.举例说明顺序队列的“假溢出”现象。【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。6.在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。【解答】队头元素为5，队尾元素为9。其执行过程如图3-8所示。8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。 9.算法设计⑴假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。【解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。入队算法如下：出队算法如下：⑵设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为：①将所有元素出栈并入队；②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；③将奇数结点出栈并入队； ④将偶数结点出队并入栈；⑤将所有元素出栈并入队；⑥将所有元素出队并入栈即为所求。⑶用顺序存储结构存储串S，编写算法删除S中第i个字符开始的连续j个字符。【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：⑷对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：⑸对串的模式匹配KMP算法设计求模式滑动位置的next函数。【解答】参见3.2.5学习自测及答案1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。A不变Btop=0;Ctop=top-1;Dtop=top+1;【解答】C 2．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的出栈序列是（）。AedcbaBcdebaCdebcaDabcde【解答】C3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。Ax=top;top=top->next;Bx=top->data;Ctop=top->next;x=top->data;Dx=top->data;top=top->next;【解答】D4．设元素1,2,3,P,A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。【解答】PA321,P3A21,P32A1,P321A,AP3215.设S="I_am_a_teacther"，其长度为（）。【解答】156．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（）。【解答】Ｏ(1)7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA8．简述队列和栈这两种数据结构的相同点和不同点。【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。9.利用两个栈S1和S2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。【解答】利用两个栈S1和S2模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已输入的元素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S1中元素全部送入到S2中，再从S2中删除栈顶元素，最后再将S2中元素全部送入到S1中；判断队空的条件是：栈S1和S2同时为空。10.设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。【解答】算法基于原理：N=(Ndivd)×d+Nmodd（div为整除运算，mod为求余运算）。 11．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。【解答】假设表达式已存入字符数组A[n]中，具体算法如下： 第4章广义线性表——多维数组和广义表课后习题讲解1.填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。【解答】三元组顺序表，十字链表⑸广义表((a),(((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。【解答】Head(Head(Tail(LS)))2.选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。A90B180C240D540E108F114G54HA[8][5]IA[3][10]JA[5][8]KA[4][9]【解答】D，E，K【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。 ⑵将数组称为随机存取结构是因为（）A数组元素是随机的B对数组任一元素的存取时间是相等的C随时可以对数组进行访问D数组的存储结构是不定【解答】B⑶下面的说法中，不正确的是（）A数组是一种线性结构B数组是一种定长的线性结构C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。⑷对特殊矩阵采用压缩存储的目的主要是为了（）A表达变得简单B对矩阵元素的存取变得简单C去掉矩阵中的多余元素D减少不必要的存储空间【解答】D【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。⑸下面（）不属于特殊矩阵。A对角矩阵B三角矩阵C稀疏矩阵D对称矩阵【解答】C⑹若广义表A满足Head(A)=Tail(A)，则A为（）A()B(())C((),())D((),(),())【解答】B⑺下面的说法中，不正确的是（）A广义表是一种多层次的结构B广义表是一种非线性结构C广义表是一种共享结构D广义表是一种递归【解答】B【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。⑻下面的说法中，不正确的是（）A对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B对角矩阵只须存放非零元素即可。C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储【解答】D【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3.判断题 ⑴数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。⑵使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。⑶稀疏矩阵压缩存储后，必会失去随机存取功能。【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。⑷线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。⑸若一个广义表的表头为空表，则此广义表亦为空表。【解答】错。如广义表L=(()，(a，b))的表头为空表，但L不是空表。4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。5．已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩 阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t<0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。【解答】2h-1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。⑸深度为k的二叉树中，所含叶子的个数最多为（）。【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。⑹具有100个结点的完全二叉树的叶子结点数为（）。【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。 ⑼在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n，n-1，n+1（10）在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n，n-1【分析】n-1个分支结点是经过n-1次合并后得到的。2.选择题⑴如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A1B2C3D4【解答】D⑵设二叉树有n个结点，则其深度为（）。An-1BnC+1D不能确定【解答】D【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是+1。⑶二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子【解答】B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。⑷线索二叉树中某结点R没有左孩子的充要条件是（）。AR.lchild=NULLBR.ltag=0CR.ltag=1DR.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。⑸深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。A2k-2+1B2k-1C2k-1D2k–1-1E2k+1F2k+1-1G2k-1+1H2k【解答】B，C，A【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。⑹一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。An=h+mBh+m=2nCm=h-1Dn=2m-1【解答】D【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。 ⑺任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树。⑻如果T"是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T"中结点的（）序列，T中结点的后序序列就是T"中结点的（）序列。A前序B中序C后序D层序【解答】A，B⑼设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（）个结点，根结点的左子树上有（）个结点。An1-1Bn1Cn1+n2+n3Dn2+n3+n4【解答】D，A【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。（10）讨论树、森林和二叉树的关系，目的是为了（）。A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转换成二叉树D体现一种技巧，没有什么实际意义【解答】B3.判断题⑴在线索二叉树中，任一结点均有指向其前趋和后继的线索。【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。⑵在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。【解答】对。由前序遍历的操作定义可知。⑶二叉树是度为2的树。【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。⑷由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。⑸用一维数组存储二叉树时，总是以前序遍历存储结点。【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。4．证明：对任一满二叉树，其分枝数B＝2(n0-1)。（其中，n0为终端结点数） 【解答】因为在满二叉树中没有度为1的结点，所以有：n=n0+n2设B为树中分枝数，则n=B+1所以B=n0+n2-1再由二叉树性质：n0=n2+1代入上式有：B=n0+n0-1-1=2(n0-1)5．证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。【解答】证明采用归纳法。设二叉树的前序遍历序列为a1a2a3…an，中序遍历序列为b1b2b3…bn。当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1=b1，可以唯一确定该二叉树；假设当n<=k时，前序遍历序列a1a2a3…ak和中序遍历序列b1b2b3…bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3…akak+1和中序遍历序列b1b2b3…bkbk+1可唯一确定一棵二叉树。在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2…bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3…ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3…ai和中序遍历序列b1b2…bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2…ak+1和中序遍历序列bi+1bi+2…bk+1唯一确定了根结点的右子树。6．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？【解答】设该树的总结点数为n，则n=n0+n1+n2+……+nm又：n=分枝数+1=0×n0+1×n1+2×n2+……+m×nm+1由上述两式可得：n0=n2+2n3+……+(m-1)nm+17．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。【解答】二叉树的构造过程如图5-12所示。 8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图5-13所示。树的带权路径长度为：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1209．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。10．算法设计 ⑴设计算法求二叉树的结点个数。【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的“访问”操作改为“计数操作”，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。具体算法如下：⑵设计算法按前序次序打印二叉树中的叶子结点。【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：⑶设计算法求二叉树的深度。【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下： ⑷编写算法，要求输出二叉树后序遍历序列的逆序。【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：⑸以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：⑹以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下： ⑺一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下：①每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。②从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。具体算法如下：⑻编写算法交换二叉树中所有结点的左右子树。【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。具体算法如下： ⑼以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。树的孩子兄弟表示法中的结点结构定义如下：templatestructTNode{Tdata;TNode*firstchild,*rightsib;};具体算法如下： 学习自测及答案1．前序遍历和中序遍历结果相同的二叉树是（）。A根结点无左孩子的二叉树B根结点无右孩子的二叉树C所有结点只有左子树的二叉树D所有结点只有右子树的二叉树【解答】D2．由权值为{3,8,6,2,5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。A24B48C53D72【解答】C3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]【解答】D4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。An0=n2-1Bn0=n2Cn0=n2+1D没有规律【解答】C5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。An=h+mBh+m=2nCm=h-1Dn=2h-1【解答】D6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。AhBh+1Ch或h+1D任意【解答】C7．假定一棵度为3的树中结点数为50，则其最小高度应为。A3B4C5D6【解答】C8．在线索二叉树中，一个结点是叶子结点的充要条件为（）。A左线索标志为0，右线索标志为1B左线索标志为1，右线索标志为0C左、右线索标志均为0D左、右线索标志均为1【解答】C9．对于一棵具有n个结点的树，其所有结点的度之和为（）。【解答】n-1 10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。【解答】11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？【解答】共有5种二叉树可以得到这一结果，如图5-15所示。12．试找出分别满足下列条件的所有二叉树：⑴前序序列和中序序列相同。⑵中序序列和后序序列相同。⑶前序序列和后序序列相同。【解答】⑴空二叉树、只有一个根结点的二叉树和右斜树。⑵空二叉树、只有一个根结点的二叉树和左斜树。⑶空二叉树、只有一个根结点的二叉树13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。 14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下：15．设计算法，判断一棵二叉树是否为完全二叉树。【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足：⑴若某结点没有左孩子，则其一定没有右孩子；⑵若某结点无右孩子，则其所有后继结点一定无孩子。若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。具体算法如下： 第6章图课后习题讲解1.填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 （10）在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi,vj,vk的相对次序为（）。【解答】vi,vj,vk【分析】对由顶点vi,vj,vk组成的图进行拓扑排序。2.选择题⑴在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A1/2B1C2D4【解答】C【分析】设无向图中含有n个顶点e条边，则。⑵n个顶点的强连通图至少有（）条边，其形状是（）。AnBn+1Cn-1Dn×(n-1)E无回路F有回路G环状H树状【解答】A，G⑶含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A1Bn/2Cn-1Dn【解答】C【分析】若超过n-1，则路径中必存在重复的顶点。⑷对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。AnB(n-1)2Cn-1Dn2【解答】D⑸图的生成树（），n个顶点的生成树有（）条边。A唯一B不唯一C唯一性不能确定DnEn+1Fn-1【解答】C，F⑹设无向图G=(V,E)和G"=(V",E")，如果G"是G的生成树，则下面的说法中错误的是（）。AG"为G的子图BG"为G的连通分量CG"为G的极小连通子图且V=V"DG"是G的一个无环子图【解答】B【分析】连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。⑺G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A6B7C8D9【解答】D【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。⑻最小生成树指的是（）。A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图【解答】C ⑼判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A求关键路径的方法B求最短路径的方法C广度优先遍历算法D深度优先遍历算法【解答】D【分析】当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。⑽下面关于工程计划的AOE网的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动都提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完【解答】B【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。3.判断题⑴一个有向图的邻接表和逆邻接表中的结点个数一定相等。【解答】对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。⑵用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。⑶图G的生成树是该图的一个极小连通子图【解答】错。必须包含全部顶点。⑷无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的【解答】错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。⑸对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。⑹在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。⑺若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。【解答】对。参见第11题的证明。⑻在AOE网中一定只有一条关键路径?【解答】错。AOE网中可能有不止一条关键路径，他们的路径长度相同。4．n个顶点的无向图，采用邻接表存储，回答下列问题?⑴图中有多少条边？ ⑵任意两个顶点i和j是否有边相连？⑶任意一个顶点的度是多少?【解答】⑴边表中的结点个数之和除以2。⑵第i个边表中是否含有结点j。⑶该顶点所对应的边表中所含结点个数。5．n个顶点的无向图，采用邻接矩阵存储，回答下列问题：⑴图中有多少条边？⑵任意两个顶点i和j是否有边相连？⑶任意一个顶点的度是多少？【解答】⑴邻接矩阵中非零元素个数的总和除以2。⑵当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。⑶计算邻接矩阵上该顶点对应的行上非零元素的个数。6．证明：生成树中最长路径的起点和终点的度均为１。【解答】用反证法证明。设v1,v2,…,vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1,v2,…,vk,v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。【解答】邻接矩阵表示如下：深度优先遍历序列为：v1v2v3v5v4v6广度优先遍历序列为：v1v2v4v6v3v5邻接表表示如下： 8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。【解答】按Prim算法求最小生成树的过程如下：按Kruskal算法求最小生成树的过程如下： 9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。【解答】从源点v1到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v32510．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。【解答】从源点v1到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度 v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v44511．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。12.算法设计⑴设计算法，将一个无向图的邻接矩阵转换为邻接表。【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。邻接矩阵存储结构定义如下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组intvertexNum,arcNum;//图的顶点数和边数};邻接表存储结构定义如下：constintMaxSize=10;structArcNode//定义边表结点{intadjvex;//邻接点域ArcNode*next;};templatestructVertexNode//定义顶点表结点{Tvertex;ArcNode*firstedge;}; structAdjList{VertexNodeadjlist[MaxSize];intvertexNum,arcNum;//图的顶点数和边数};具体算法如下：⑵设计算法，将一个无向图的邻接表转换成邻接矩阵。【解答】在邻接表上顺序地取每个边表中的结点，将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下： ⑶设计算法，计算图中出度为零的顶点个数。【解答】在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下：⑷以邻接表作存储结构，设计按深度优先遍历图的非递归算法。【解答】参见6.2.1。⑸已知一个有向图的邻接表，编写算法建立其逆邻接表。【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头结点firstedge域置空，然后逐行将表头结点的邻接点进行转化。 ⑹分别基于深度优先搜索和广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。【解答】⑴基于深度优先遍历：⑵基于广度优先遍历： 学习自测及答案1．某无向图的邻接矩阵A=，可以看出，该图共有（）个顶点。A.3B.6C.9D.以上答案均不正确【解答】A2．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）A上三角矩阵B下三角矩阵C对称矩阵D无规律【解答】C，D3．下列命题正确的是（）。A一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一【解答】B4．十字链表适合存储（），邻接多重表适合存储（）。【解答】有向图，无向图5.在一个具有n个顶点的有向完全图中包含有（）条边：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】B6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。【解答】2(n-1)7．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（）个非零矩阵元素。【解答】10008．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。AkBnCn-kD1【解答】C9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。A逆拓扑有序B拓扑有序C无序D深度优先遍历序列【解答】A10.关键路径是AOE网中（）。A从源点到终点的最长路径B从源点到终点的最长路径C最长的回路D最短的回路【解答】A11.已知无向图G的邻接表如图6-10所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。 【解答】深度优先遍历序列为：1，2，3，4，5，6对应的生成树为：广度优先遍历序列为：1，2，4，3，5，6对应的生成树为：12.已知已个AOV网如图6-11所示，写出所有拓扑序列。【解答】拓扑序列为：v0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。 第7章查找技术课后习题讲解1.填空题⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。【解答】顺序存储和链接存储，顺序存储，按关键码有序⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。【解答】1，7【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。⑶对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。【解答】8，59/15【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。【解答】4【分析】在折半查找判定树中，第3层共有4个结点。⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=kmod7，则元素48的同义词是（）。【解答】62【分析】H(48)=H(62)=6⑹在散列技术中，处理冲突的两种主要方法是（）和（）。【解答】开放定址法，拉链法⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻与其他方法相比，散列查找法的特点是（）。【解答】通过关键码计算记录的存储地址，并进行一定的比较2.选择题⑴静态查找与动态查找的根本区别在于（）。A它们的逻辑结构不一样B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。As=bBs>bCs【解答】D，D【分析】此题没有指明是平均性能。例如，在有序表中查找最大元素，则顺序查找比折半查找快，而平均性能折半查找要优于顺序查找，查找不成功的情况也类似。⑶长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。A37/12B62/13C39/12D49/13【解答】A，B【分析】画出长度为12的折半查找判定树，判定树中有12个内结点和13个外结点。⑷用n个键值构造一棵二叉排序树，其最低高度为（）。An/2BnClog2nDlog2n+1【解答】D【分析】二叉排序树的最低高度与完全二叉树的高度相同。⑸二叉排序树中，最小值结点的（）。A左指针一定为空B右指针一定为空C左、右指针均为空D左、右指针均不为空【解答】A【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。⑹散列技术中的冲突指的是（）。A两个元素具有相同的序号B两个元素的键值不同，而其他属性相同C数据元素过多D不同键值的元素对应于相同的存储地址【解答】D⑺设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（）。 A8B3C5D9【解答】A【分析】元素15、38、61、84分别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。⑻在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。A一定都是同义词B一定都不是同义词C不一定都是同义词D都相同【解答】C【分析】采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。3.判断题⑴二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。【解答】错。分析二叉排序树的定义，是左子树上的所有结点的值都小于根结点的值，右子树上的所有结点的值都大于根结点的值。例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序树。⑵二叉排序树的查找和折半查找的时间性能相同。【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。⑶若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。【解答】错。在二叉排序树中，最小元素所在结点一定是中序遍历序列中第一个被访问的结点，即是二叉树的最左下结点，但可能有右子树。最大元素所在结点一定是中序遍历序列中最后一个被访问的结点，即是二叉树的最右下结点，但可能有左子树。如图7-8所示，5是最小元素，25是最大元素，但5和25都不是叶子结点。⑷散列技术的查找效率主要取决于散列函数和处理冲突的方法。【解答】错。更重要的取决于装填因子，散列表的平均查找长度是装填因子的函数。 ⑸当装填因子小于1时，向散列表中存储元素时不会引起冲突。【解答】错。装填因子越小，只能说明发生冲突的可能性越小。4．分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找关键码e和g的过程。【解答】查找关键码e的过程如图7-9所示，查找关键码g的过程如图7-10所示。5．画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度。【解答】参见7.2.1。 6．将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。【解答】二叉排序树如图7-11所示，其平均查找长度=1+2×2+3×2+4×2=19/77．一棵二叉排序树的结构如图7-12所示，结点的值为1～8，请标出各结点的值。【解答】二叉排序树中各结点的值如图7-13所示。8．已知散列函数H(k)=kmod12，键值序列为(25,37,52,43,84,99,120,15,26,11,70,82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。【解答】H(25)=1,H(37)=1,H(52)=4,H(43)=7,H(84)=0,H(99)=3,H(120)=0,H(15)=3,H(26)=2,H(11)=11,H(70)=10,H(82)=10构造的开散列表如下：平均查找长度ASL=(8×1+4×2)/12=16/129.算法设计⑴设计顺序查找算法，将哨兵设在下标高端。 【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下：⑵编写算法求给定结点在二叉排序树中所在的层数。【解答】根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。具体算法如下：⑶编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。【解答】设两个结点分别为A和B，根据题目要求分下面情况讨论：⑴若A为根结点，则A为公共祖先；⑵若A->datadata且root->datadata，root为公共祖先；⑶若A->datadata且B->datadata，则到左子树查找；⑷若A->data>root->data且B->data>root->data，则到右子树查找。具体算法如下：⑷设计算法判定一棵二叉树是否为二叉排序树。【解答】对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。 具体算法如下：学习自测及答案1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（）次比较后查找成功。A2B3C4D5【解答】A2．已知10个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为62的结点所需比较次数为（）。A2B3C4D5【解答】B3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。A4B5C6D7【解答】B4．按（）遍历二叉排序树得到的序列是一个有序序列。A前序B中序C后序D层次【解答】B5．将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T"中，则T与T"是相同的，这种说法是否正确？【解答】正确6.一棵高度为h的平衡二叉树，最少含有个结点。A2hB2h-1C2h+1D2h-1【解答】D7．在散列函数H(k)=kmodm中，一般来讲，m应取（）。A奇数B偶数C素数D充分大的数【解答】C 8．已知关键码序列为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec），散列表的地址空间为0~16，设散列函数为H(x)=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】H(Jan)=10/2=5,H(Feb)=6/2=3,H(Mar)=13/2=6,H(Apr)=1/2=0H(May)=13/2=6,H(Jun)=10/25,H(Jul)=10/25,H(Aug)=1/2=0H(Sep)=19/2=8,H(Oct)=15/2=7,H(Nov)=14/2=7,H(Dec)=4/2=2采用线性探测法处理冲突，得到的闭散列表如下：平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/12第九题9.试推导含有12个结点的平衡二叉树的最大深度，并画出以棵这样的树。【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目，则：F1=1，F2=2，…，Fn=Fn-2+Fn-1+1。含有12个结点的平衡二叉树的最大深度为5，例如： 第8章排序技术课后习题讲解1.填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。在（）情况下比较次数最多，其比较次数为（）。【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。⑷对一组记录（54,38,96,23,15,72,60,45,83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。2.选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。⑵下列序列中，（）是执行第一趟快速排序的结果。A[da，ax，eb，de，bb]ff[ha，gc]B[cd，eb，ax，da]ff[ha，gc，bb] C[gc，ax，eb，cd，bb]ff[da，ha]D[ax，bb，cd，da]ff[eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。⑶对初始状态为递增有序的序列进行排序，最省时间的是（），最费时间的是（）。已知待排序序列中每个元素距其最终位置不远，则采用（）方法最节省时间。A堆排序B插入排序C快速排序D直接选择排序【解答】B，C，B【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。⑷堆的形状是一棵（）。A二叉排序树B满二叉树C完全二叉树D判定树【解答】C【分析】从逻辑结构的角度来看，堆实际上是一种完全二叉树的结构。⑸当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（），就平均时间而言，（）最佳。A直接插入排序B起泡排序C简单选择排序D快速排序【解答】A，D⑹设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（）方法最好。A快速排序B堆排序C希尔排序D归并排序【解答】B【分析】堆排序不必将整个序列排序即可确定前若干个最大（或最小）元素。⑺设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，则（）是起泡排序一趟扫描的结果，（）是增量为4的希尔排序一趟扫描的结果，（）二路归并排序一趟扫描的结果，（）是以第一个元素为轴值的快速排序一趟扫描的结果，（）是堆排序初始建堆的结果。A（F，H，C，D，P，A，M，Q，R，S，Y，X）B（P，A，C，S，Q，D，F，X，R，H，M，Y）C（A，D，C，R，F，Q，M，S，Y，P，H，X）D（H，C，Q，P，A，M，S，R，D，F，X，Y）E（H，Q，C，Y，A，P，M，S，D，R，F，X）【解答】D，B，E，A，C【分析】此题需要按字典序比较，并且需要掌握各种排序方法的执行过程。⑻排序的方法有很多种，（）法从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较，当被比较的两元素为逆序时，进行交换；（）和（）是基于这类方法的两种排序方法，而（）是比（）效率更高的方法；（）法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。A选择排序B快速排序C插入排序D起泡排序E归并排序F堆排序【解答】C，A，D，B，B，D，F⑼快速排序在（）情况下最不利于发挥其长处。A待排序的数据量太大B待排序的数据中含有多个相同值C待排序的数据已基本有序D待排序的数据数量为奇数 【解答】C【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否含有多个相同值，待排序的数据数量为奇数或偶数都没有影响。⑽（）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。A归并排序B插入排序C快速排序D选择排序【解答】D3.判断题⑴如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。【解答】错。一种排序算法适合于某种特定的数据环境，有时对排序的稳定性没有要求。⑵当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。【解答】对。此时着重考虑元素的移动次数。⑶对n个记录的集合进行快速排序，所需要的附加空间是Ο(n)。【解答】错。最坏情况下是Ο(n)。⑷堆排序所需的时间与待排序的记录个数无关。【解答】错。堆排序最好、最坏及平均时间均为Ο(nlog2n)，是待排序的记录个数n的函数。一般来说，待排序的记录个数越多，排序所消耗的时间也就越多。⑸设有键值序列（k1,k2,…,kn），当i>n/2时，任何一个子序列（ki,ki+1,…,kn）一定是堆。【解答】对。当i>n/2时，ki,ki+1,…,kn均是叶子结点，所以一定是堆。4．已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，写出插入排序、起泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果。【解答】用上述排序方法的每趟结果如下： 5．对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。【解答】最好情况：4，7，5，6，3，1，2最坏情况：7，6，5，4，3，2，16．判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图表示建堆的过程。⑴（1，5，7，25，21，8，8，42）⑵（3，9，5，8，4，17，21，6）【解答】序列⑴是堆，序列⑵不是堆，调整为堆（假设为大根堆）的过程如图8-5所示。7．已知下列各种初始状态（长度为n）的元素，试问当利用直接插入排序进行排序时，至少需要进行多少次比较（要求排序后的记录由小到大顺序排列）？⑴关键码从小到大有序（key1key2>…>keyn）。⑶奇数关键码顺序有序，偶数关键码顺序有序（key1⑷前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1A[i+1]，则将二者交换，然后重复上述排序过程，直至整个数组有序。编写算法实现上述奇偶交换排序。【解答】具体算法如下： 第9章索引技术课后习题讲解1.填空题⑴在索引表中，每个索引项至少包含（）和（）等信息【解答】关键码，关键码对应的记录在存储器中的位置⑵在线性索引中，（）称为稠密索引【解答】若文件中的每个记录对应一个索引项⑶分块有序是指将文件划分为若干块，（）无序，（）有序。【解答】块内，块间⑷在分块查找方法中，首先查找（），然后查找相应的（）。【解答】索引表，块⑸在10阶B—树中根结点所包含的关键码个数最多为（），最少为（）。【解答】9，1【分析】m阶的B－树中每个结点至多有m棵子树，若根结点不是终端结点，则至少有两棵子树，每个结点中关键码的个数为子树的个数减1。⑹一棵5阶B—树中，除根结点外，每个结点的子树树目最少为（），最多为（）。【解答】3，5【分析】m阶的B－树中每个结点至多有m棵子树，除根结点之外的所有非终端结点至少有?m/2?棵子树。⑺对于包含n个关键码的m阶B—树，其最小高度是（），最大高度是（）。【解答】[logm(n+1)]，[logm/2(n+1)/2]⑻在一棵B—树中删除关键码，若最终引起树根结点的合并，则新树比原树的高度（）。【解答】减少1层⑼在一棵高度为h的B—树中，叶子结点处于第（）层，当向该B—树中插入一个新关键码时，为查找插入位置需读取（）个结点。【解答】h+1，h【分析】B－树的叶子结点可以看作是外部结点（即查找失败）的结点，通常称为外结点。实际上这些结点不存在，指向这些结点的指针为空，B－树将记录插入在终端结点中。⑽对于长度为n的线性表，若采用分块查找（假定总块数和每块长度均接近，用顺序查找确定所在块），则时间复杂性为（）。【解答】O()2.判断题⑴在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。 【解答】对。分块查找的平均查找长度不仅和文件中记录的个数n有关，而且和每一块中的记录个数t有关，当t取时，ASL取最小值+1。⑵B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。【解答】错。B—树不能进行顺序查找。⑶对于B—树中任何一个非叶结点中的某个关键码k来说，比k大的最小关键码和比k小的最大关键码一定都在叶结点中。【解答】对。⑷在索引顺序表的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。【解答】对。因为索引表有序。⑸m阶B—树中每个结点的子树个数都大于或等于?m/2?。【解答】错。m阶的B－树中除根结点之外的所有非终端结点至少有[m/2]棵子树。若根结点不是终端结点，则至少有两棵子树。⑹m阶B—树中任何一个结点的左右子树的高度都相等。【解答】对。B树都是树高平衡的。3．对图9-2所示的3阶B—树，分别给出插入关键码为2，12，16，17和18之后的结果。【解答】插入关键码为2，12，16，17，18之后的结果分别如图9-3中(a)、(b)、(c)、(d)、(e)所示。 4．对上题所示的3阶B—树，分别给出删除关键码为4，8，9之后的结果。【解答】删除关键码为4，8，10之后的结果如图9-4(a)，(b)，(c)所示： 5．为什么在内存中使用的B—树通常是3阶的，而不使用更高阶的B—树？【解答】作为外存上的动态查找，B—树比平衡二叉树的性能要好，但若要作为内存中的查找表，B—树却不一定比平衡二叉树性能好，因为查找等操作的时间性能在m阶B—树上是O(mlogtn）=O(log2n*(m/log2t))（n为记录个数），而m/log2t>1，故m较大时，O(mlog2n)比平衡的二叉排序树上相应操作的时间O(log2n)大得多。因此，仅在内存中使用的B—树必须取较小的m，通常取最小值m=3。6．设有10000个记录，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？【解答】每个子表的大小应为。学习自测及答案1．在索引顺序表中，首先查找（），然后再查找相应的（），其平均查找长度等于（）。【解答】索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和2．既希望较快的查找又便于线性表动态变化的查找方法是（）。A顺序查找B折半查找C散列查找D索引顺序查找【解答】D3．在一个3阶的B—树上，每个结点所含的子树数目最多为（）。【解答】34．在一棵m阶的B—树中，当将一个关键码插入某结点而引起该结点分裂时，此结点原有（）个关键码；若删去某结点中的一个关键码，而导致结点合并时，该结点原有（）个关键码。【解答】m-1，?m/2?-15．当向B—树中插入关键码时，可能引起结点的（），最终可能导致整个B-树的高度（），当从B—树中删除关键码时，可能引起结点（），最终可能导致整个B—树的高度（）。【解答】分裂，增加1，合并，减少16．在9阶B—树中，除根结点以外其他非叶子结点中的关键码个数不少于（）。【解答】47．当向一棵m阶的B—树做插入操作时，若一个结点中的关键字个数等于（），则必须分裂为两个结点。AmBm-1Cm+1Dm/2【解答】A8．在一个5阶的B—树上，每个非终端结点所含的子树数最少为（）。A2B3C4D5 【解答】B9.给定一组记录，其关键码为字母。记录按照下面的顺序插入一棵空的B—树中：C，S，D，T，A，M，P，I，B，W，N，G，V，R，K，E，H，O，L，J。请画出插入这些记录后的3阶B—树。【解答】最后的B—树如图9-5所示。10．已知一个B+树有5个叶子结点，每个叶子结点中的关键码如图9-6所示，请画出这棵3阶B+树，然后在此3阶B+树中插入关键码65，再画出插入后的B+树。【解答】该B+树如图9-7所示，插入关键码65后，B+树如图9-8所示。 '