数据结构第4版习题和实验参考答案解析数据结构复习资料（完整版）c语言版

..数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。2、数据的物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示〔或映像。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成,并包括一组相关的服务〔或称操作。它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽〔独立于计算机。4、算法：是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。5、在数据结构中,从逻辑上可以把数据结构分成〔CA、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于〔AA、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为〔E,删除一个元素需要移动的元素的个数为〔A。A、<n-1>/2B、nC、n+1D、n-1E、n/2F、<n+1>/2G、<n-2>/23、"线性表的逻辑顺序与存储顺序总是一致的。"这个结论是〔BA、正确的B、错误的C、不一定,与具体的结构有关4、线性表采用链式存储结构时,要求内存中可用存储单元的地址〔DA、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是〔BA、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是〔AA、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足〔CA、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是〔BA、O<1>B、O<n>C、O<n2>D、O<nlog2n>9、在一个单链表中,若删除p所指结点的后继结点,则执行〔AA、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p=p->next->next;10、在一个单链表中,若在p所指结点之后插入s所指结点,则执行〔BA、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中,已知q是p的前趋结点,若在q和p之间插入结点s,则执行〔CA、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中,第一个结点没有前趋结点,其余每个结点有且只有1个前趋结点。栈和队列1、在栈操作中,输入序列为〔A,B,C,D,不可能得到的输出数列是〔DA、〔A,B,C,DB、〔D,C,B,AC、〔A,C,D,BD、〔C,A,D,B2、设栈ST用顺序存储结构表示,则栈ST为空的条件〔BA、ST.top=ST.base<>0B、ST.top=ST.base==0C、ST.top=ST.base<>nD、ST.top=ST.base==n3、向一个栈顶指针为HS的链栈中插入一个s结点时,执行〔CA、HS->next=s;B、s->next=HS->next;HS->next=s;C、s->next=HS;HS=S;D、s->next=HS;HS=HS->next;4、从一个栈顶指针为HS的链栈中删除一个结点,用x保存被删结点的值,则执行〔CA、x=HS;HS=HS->next;B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next;D、s->next=HS;HS=HS->next;5、用单链表表示的链示队列的队头在链表的〔A位置。A、链头B、链尾C、链中6、判定一个链队列Ｑ〔最多元素个数为n为空的条件是〔AＡ、Ｑ.front==Q.rearB、Q.front!=Q.rearC、Q.front==<Q.rear+1>%nD、Q.front!=<Q.rear+1>%n7、在链队列Ｑ中,插入要所指结点需顺序执行的指令是〔BA、Q.front->next=s;f=s;B、Q.rear->next=s;Q.rear=s;C、s->next=Q.rear;Q.rear=s;D、s->next=Q.front;Q.front=s;8、在一个链队列Q中,删除一个结点需要执行的指令是〔CA、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;9、栈和队列的共同点〔CA、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10、栈的特点是_先进后出,队列的特点是先进先出11、线性表、栈和队列都是线性结构,可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。串和数组1、设串s1=’ABCDEFG’,s2=’PQRST’,函数Concat<x,y>返回x和y串的连接串,Substr<s,I,j>返回串s从序号i开始的j个字符组成的子串,length<s>返回串s的长度,则Concat<Substr<s1,2,length<s2>,Substr<s1,length<s2>,2>>的结果串是〔DA、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF2、串是一种特殊的线性表,其特殊性体现在〔DA、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符3、设有两个串p和q,求q在p中首次出现的位置的运算称作〔BA、连接B、模式匹配C、求子串联D、求串长4、串的两种最基本的存储方式是顺序存储方式和链接存储方式。树和二叉树1、树最合适用来表示〔BA、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据2、按照二叉树的定义,具有3个结点的二叉树有〔C种。A、3B、4C、5D、63、在一棵有n个结点的二叉树中,若度为2的结点数为n2,度为1的结点数为n1,度为0的结点数为n0,则树的最大高度为〔E,其叶结点数为〔G；树的最小高度为〔B,其叶结点数为〔G；若采用链表存储结构,则有〔I个空链域。A、n/2B、[log2n]+1C、log2nD、nE、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1J、n1K、n2L、n1+14、在一棵二叉树上第5层的结点数最多为〔B。〔假设根结点的层数为0A、8B、16C、15D、325、深度为5的二叉树至多有〔C个结点。A、16B、32C、31D、106、在一非空二叉树的中序遍历序列中,根结点的右边〔AA、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点7、一棵完全二叉树按层次遍历的序列为ABCDEFGHI,则在先序遍历中结点E的直接前趋为〔D,后序遍历中结点B的直接后继是〔E。A、BB、DC、AD、IE、FF、C8、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是〔DA、acbedB、decabC、deabcD、cedba9、在树形结构中,树根结点没有___前趋________结点,其余每个结点有且只有_______1______个前趋结点；叶子结点没有______后继___________结点,其余每个结点的后继结点可以__任意多个____。10、有一棵树如图所示,回答下面的问题：K1K1K7K6K5K2K3K4这棵树的根结点是____K1_______,这棵树的叶子结点是__K2,K5,K7,K4______；结点k3的度是____2________;这棵树的度为___3_______；这棵树的深度是_____4_________；结点k3的子女是______K5,K6_____；结点k3的父结点是_____K1_________.11、已知一棵二叉树的中序遍历序列为CDBAEGF,前序遍历序列为ABCDEFG,试问能不能惟一确定一棵二叉树,若能请画出该二叉树。若给定前序遍历序列和后序遍历序列,能否惟一确定一棵二叉树,说明理由。答：=1\*GB2⑴由中序遍历序列和前序遍历序列或中序遍历序列和后序遍历序列可以惟一确定一棵二叉树。基本思想是前序〔后序定根,中序分左右。对于给定的前序和中序序列。可确定根结点为A,以A为根的左子树结点为B,C,D,右子树结点为E,F,G。进一步可确定所有子树的根结点,因而也就确定了整个二叉树。对应的二叉树如图所示：FFADGFECB=2\*GB2⑵由前序遍历和后序遍历序列不能惟一确定一棵二叉树。如图所示为4棵不同的二叉树,它们的前序遍历序列都是ABC,而后序遍历序列都是CBA。AACBCBAACBACB12、设二叉树bt的存储结构如下：12345678910left00237580101datajhfdbacegiright0009400000其中bt为树根结点指针,left,right分别为结点的左右孩子指针域,data为结点的数据域,请完成下列各题：=1\*GB2⑴画出二叉树bt的逻辑结构=2\*GB2⑵写出按前序、中序和后序遍历二叉树bt所得到的结点序列。答：=1\*GB2⑴二叉树bt的逻辑结构如图所示：1212ajighfdecb=2\*GB2⑵前序遍历：abcedfhgij中序遍历：ecbhfdjiga后序遍历：echfjigdba13、给定一棵以二叉链表存储结构表示的二叉树,其根结点指针为T,试写出求二叉树的叶子数目的算法。intCountLeaf<BiTreeT>{//返回指针T所指二叉树中所有叶子结点个数if<!T>return0;if<!T->lchild&&!T->rchild>return1;else{m=CountLeaf<T->lchild>;n=CountLeaf<T->rchild>;return<m+n>;}//else}//CountLeaf14、给定一棵以二叉链表存储结构表示的二叉树,其根结点指针为T,试写出求二叉树的深度的算法。intDepth<BiTreeT>{//返回二叉树的深度if<!T>depthval=0;else{depthLeft=Depth<T->lchild>;depthRight=Depth<T->rchild>;depthval=1+<depthLeft>depthRight?depthLeft:depthRight>;}returndepthval;}图1、一个有n个顶点的无向图最多有〔C条边。A、nB、n<n-1>C、n<n-1>/2D、2n2、具有6个顶点的无向图至少应有〔A条边才能确保是一个连通图。A、5B、6C、7D、83、存储稀疏图的数据结构常用的是〔CA、邻接矩阵B、三元组C、邻接表D、十字链表4、在有向图的邻接表存储结构中,顶点V在表结点中出现的次数是〔CA、顶点V的度B、顶点V的出度C、顶点V的入度D、依附于顶点V的边数5、用DFS遍历一个无环有向图,并在DFS算法退栈返回时,打印出相应的顶点,则输出的顶点序列是〔AA、逆拓扑有序的B、拓扑有序的C、无序的6、已知一个图如图所示,若从顶点a出发按深度优先搜索法进行遍历,则可能得到的一种顶点序列为〔D,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为〔B。=1\*GB2⑴A、abecdfB、acfebdC、acebfdD、acfdeb=2\*GB2⑵A、abcedfB、abcefdC、abedfcD、acfdebCCacfdeb7、采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的〔DA、中序遍历B、先序遍历C、后序遍历D、按层遍历8、已知一个图如图所示,则由该图得到的一种拓扑序列为〔A1165432A、V1,V4,V6,V2,V5,V3B、V1,V2,V3,V4,V5,V6C、V1,V4,V2,V3,V6,V5D、V1,V2,V4,V6,V3,V59、在图形结构中,每个结点的前趋结点数和后续结点数可以___任意多个_______。10、在AOE网中,从源点到汇点各活动时间总和最长的路径称为关键路径。11、给出图G,如图所示：11111098765432〔1给出图G的邻接表〔画图即可〔2在你给出的邻接表的情况下,以顶点V4为根,画出图G的深度优先生成树和广度优先生成树。〔3将你画出的广度优先生成树转换为对应的二叉树。答：〔1图的邻接表如下图所示：略〔2以顶点V4为根的深度优先生成树和广度优先生成树如图所示11111098765432dd1111098765432〔3广度优先生成树转换成二叉树如下图所示111109117863452附录习题及实验参考答案习题1参考答案1.1.选择题<1>.A.<2>.A.<3>.A.<4>.B.,C.<5>.A.<6>.A.<7>.C.<8>.C.<9>.B.<10.>A.1.2.填空题<1>.数据关系<2>.逻辑结构物理结构<3>.线性数据结构树型结构图结构<4>.顺序存储链式存储索引存储散列表〔Hash存储<5>.变量的取值范围操作的类别<6>.数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系<7>.关系网状结构树结构<8>.空间复杂度和时间复杂度<9>.空间时间<10>.Ο<n>1.3名词解释如下：数据：数据是信息的载体,是计算机程序加工和处理的对象,包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位,数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述,是指令的有限序列。1.4语句的时间复杂度为：<1>Ο<n2><2>Ο<n2><3>Ο<n2><4>Ο<n-1><5>Ο<n3>1.5参考程序：main<>{intX,Y,Z；scanf<"%d,%d,%d",&X,&Y,Z>；if<X>=Y>if<X>=Z>if<Y>=Z>{printf<"%d,%d,%d",X,Y,Z>;}else{printf<"%d,%d,%d",X,Z,Y>;}else{printf<"%d,%d,%d",Z,X,Y>;}elseif<Z>=X>if<Y>=Z>{printf<"%d,%d,%d",Y,Z,X>;}else{printf<"%d,%d,%d",Z,Y,X>;}else{printf<"%d,%d,%d",Y,X,Z>;}}1.6参考程序：main<>{inti,n;floatx,a[],p;printf<"\nn=">;scanf<"%f",&n>;printf<"\nx=">;scanf<"%f",&x>;for<i=0;i<=n;i++>scanf<"%f",&a[i]>;p=a[0];for<i=1;i<=n;i++>{p=p+a[i]*x;x=x*x;}printf<"%f",p>’}习题2参考答案2.1选择题<1>.C.<2>.B.<3>.B.<4>.B.5.D.6.B.7.B.8.A.9.A.10.D.2.2.填空题<1>.有限序列<2>.顺序存储和链式存储<3>.Ｏ<n>O<n><4>.n-i+1n-i<5>.链式<6>.数据指针<7>.前驱后继<8>.Ο<1>Ο<n><9>.s->next=p->next;p->next=s;<10>.s->next2.3.解题思路：将顺序表A中的元素输入数组a,若数组a中元素个数为n,将下标为0,1,2,…,〔n-1/2的元素依次与下标为n,n-1,…,〔n-1/2的元素交换,输出数组a的元素。参考程序如下：main<>{inti,n;floatt,a[];printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<=n-1;i++>scanf<"%f",&a[i]>;for<i=0;i<=<n-1>/2;i++>{t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}for<i=0;i<=n-1;i++>printf<"%f",a[i]>;}2.4算法与程序：main<>{inti,n;floatt,a[];printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<n;i++>scanf<"%f",&a[i]>;for<i=1;i<n;i++>if<a[i]>a[0]{t=a[i];a[i]=a[0];a[0]=t;}printf<"%f",a[0]>;for<i=2;i<n;i++>if<a[i]>a[1]{t=a[i];a[i]=a[1];a[1]=t;}printf<"%f",a[0]>;}2.5算法与程序：main<>{inti,j,k,n;floatx,t,a[];printf<"\nx=">;scanf<"%f",&x>;printf<"\nn=">;scanf<"%f",&n>;for<i=0;i<n;i++>scanf<"%f",&a[i]>;//输入线性表中的元素for<i=0;i<n;i++>{//对线性表中的元素递增排序k=i;for<j=i+1;j<n;j++>if<a[j]<a[k]>k=j;if<k<>j>{t=a[i];a[i]=a[k];a[k]=t;}}for<i=0;i<n;i++>//在线性表中找到合适的位置if<a[i]>x>break;for<k=n-1;k>=i;i-->//移动线性表中元素,然后插入元素xa[k+1]=a[k];a[i]=x;for<i=0;i<=n;i++>//依次输出线性表中的元素printf<"%f",a[i]>;}2.6算法思路：依次扫描A和B的元素,比较A、B当前的元素的值,将较小值的元素赋给C,如此直到一个线性表扫描完毕,最后将未扫描完顺序表中的余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：voidmerge<SeqListA,SeqListB,SeqList*C>{inti,j,k；i=0；j=0；k=0；while<i<=A.last&&j<=B.last>if<A.data[i]<=B.data[j]>C->data[k++]=A.data[i++]；elseC->data[k++]=B.data[j++]；while<i<=A.last>C->data[k++]=A.data[i++]；while<j<=B.last>C->data[k++]=B.data[j++]；C->last=k-1；}2.7算法思路：依次将A中的元素和B的元素比较,将值相等的元素赋给C,如此直到线性表扫描完毕,线性表C就是所求递增有序线性表。算法：voidmerge<SeqListA,SeqListB,SeqList*C>{inti,j,k；i=0；j=0；k=0；while<i<=A.last>while〔j<=B.last>if<A.data[i]=B.data[j]>C->data[k++]=A.data[i++]；C->last=k-1；}习题3参考答案3.1.选择题<1>.D<2>.C<3>.D<4>.C<5>.B<6>.C<7>.C<8>.C<9>.B<10>.AB<11>.D<12>.B<13>.D<14>.C<15>.C<16>.D<17>.B<18>.C<19>.C<20>.C3.2.填空题FILO,FIFO-1,34X*+2Y*3/-stack.top++,stack.s[stack.top]=xp>llink->rlink=p->rlink,p->rlink->llink=p->rlink<R-F+M>%Mtop1+1=top2F==Rfront==rearfront==<rear+1>%nN-13.3答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入〔称为入栈,push或者读取栈顶元素或者称为"弹出、出栈"<pop>。3.4答：相同点：栈和队列都是特殊的线性表,只在端点处进行插入,删除操作。不同点：栈只在一端〔栈顶进行插入,删除操作；队列在一端〔top删除,一端<rear>插入。3.5答：可能序列有14种：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。3.6答：不能得到4,3,5,6,1,2,最先出栈的是4,则按321的方式出,不可能得到1在2前的序列,可以得到1,3,5,4,2,6,按如下方式进行push<1>,pop<>,push<2>,push<3>,pop<>,push<4>,push<5>,pop<>,pop<>,pop<>,push<6>,pop<>。3.7答：stack3.8非递归:intvonvert<intno,inta[]>//将十进制数转换为2进制存放在a[],并返回位数{ intr; SeStacks,*p; P=&s; Init_stack<p>; while<no> { push<p,no%2>; no/=10; } r=0; while<!empty_stack<p>> { pop<p,a+r>; r++; } returnr;} 递归算法:voidconvert<intno>{ if<no/2>0> { Convert<no/2>; Printf<"%d",no%2>; } else printf<"%d",no>; }3.9参考程序：voidview<SeStacks>{ SeStack*p;//假设栈元素为字符型 charc; p=&s; while<!empty_stack<p>> { c=pop<p>; printf<"%c",c>; } printf<"\n">;}3.10答：char3.11参考程序：voidout<linkqueueq>{ inte; while<q.rear!=q.front> { dequeue<q,e>; print<e>;//打印 }}习题4参考答案4.1选择题：<1>.A<2>.D<3>.C<4>.C<5>.B<6>.B<7>.D<8>.A<9>.B<10>.D4.2填空题：串长相等且对应位置字符相等不含任何元素的串,0所含字符均是空格,所含空格数10"helloboy"181066由零个或多个任意字符组成的字符序列串中所含不同字符的个数364.3StrLength<s>=14,StrLength<t>=4,SubStr<s,8,7>="STUDENT",SubStr<t,2,1>="O",StrIndex<s,"A">=3,StrIndex<s,t>=0,StrRep<s,"STUDENT",q>="IAMAWORKER",4.4StrRep<s,"Y","+">;StrRep<s,"+*","*Y">;4.5空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6intEQUAl<S,T>{ char*p,*q; p=&S; q=&T; while<*p&&*q> { if<*p!=*q> return*p-*q; p++; q++; } return*p-*q;}4.7<1>6*8*6=288<2>1000+47*6=1282<3>1000+<8+4>*6=1072<4>1000+<6*7+4>*6=12764.8iijv1121215-132144347542665187539矩阵的三元组表习题5参考答案5.1选择〔1C〔2B〔3C〔4B〔5C〔6D〔7C〔8C〔9B〔10C〔11B〔12C〔13C〔14C〔15C5.2填空〔11〔21036；1040〔32i〔41；n;n-1;2〔52k-1；2k-1〔6ACDBGJKIHFE〔7p!=NULL〔8Huffman树〔9其第一个孩子;下一个兄弟〔10先序遍历；中序遍历5.3叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点：ABCDEFGLIJKM度：430120000100树深：45.4无序树形态如下：二叉树形态如下：5.5二叉链表如下:AABC∧D∧E∧F∧G∧∧H∧∧I∧∧J∧三叉链表如下:∧A∧ACBCBF∧∧G∧∧D∧EF∧∧G∧∧D∧EJ∧∧I∧∧H∧J∧∧I∧∧H∧5.6先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7 <1>先序序列和中序序列相同：空树或缺左子树的单支树； <2>后序序列和中序序列相同：空树或缺右子树的单支树； <3>先序序列和后序序列相同：空树或只有根结点的二叉树。5.8这棵二叉树为:5.9先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n,叶子结点数为n0,则n=n0+n1+……+nm〔1再设树中分支数目为B,则B=n1+2n2+3n3+……+mnm〔2因为除根结点外,每个结点均对应一个进入它的分支,所以有n=B+1〔3将〔1和〔2代入〔3,得n0+n1+……+nm=n1+2n2+3n3+……+mnm+1从而可得叶子结点数为：n0=n2+2n3+……+<m-1>nm+15.11由5.10结论得,n0=<k-1>nk+1又由n=n0+nk,得nk=n-n0,代入上式,得n0=<k-1>〔n-n0+1叶子结点数为：n0=n<k-1>/k5.12intNodeCount<BiTreeT>

{//计算结点总数

if<T>

if<T->lchild==NULL>&&<T-->rchild==NULL>

return1;

elsereturnNodeCount<T->lchild>+Node<T-->rchild>+1;

elsereturn0;

}5.13voidExchangeLR<Bitreebt>{/*将bt所指二叉树中所有结点的左、右子树相互交换*/if<bt&&<bt->lchild||bt->rchild>>{bt->lchild<->bt->rchild;Exchange-lr<bt->lchild>;Exchange-lr<bt->rchild>;}}/*ExchangeLR*/5.14intIsFullBitree<BitreeT>

{/*是则返回1,否则返回0。*/

Init_Queue<Q>;/*初始化队列*/

flag=0;

In_Queue<Q,T>;/*根指针入队列,按层次遍历*/

while<!Empty_Queue<Q>>

{

Out_Queue<Q,p>;

if<!p>flag=1;/*若本次出队列的是空指针时,则修改flag值为1。若以后出队列的指针存在非空,则可断定不是完全二叉树*/

elseif<flag>return0;/*断定不是完全二叉树*/

else

{

In_Queue<Q,p->lchild>;

In_Queue<Q,p->rchild>;/*不管孩子是否为空,都入队列。*/

}

}/*while*/

return1;/*只有从某个孩子指针开始,之后所有孩子指针都为空,才可断定为完全二叉树*/

}/*IsFullBitree*/5.15转换的二叉树为：5.16对应的森林分别为：CC5.17typedefcharelemtype;typedefstruct{elemtypedata;intparent;}NodeType;<1>求树中结点双亲的算法:intParent<NodeTypet[],elemtypex>{/*x不存在时返回-2,否则返回x双亲的下标<根的双亲为-1*/for<i=0;i<MAXNODE;i++>if<x==t[i].data>returnt[i].parent;return-2;}/*Parent*/<2>求树中结点孩子的算法:voidChildren<NodeTypet[],elemtypex>{for<i=0;i<MAXNODE;i++>{if<x==t[i].data>break;/*找到x,退出循环*/}/*for*/if<i>=MAXNODE>printf<"x不存在\n">;else{flag=0;for<j=0;j<MAXNODE;j++>if<i==t[j].parent>{printf<"x的孩子:%c\n",t[j].data>;flag=1;}if<flag==0>printf<"x无孩子\n">;}}/*Children*/5.18typedefcharelemtype;typedefstructChildNode{intchildcode;structChildNode*nextchild;}typedefstruct{elemtypedata;structChildNode*firstchild;}NodeType;<1>求树中结点双亲的算法:intParentCL<NodeTypet[],elemtypex>{/*x不存在时返回-2,否则返回x双亲的下标*/for<i=0;i<MAXNODE;i++>if<x==t[i].data>{loc=i;/*记下x的下标*/break;}if<i>=MAXNODE>return-2;/*x不存在*//*搜索x的双亲*/for<i=0;i<MAXNODE;i++>for<p=t[i].firstchild;p!=NULL;p=p->nextchild>if<loc==p->childcode>returni;/*返回x结点的双亲下标*/}/*ParentL*/<2>求树中结点孩子的算法:voidChildrenCL<NodeTypet[],elemtypex>{for<i=0;i<MAXNODE;i++>if<x==t[i].data>/*依次打印x的孩子*/{flag=0;/*x存在*/for<p=t[i].firstchild;p;p=p->nextchild>{printf<"x的孩子:%c\n",t[p->childcode].data>;flag=1;}if<flag==0>printf<"x无孩子\n">;return;}/*if*/printf<"x不存在\n">;return;}/*ChildrenL*/5.19typedefcharelemtype;typedefstructTreeNode{elemtypedata;structTreeNode*firstchild;structTreeNode*nextsibling;}NodeType;voidChildrenCSL<NodeType*t,elemtypex>{/*层次遍历方法*/Init_Queue<Q>;/*初始化队列*/

In_Queue<Q,t>;count=0;while<!Empty_Queue<Q>>{

Out_Queue<Q,p>;

if<p->data==x>{/*输出x的孩子*/p=p->firstchild;if<!p>printf<"无孩子\n">;else{printf<"x的第%i个孩子:%c\n",++count,p->data>;/*输出第一个孩子*/p=p->nextsibling;/*沿右分支*/while<p>{printf<"x的第%i个孩子:%c\n",++count,p->data>;p=p->nextsibling;}}return;}if<p->firstchild>In_Queue<Q,p->firstchild>;

if<p->nextsibling>In_Queue<Q,p->nextsibling>;}}/*ChildrenCSL*/

5.20<1>哈夫曼树为:69692816941192210512743<2>在上述哈夫曼树的每个左分支上标以1,右分支上标以0,并设这7个字母分别为A、B、C、D、E、F和H,如下图所示：则它们的哈夫曼树为分别为:A：1100B：1101C：10D：011E：00F：010H：111习题6参考答案6.1选择题〔1C〔2A〔3B〔4C〔5B______条边。〔6B〔7A〔8A〔9B〔10A〔11A〔12A〔13B〔14A〔15B〔16A〔17C6.2填空〔14〔21对多;多对多〔3n-1;n〔40_〔5有向图〔61〔7一半〔8一半〔9___第i个链表中边表结点数___〔10___第i个链表中边表结点数___〔11深度优先遍历；广度优先遍历〔12O〔n2〔13___无回路6.3〔1邻接矩阵:〔2邻接链表：〔3每个顶点的度：顶点度V13V23V32V43V536.4〔1邻接链表：〔2逆邻接链表：〔3顶点入度出度V130V222V312V413V521V6236.5〔1深度优先查找遍历序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2〔1广度优先查找遍历序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V56.6有两个连通分量：6.7顶点〔1〔2〔3〔4〔5LowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexLowCloseCostVexV10101010101V211010110101V31111010101V43122220202V5∞152332404U{v1}{v1,v2}{v1,v2,v3}{v1,v2,v3,v4}{v1,v2,v3,v4,v5}T{}{<v1,v2>}{<v1,v2>,<v1,v3>}{<v1,v2>,<v1,v3>,<v2,v4>}{<v1,v2>,<v1,v3>,<v2,v4>,<v4,v5>}最小生成树的示意图如下：6.8拓扑排序结果：V3V1V4V5V2V66.9〔1建立无向图邻接矩阵算法：提示：参见算法6.1因为无向图的邻接矩阵是对称的,所以有for<k=0;k<G->e;k++>/*输入e条边,建立无向图邻接矩阵*/{scanf<"\n%d,%d",&i,&j>;G->edges[i][j]=G->edges[j][i]=1;}<2>建立无向网邻接矩阵算法:提示：参见算法6.1。初始化邻接矩阵：#defineINFINITY32768/*表示极大值*/for<i=0;i<G->n;i++>for<j=0;j<G->n;j++>G->edges[i][j]=INFINITY;输入边的信息：不仅要输入边邻接的两个顶点序号,还要输入边上的权值for<k=0;k<G->e;k++>/*输入e条边,建立无向网邻接矩阵*/{scanf<"\n%d,%d,%d",&i,&j,&cost>;/*设权值为int型*/G->edges[i][j]=G->edges[j][i]=cost;/*对称矩阵*/}<3>建立有向图邻接矩阵算法:提示：参见算法6.1。6.10<1>建立无向图邻接链表算法：typedefVertexTypechar;intCreate_NgAdjList<ALGraph*G>

{/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/

scanf<"%d",&n>;if<n<0>return-1;/*顶点数不能为负*/

G->n=n;

scanf<"%d",&e>;if<e<0>return=1;/*边数不能为负*/

G->e=e;for<m=0;m<G->n;m++>

G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/

for<m=0;m<G->n;m++>

G->adjlist[m].vertex=getchar<>;/*输入各顶点的符号*/

for<m=1;m<=G->e;m++>

{

scanf<"\n%d,%d",&i,&j>;/*输入一对邻接顶点序号*/if<<i<0||j<0>return-1;

p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第i+1个链表中插入一个边表结点*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第j+1个链表中插入一个边表结点*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*for*/return0;/*成功*/}//Create_NgAdjList<2>建立有向图逆邻接链表算法：typedefVertexTypechar;intCreate_AdjList<ALGraph*G>

{/*输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表*/

scanf<"%d",&n>;if<n<0>return-1;/*顶点数不能为负*/

G->n=n;

scanf<"%d",&e>;if<e<0>return=1;/*弧数不能为负*/

G->e=e;

for<m=0;m<G->n;m++>

G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/for<m=0;m<G->n;m++>

G->adjlist[m].vertex=getchar<>;/*输入各顶点的符号*/

for<m=1;m<=G->e;m++>

{

scanf<"\n%d,%d",&t,&h>;/*输入弧尾和弧头序号*/if<<t<0||h<0>return-1;

p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第h+1个链表中插入一个边表结点*/p->adjvex=t;p->next=G->adjlist[h].firstedge;G->adjlist[h].firstedge=p;}/*for*/return0;/*成功*/}//Create_AdjList6.11voidCreate_AdjM<ALGraph*G1,MGraph*G2>

{/*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/G2->n=G1->n;G2->e=G1->e;for<i=0;i<G2->n;i++>/*置G2每个元素为0*/for<j=0;j<G2->n;j++>G2->edges[i][j]=0;for<m=0;m<G1->n;m++>G2->vexs[m]=G1->adjlist[m].vertex;/*复制顶点信息*/num=〔G1->n/2==0?G1->n/2:G1->n/2+1;/*只要搜索前n/2个单链表即可*/for<m=0;m<num;m++>{p=G1->adjlist[m].firstedge;while<p>{/*无向图的存储具有对称性*/G2->edges[m][p->adjvex]=G2->edges[p->adjvex][m]=1;p==p->next;}}/*for*/}/*Create_AdjM*/6.12voidCreate_AdjL<ALGraph*G1,MGraph*G2>

{/*通过无向图的邻接矩阵G1,生成无向图的邻接链表G2*/G2->n=G1->n;G2->e=G1->e;for<i=0;i<G1->n;i++>/*建立每个单链表*/{G2->vexs[i]=G1->adjlist[i].vertex;G2->adjlist[i].firstedge=NULL；for<j=i;j<G1->n;j++>/*对称矩阵,只要搜索主对角以上的元素即可*/{if<G1->edges[i][j]==1>{p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第i+1个链表中插入一个边表结点*/p->adjvex=j;p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p=<EdgeNode*>malloc<sizeof<EdgeNode>>;/*在第j+1个链表中插入一个边表结点*/p->adjvex=i;p->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=p;}/*if*/}/*for*/}/*for*/}/*Create_AdjL*/6.13<1>邻接矩阵中1的个数的一半;<2>若位于[i-1,j-1]或[j-1,i-1]位置的元素值等于1,则有边相连,否则没有。<3>顶点i的度等于第i-1行中或第i-1列中1的个数。6.14<1>邻接链表中边表结点的个数的一半;<2>若第i-1〔或j-1个单链表中存在adjvex域值等于j-1〔或i-1的边表结点,则有边相连,否则没有。<3>顶点i的度等于第i-1个单链表中边表结点的个数。6.15提示：参见算法6.2和6.3。习题7参考答案7.1选择题〔1C<2>C<3>C<4>B<5>A<6>A<7>D<8>B<9>D<10>B<11>B<12>A<13>C<14>C<15>A<16>D<17>C<18>B,C<19>B<20>A7.2填空题O<n>,O<log2n>1,2,4,8,5,log2<n+1>-1小于,大于增序序列,m-170;34,20,55n/m开放地址法,链地址法产生冲突的可能性就越大,产生冲突的可能性就越小关键码直接②,①,⑦16,16,8,21直接定址法,数字分析法,平方取中法,折叠法,除留余数法,随机数法开放地址法,再哈希法,链地址法,建立一个公共溢出区装满程度索引,快哈希函数,装填因子一个结点中序等于7.3一棵二叉排序树<又称二叉查找树>或者是一棵空树,或者是一棵同时满足下列条件的二叉树：<1>若它的左子树不空,则左子树上所有结点的键值均小于它根结点键值。<2>若它的右子树不空,则右子树上所有结点的键值均大于它根结点键值。<3>它的左、右子树也分别为二叉排序树。7.4对地址单元d=H<K>,如发生冲突,以d为中心在左右两边交替进行探测。按照二次探测法,键值K的散列地址序列为：do=H<K>,d1=<d0+12>modm,d2=<d0-12>modm,d3=<d0+22>modm,d4=<d0-12>modm,……7.5衡量算法的标准有很多,时间复杂度只是其中之一。尽管有些算法时间性能很好,但是其他方面可能就存在着不足。比如散列查找的时间性能很优越,但是需要关注如何合理地构造散列函数问题,而且总存在着冲突等现象,为了解决冲突,还得采用其他方法。二分查找也是有代价的,因为事先必须对整个查找区间进行排序,而排序也是费时的,所以常应用于频繁查找的场合。对于顺序查找,尽管效率不高,但却比较简单,常用于查找范围较小或偶而进行查找的情况。7.6此法要求设立多个散列函数Hi,i=1,…,k。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时,继续计算该给定值K在下一个散列函数Hi+1下的散列地址,直到不再产生冲突为止。7.7散列表由两个一维数组组成。一个称为基本表,另一个称为溢出表。插入首先在基本表上进行；假如发生冲突,则将同义词存人溢出表。7.8结点个数为n时,高度最小的树的高度为1,有两层,它有n-1个叶结点,1个分支结点；高度最大的树的高度为n-l,有n层,它有1个叶结点,n-1个分支结点。7.9设顺序查找以h为表头指针的有序链表,若查找成功则返回结点指针p,查找失败则返回null值。pointersqesrearch<pointerh,intx,pointerp>{p=null；while<h>if<x>h->key>h=h->link；else{if<x==h->key>p=h；return<p>；}}虽然链表中的结点是按从小到大的顺序排列的,但是其存储结构为单链表,查找结点时只能从头指针开始逐步进行搜索,故不能用折半<二分>查找。7.10分析：对二叉排序树来讲,其中根遍历序列为一个递增有序序列。因此,对给定的二叉树进行中根遍历,如果始终能保证前一个值比后一个值小,则说明该二叉树是二叉排序树。intbsbtr<bitreptrT>／*predt记录当前结点前趋值,初值为-∞*／{if<T==NULL>return<1>；else{b1=bsbtr<T->lchild>；／*判断左子树*／if<!b1||<predt>=T->data>>return<0>；*当前结点和前趋比较*／predt=T->data；／*修改当前结点的前趋值*／return<bsbtr<T->rchild>>；／*判断右子树并返回最终结果*／}}7.11<1>使用线性探查再散列法来构造散列表如表下所示。散列表───────────────────────────────地址012345678910───────────────────────────────数据331131234382722───────────────────────────────〔2使用链地址法来构造散列表,如下图<3>装填因子a=8／11。使用线性探查再散列法查找成功所需的平均查找次数为Snl=0．5<1+1／<1-a>>=0．5*<1+1／<1-8／11>>=7／3使用线性探查再散列法查找不成功所需的平均查找次数为：Unl=0．5<1+1／<1-a>2>=0．5*<1+1／<1-8／11>2>=65／9使用链地址法查找成功所需的平均查找次数为：Snc=l+a／2=1+8／22=15／11使用链地址法查找不成功所需的平均查找次数为：‘Unl=a+e-a=8／1l+e-8／117.12分析：在等查区间的上、下界处设两个指针,由此计算出中间元素的序号,当中间元素大于给定值X时,接下来到其低端区间去查找；当中间元素小于给定值X时,接下来到其高端区间去查找；当中间元素等于给定值X时,表示查找成功,输出其序号。Intbinlist<sqtableA,ints,t,keytypeX>／*t、s分别为查找区间的上、下界*／{if<s<t>return<0>；／*查找失败*／else{mid=<S+t>／2；switCh<mid>{casex<A.item[midJ.key：return<binlist<A,s,mid-l,X>>；／*在低端区间上递归*／casex==A.item[mid].key：return<mid>；／+查找成功*／casex>A.item[mid].key：return<a,mid+l,t,X>>；／*在高端区间上递归*／}}}7.13intsqsearch0<sqtableA,keytypeX>/*数组有元素n个*／{i=l；A.item[n+1].key=X；／t设置哨兵*／while<A.item[n+1].key!=X>i++；return<i%<n／1>>；／*找不到返回0,找到返回其下标*／}查找成功平均查找长度为：<1+2+3+…+n>／n：<1+n>／2。查找不成功平均查找长度为：n+1。7.14散列函数：H<key>=100+<key个位数+key十位数>modl0；形成的散列表：100101102103104105106107108109987563464979615317查找成功时的平均长度为：<1+2+1+1+5+1+1+5+5+3>/10=2.5次。由于长度为10的哈希表已满,因此在插人第11个记录时所需作的比较次数的期望值为10,查找不成功时的平均长度为10。习题8参考答案8．1选择题〔1B<2>A<3>D<4>C<5>B<6>A<7>B<8>C<9>A<10>C<11>D<12>C<13>C〔14D〔15C<16>B<17>D〔18C〔19B〔20D8.2填空题快速,归并O〔log2n,O<nlog2n>归并向上,根结点19,18,16,20,30,22〔6192318162030192318162030〔749,13,27,50,76,38,65,97〔88,8〔9插入,选择〔每次选择最大的〔10快速,归并<11>O<1>,O<nlog2n><12>稳定<13>3<14><15,20,50,40><15>O<log2n><16>O<n2><17>冒泡排序,快速排序<18>完全二叉树,n/2<19>稳定,不稳定<20>2,4,<20,40,15>8.3.假定给定含有n个记录的文件<r1,f2,…,rn>,其相应的关键字为<k1,k2,…,kn>,则排序就是确定文件的一个序列rr,r2,,…,rn,,使得k1'≤k2'≤…≤kn',从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行,则排序叫内部排序。假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字,若采用某种排序方法后,使得这些具有相同关键字的记录在排序前后相对次序依然保持不变,则认为该排序方法是稳定的,否则就认为排序方法是不稳定的。8.4．稳定的有：直接插入排序、二分法插入排序、起泡排序、归并排序和直接选择排序。8.5．初始记录序列按关键字有序或基本有序时,比较次数为最多。8.6．设5个元素分别用a,b,c,d,e表示,取a与b、c与d进行比较。若a>b,c>d<也可能是a<b,c<d,此时情况类似>,显然此时进行了两次比较,取b与d再比较,若b>d则a>b>d,若b<d,则有c>d>b,此时已进行了3次比较,要使排序比较最多7次,可把另外两个元素按折半检索排序插入到上面所得的有序序列中,此时共需要4次比较。从而可得算法,共只需7次比较。8.7．题目中所说的几种排序方法中,其排序速度都很快,但快速排序、归并排序、基数排序和Shell排序都是在排序结束后才能确定数据元素的全部序列,而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素<即最大或最少值的元素>,然后对堆进行再调整,保证堆顶元素总是当前剩下元素的最大或最小的,从而可知,欲在一个大量数据的文件中,如含有15000个元素的记录文件中选取前10个最大的元素,可采用堆排序进行。8.8．二分法排序。8.9．voidinsertsort<seqlistr> ；{／／对顺序表中记录R[0一N—1>按递增序进行插入排序&NBSP；inti,j； ；for<i=n-2；i>=0;i-->／／在有序区中依次插入r[n-2]．．r[0] ；if<r[i].key>r[i+1].key>／／若不是这样则r[i]原位不动 ；{ ；r[n]=r[i]；j=i+l；／／r[n]是哨兵 ；do{／／从左向右在有序区中查找插入位置 ；r[j-1]=r[j]；／／将关键字小于r[i]．key的记录向右移 ；j++； ；}whle<r[j].keyr[j-1]=r[n]；／／将引i>插入到正确位置上 ；}／／endif ；}／／insertsort． ；8.10．建立初始堆：[9376948632654387517421290753011]&NBSP；&NBSP；第一次排序重建堆：[863694751765438301742129075]9378.11．在排序过程中,每次比较会有两种情况出现,若整个排序过程至少需作t次比较,则显然会有2^t个情况,由于n个结点总共有n!种不同的排列,因而必须有n!种不同的比较路径,于是：2t≥n!即t≥log2n!因为log2nl=nlog2n-n／ln2+log2n／2+O<1>故有log2n!≈nlog2n从而t≧nlog2n得证。8.12．依据堆定义可知：序列<1>、<2>、<4>是堆,<3>不是堆,从而可对其调整使之为如下的大根堆<100,95,80,60,40,95,82,10,20>。8.13．第一趟：[265301][129751][863937][694742][076438]&NBSP；&NBSP；第二趟：[129265301751][694742863937][076438]&NBSP；&NBSP；第三趟：[129265301694742751863937][076438]&NBSP；&NBSP；第四趟：[076129265301438694742751863937]&NBSP；8.14．<1>归并排序：<18,29><25,47><12,58><10,51><18,25,29,47><10,12,51,58><10,12,18,25,29,47,51,58><2>快速排序：<10,18,25,12,29,58,51,47><10,18,25,12,29,47,51,58><10,12,18,25,29,47,51,58><3>堆排序：初始堆<大顶堆>：<58,47,51,29,18,12,25,10>第一次调整：<51,47,25,29,18,12,10><58>第二次调整：<47,29,25,10,18,12><51,58>第三次调整：<29,18,25,10,12><47,51,58>第四次调整：<25,18,12,10><29,47,51,58>第五次调整：<18,10,12><25,29,47,51,58>第六次调整：<12,10><18,25,29,47,51,58>第七次调整：<10,12,18,25,29,47,51,58>8.15．<1>直接插入排序。序号1234567891011