《数据结构与算法》课后习题答案.doc 37页

'2.3课后习题解答2.3.2判断题1．线性表的逻辑顺序与存储顺序总是一致的。（×）2．顺序存储的线性表可以按序号随机存取。（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）12．线性表的特点是每个元素都有一个前驱和一个后继。（×）2.3.3算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x，最后修改表示表长的变量。intinsert(datatypeA[],int*elenum,datatypex)/*设elenum为表的最大下标*/{if(*elenum==arrsize-1)return0;/*表已满，无法插入*/else{i=*elenum;while(i>=0&&A[i]>x)/*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x;/*找到的位置是插入位的下一位*/(*elenum)++;return1;/*插入成功*/}}时间复杂度为O(n)。 2．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。【提示】对顺序表A，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。voiddelete(Seqlist*A){i=0;while(ilast)/*将第i个元素以后与其值相同的元素删除*/{k=i+1;while(k<=A->last&&A->data[i]==A->data[k])k++;/*使k指向第一个与A[i]不同的元素*/n=k-i-1;/*n表示要删除元素的个数*/for(j=k;j<=A->last;j++)A->data[j-n]=A->data[j];/*删除多余元素*/A->last=A->last-n;i++;}}3．写一个算法，从一个给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。【提示】对顺序表A，从前向后依次判断当前元素A->data[i]是否介于x和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将A->data[i]向前移动n位。n用来记录当前已删除元素的个数。voiddelete(Seqlist*A,intx,inty){i=0;n=0;while(ilast){if(A->data[i]>=x&&A->data[i]<=y)n++;/*若A->data[i]介于x和y之间，n自增*/elseA->data[i-n]=A->data[i];/*否则向前移动A->data[i]*/i++;}A->last-=n;}4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。intfch(charc)/*判断c是否字母*/{if(c>="a"&&c<="z"||c>="A"&&c<="Z")return(1);elsereturn(0);}intfnum(charc)/*判断c是否数字*/{if(c>="0"&&c<="9")return(1); elsereturn(0);}voidprocess(charR[n]){low=0;high=n-1;while(lowdata[0];for(k=1;k<=L->last;k++)L->data[k-1]=L->data[k];L->data[L->last]=x;}elsefor(i=1;i<=n;i++){x=L->data[L->last];for(k=L->last-1;k>=0;k--)L->data[k+1]=L->data[k]; L->data[0]=x;}}6．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。LinkListinsert(LinkListL,intx){p=L;while(p->next&&x>p->next->data)p=p->next;/*寻找插入位置*/s=(LNode*)malloc(sizeof(LNode));/*申请结点空间*/s->data=x;/*填装结点*/s->next=p->next;p->next=s;/*将结点插入到链表中*/return(L);}7．假设有两个已排序（递增）的单链表A和B，编写算法将它们合并成一个链表C而不改变其排序性。LinkListCombine(LinkListA,LinkListB){C=A;rc=C;pa=A->next;/*pa指向表A的第一个结点*/pb=B->next;/*pb指向表B的第一个结点*/free(B);/*释放B的头结点*/while(pa&&pb)/*将pa、pb所指向结点中，值较小的一个插入到链表C的表尾*/if(pa->datadata){rc->next=pa;rc=pa;pa=pa->next;}else{rc->next=pb;rc=pb;pb=pb->next;}if(pa)rc->next=pa;elserc->next=pb;/*将链表A或B中剩余的部分链接到链表C的表尾*/return(C);}8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。vioddelepre(LNode*s){LNode*p,*q; p=s;while(p->next!=s){q=p;p=p->next;}q->next=s;free(p);}9．已知两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C，要求C同样以元素递增的单链表形式存储。【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。LinkListIntersect(LinkListA,LinkListB){LNode*q,*p,*r,*s;LinkListC;C=(LNode*)malloc(sizeof(LNode));C->next=NULL;r=C;p=A;q=B;while(p&&q)if(p->datadata)p=p->next;elseif(p->data==q->data){s=(LNode*)malloc(sizeof(LNode));s->data=p->data;r->next=s;r=s;p=p->next;q=q->next;}elseq=q->next;r->next=NULL;C=C->next;returnC;}10．设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata(L,x)算法。【提示】在定位操作的同时，需要调整链表中结点的次序：每次进行定位操作后，要查看所查找结点的freq域，将其同前面结点的freq域进行比较，同时进行结点次序的调整。typedefstructdnode {datatypedata;intfreq;structDLnode*prior,*next;}DLnode,*DLinkList;DlinkListLocate(DLinkListL,datatypex){p=L->next;while(p&&p->data!=x)p=p->next;/*查找值为x的结点，使p指向它*/if(!p)return(NULL);/*若查找失败，返回空指针*/p->freq++;/*修改p的freq域*/while(p->prior!=L&&p->prior->freqfreq)/*调整结点的次序*/{k=p->prior->data;p->prior->data=p->data;p->data=k;k=p->prior->freq;p->prior->freq=p->freq;p->freq=k;p=p->prior;}return(p);/*返回找到的结点的地址*/}3.3课后习题解答##3.3.1选择题1．向一个栈顶指针为Top的链栈中插入一个p所指结点时，其操作步骤为（C）。A．Top->next=p;B．p->next=Top->next;Top->next=p;C．p->next=Top;Top=p;D．p->next=Top;Top=Top->next;2．对于栈操作数据的原则是（B）。A．先进先出B．后进先出C．后进后出D．不分顺序3．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是（D）。A．iB．n-iC．n-i+1D．不确定4．表达式a*(b－c)＋d的后缀表达式是（B）。A．abcd*-+B．abc-*d+C．abc*-d+D．+-*abcd5．采用顺序存储的两个栈共享空间S[1..m]，top[i]代表第i个栈(i=1,2)的栈顶，栈1的底在S[1]，栈2的底在S[m]，则栈满的条件是（B）。A．top[2]-top[1]|=0B．top[1]+1=top[2]C．top[1]+top[2]=mD．top[1]=top[2]6．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（C）。A．edcbaB．decbaC．dceabD．abcde7．在一个链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（B）。A．f->next=r;f=s;B．r->next=s;r=s;C．s->next=r;r=s;D．s->next=f;f=s;8．用不带头结点的单链表存储队列时，在进行删除运算时（D）。 A．仅修改头指针B．仅修改尾指针C．头、尾指针都要修改D．头、尾指针可能都要修改9．递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A．队列B．静态链表C．栈D．顺序表10．栈和队都是（C）。A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构3.3.2判断题1．栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（√）2．任何一个递归过程都可以转换成非递归过程。（√）3．若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。（√）4．通常使用队列来处理函数的调用。（×）5．循环队列通常用指针来实现队列的头尾相接。（×）3.3.3简答题1．循环队列的优点是什么？如何判别它的空和满？循环队列的优点是能够克服“假溢满”现象。设有循环队列sq，队满的判别条件为：（sq->rear+1）%maxsize==sq->front;或sq->num==maxsize。队空的判别条件为：sq->rear==sq->front。2．栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？栈和队列都是操作受限的线性表，栈的运算规则是“后进先出”，队列的运算规则是“先进先出”。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。3．什么是递归？递归程序有什么优缺点？一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。4．设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3课后习题解答###4.3.1选择题1．下面关于串的叙述错误的是（C）。A．串是字符的有限序列B．串既可以采用顺序存储，也可以采用链式存储C．空串是由空格构成的串D．模式匹配是串的一种重要运算2．串的长度是指（B）。A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数3．已知串S=‘aaab’,其Next数组值为（D）。A．0123B．1123C．1231D．12114．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；M的第8列和第5行共占（A）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（C）元素的起始地址一致。（1）A．90B．180C．240D．540（2）A．108B．114C．54D．60（3）A．M[8][5]B．M[3][10]C．M[5][8]D．M[0][9]5．数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C），若该数组按行存放，元素A[8][5]的起始地址是（C），若该数组按列存放，元素A[8][5]的起始地址是（C）。（1）A．80B．100C．240D．270（2）A．SA+141B．SA+144C．SA+222D．SA+225（3）A．SA+141B．SA+180C．SA+117D．SA+2256．稀疏矩阵采用压缩存储，一般有（C）两种方法。A．二维数组和三维数组B．三元组和散列C．三元组表和十字链表D．散列和十字链表4.3.2判断题1．串相等是指两个串的长度相等。（×）2．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√）3．稀疏矩阵压缩存储后，必会失去随机存取功能。（√）4．数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×）5．若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（×）6．若一个广义表的表头为空表，则此广义表亦为空表。（×）7．所谓取广义表的表尾就是返回广义表中最后一个元素。（×）4.3.3简答题1．KMP算法较朴素的模式匹配算法有哪些改进?KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。2．设字符串S=‘aabaabaabaac"，P=‘aabaac"。（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。【解答】（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)3．假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占４个字节。问下列元素的存储地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247【解答】(1)LOC(a0000)=100(2)LOC(a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3)LOC(a3125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784(4)LOC(a8247)=100+(3*5*8*8+5*8*2+8*4+7)*4=48164．假设一个准对角矩阵：a11a12a21a22a33a34a43a44….aija2m-1,2m-1a2m-1,2ma2m,2m-1a2m,2m按以下方式存储于一维数组B[4m]中（m为一个整数）：0123456…k…4m-14ma11a12a21a22a33a34a43…aij…a2m-1,2ma2m,2m-1a2m,2m写出下标转换函数k=f(i,j)。【解答】由题目可知，每一行有两个非0元素。当i为奇数时，第i行的元素为：ai,i、ai,(i+1)，此时k=2*(i-1)+j-i=i+j-2当i为偶数时，第i行的元素为：ai,(i-1)、ai,i，此时k=2*(i-1)+j-I+1=i+j-1综上所述，k=i+j-i%2-1。5．设有n×n的带宽为3的带状矩阵A，将其3条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推导出从（i,j）到(u,v)的下标变换公式。【解答】u=j-i+1v=j-1 6．现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。（1）三元组表表示法（2）十字链表法。000220-150133000000-60000000091000000028000【解答】（1）三元组表表示法:ijv1234567142216-15221323334-651916328（2）十字链表法：012345^0123^455191^^233^34-6^^14226328^^16-15^^2213^ 7．画出下列广义表的头尾表示存储结构示意图。（1）A=((a,b,c),d,(a,b,c))（2）B=(a,(b,(c,d),e),f)（1）11111^1^1d0a1b1c（2）1111^1^10f0a0b0c1^10c0d5.3课后习题解答5.3.1选择题1．下列说法正确的是（C）。A．二叉树中任何一个结点的度都为2B．二叉树的度为2C．一棵二叉树的度可小于2D．任何一棵二叉树中至少有一个结点的度为22．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（C）。A．2n-1B．n-1C．n+1D．2n+13．线索化二叉树中，某结点*p没有孩子的充要条件是（B）。A．p->lchild=NULLB．p->ltag=1且p->rtag=1C．p->ltag=0D．p->lchild=NULL且p->ltag=14．如果结点A有3个兄弟,而且B是A的双亲,则B的度是（B）。A．3B．4C．5D．15．某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n。且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减１,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加１，这是按（B）编号的。A．中序遍历序列B．先序遍历序列C．后序遍历序列D．层次顺序6．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针域为空的结点有（C）个。A．n-1B．nC．n+1D．n+2 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（B）。A．500B．501C．490D．4958．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。A．N1B．N1+N2C．N2D．N2+N39．任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A）。A．不发生改变B．发生改变C．不能确定D．以上都不对10．若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D）。A．cbedB．decabC．deabcD．cedba11．若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（D）。A．gcefhaB．gdbecfhaC．bdgaechfD．gdbehfca12．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（AB）。A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是一棵满二叉树13．引入线索二叉树的目的是（A）。A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一14．设高度为h的二叉树上只有度为０和度为２的结点，则此类二叉树中所包含的结点数至少为（B）。A．2*hB．2*h-1C．2*h+1D．h+115．一个具有567个结点的二叉树的高h为（D）。A．9B．10C．9至566之间D．10至567之间16．给一个整数集合{3，5，6，7，9}，与该整数集合对应的哈夫曼树是（B）。A．B．C．D．937653567979536765395.3.2判断题1．二叉树是树的特殊形式。（√）2．由树转换成二叉树，其根结点的右子树总是空的。（√）3．先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（×）4．先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（×）5．完全二叉树中，若一个结点没有左孩子，则它必是叶子。（√）6．对于有N个结点的二叉树，其高度为ëlog2Nû＋1。（×）7 ．若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（√）8．若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（√）9．不使用递归也可实现二叉树的先序、中序和后序遍历。（√）10．先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（×）11．先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（×）12．在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。（×）13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（√）14．在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（×）15．用一维数组存放二叉树时，总是以先序遍历存储结点。（×）16．由先序序列和后序序列能唯一确定一棵二叉树。（×）17．由先序序列和中序序列能唯一确定一棵二叉树。（√）18．对一棵二叉树进行层次遍历时，应借助于一个栈。（×）19．完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（×）20．满二叉树一定是完全二叉树，反之未必。（√）5.3.3简答题1．一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】①二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。ADBGEHCF(图1)②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。2．对于图1所示二叉树，试给出：（1）它的顺序存储结构示意图；（2）它的二叉链表存储结构示意图；（3）它的三叉链表存储结构示意图。【解答】（1）顺序存储结构示意图：ABCDEF^^^G^^H（2）二叉链表存储结构示意图：（3）三叉链表存储结构示意图：ABC^^D^E^^F^G^^H^A^BC^^D^E^^F^G^^H^IDEFGCBANMKJH(图2)3．对于图2所示的树，试给出：（1）双亲数组表示法示意图；（2）孩子链表表示法示意图；（3）孩子兄弟链表表示法示意图。【解答】 （1）双亲数组表示法示意图：（2）孩子链表表示法示意图：0A-11B02C03D24E25F16G17H58I29J410K411M312N82^6410^15311^97^12^0A1B2C3D4E5F6G7H8I9J10K11M12N8^（3）孩子兄弟链表表示法示意图：A^B^N^^H^C^^GF^EDI^^J^K^^M^4．画出图3所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的结点在二叉树中是叶子。DBCIGHAFEJ(图3)【解答】HFGIJABCED 在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。5．将题5图所示的二叉树转换成相应的森林。HGDEFBAC(题5图)【解答】森林：ABHEGDCF6．证明：在结点数多于1的哈夫曼树中不存在度为1的结点。证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是由两棵子树合并产生的新结点，其度必为2，所以哈夫曼树中不存在度为1的结点。7．证明：若哈夫曼树中有n个叶结点，则树中共有2n－1个结点。证明：n个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所以树中共有2n-1个结点。8．证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。9．已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？解：设树中共有n个结点，n0个叶结点，那么n=n0+n1+…+nm(1)树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以：n=n1+2*n2+…+m*nm+1(2)由(1)、(2)可知n0=n2+2*n3+3*n4+…+(m-1)*nm+110．在具有n（n>1）个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？2;n-1;1;n;1,n-111．设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。最大值：2h-1；最小值：2h-1 12．求表达式：a＋b*(c－d)－e/f的波兰式（前缀式）和逆波兰式（后缀式）。波兰式：-+a*b–cd/ef逆波兰式：abcd-*+ef/-13．画出和下列已知序列对应的树T：树的先根次序访问序列为：GFKDAIEBCHJ；树的后根访问次序为：DIAEKFCJHBG。【解答】对应的二叉树和树分别如下左、右图所示：GBIEADKFCHJGBIEADKFCHJ14．画出和下列已知序列对应的森林F：森林的先根次序访问序列为：ABCDEFGHIJKL；森林的后根访问次序为：CBEFDGAJIKLH。ABDGCEFHIKJL15．画出和下列已知序列对应的树T：二叉树的层次访问序列为：ABCDEFGHIJ；二叉树的中序访问次序为：DBGEHJACIF。【解答】ABCDEFGHIJ按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。16．假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},（1）为这7个字母设计哈夫曼编码。 （2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文1.000.590.410.280.210.120.310.160.800.400.200.100.11111111总长压缩多少？（1）哈夫曼树：a：10b：110c：010d：1110e：011f：00g：1111（2）对这7个字母进行等长编码，至少需要3位二进制数。等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54哈夫曼编码比等长编码使电文总长压缩了：1-2.54/3=15.33%5.3.4算法设计题1．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。【提示】采用递归算法实现。二叉树结点的数目＝0当二叉树为空左子树结点数目＋右子树结点数目＋1当二叉树非空intcount(BiTreeroot){if(root==NULL)return(0);elsereturn(count(root->lchild)+count(root->rchild)+1);}2．请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点的rchild域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkListhead,pre=NULL;/*全局变量*/LinkListInOrder(BiTreeT)/*中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头指针为head*/{if(T){InOrder(T->lchild);/*中序遍历左子树*/if(T->lchild==NULL&&T->rchild==NULL)/*当前是叶子结点*/if(pre==NULL){head=T;pre=T;}/*处理第一个叶子结点*/else{pre->rchild=T; pre=T;}/*将叶子结点链入链表*/InOrder(T->rchild);/*中序遍历右子树*/pre->rchild=NULL;/*设置链表尾结点*/return(head);}3．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树的深度的算法。【提示】采取递归算法。intHeight(BiTreeroot){inthl,hr;if(root==NULL)return(0);else{hl=Height(root->lchild);hr=Height(root->rchild);if(hl>hr)return(hl+1);elsereturn(hr+1);}}4．给定一棵用二叉链表表示的二叉树，其根指针为root，试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。二叉树结点的层次数＝1当结点为根结点其双亲结点的层次数＋1当结点非根结点voidfun(BiTreeroot,intn){if(t==NULL)return;else{printf(“%d”,n);fun(root->lchild,n+1);fun(root->rchild,n+1);}}5．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。【提示】设root为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。voidExchange(BiTreeroot){BiTNode*p;if(root){Exchange(root->lchild);Exchange(root->rchild);p=root->lchild;root->lchild=root->rchild;root->rchild=p;}} 6．一棵具有n个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先序遍历。【提示】二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储结构的二叉树进行先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储结构下，判二叉树结点为空的条件为：结点下标大于n，或结点值为0（一般二叉树中的“虚结点”）。voidPreOrder(datatypedata[n+1])/*0号单元未用*/{intstack[n];inttop;if(n<1)return;t=1;top=0;while(t<=n||top>0){while(t<=n&&data[t]!=0){Visite(data[t]);stack[top]=t;top++;t=t*2;}if(top<=0)return;else{top--;t=stack[top];t=t*2+1;}}}7．二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先结点算法。【提示】对二叉树进行先序非递归遍历，查找值为x的结点。进入子树时，将子树的根压栈；从子树返回时，将栈顶元素出栈。当找到值为x的结点时，栈中存放的就是其祖先结点，依次打印各结点的值。voidPrintNode(BiTreeT,datatypex){Init_Stack(S);/*初始化空栈*/p=T;while(p||!Empty_Stack(S))/*若p非空，或栈非空*/{while(p){if(p->data==x)/*若当前结点值为x，依次输出栈中元素的值*/{while(!Empty_Stack(S)){Pop(S,q);printf(q->data);}return;}else{Push_Stack(S,p);}/*若当前结点值不是x，压栈*/p=p->lchild;}if(!Empty_Stack(S)){Pop_Stack(S,r);/*当栈非空，栈顶元素出栈，进入右子树*/p=r->rchild;} elsereturn;}}8．已知一棵二叉树的后序遍历序列和中序遍历序列，写出可以确定这棵二叉树的算法。【提示】根据后序遍历和中序遍历的特点，采用递归算法实现。voidInPost(charin[],charpost[],intil,intir,intpl,intpr,BiTreet)/*数组in和数组post中存放着二叉树的中序遍历序列和后序遍历序列，il和ir表示中序遍历序列的左右端*//*点，pl和pr表示后序遍历序列的左右端点，t表示二叉树的根*/{t=(BiTNode*)malloc(sizeof(BiTNode));t->data=post[pr];m=il;while(in[m]!=post[pr])m++;if(m==il)t->lchild=NULL;elseInPost(in,post,il,m-1,pl,pl+m-1-il,t->lchild);if(m==ir)t->rchild=NULL;elseInPost(in,post,m+1,ir,pr-ir+m,pr-1,t->rchild);}9．编写算法判断一棵二叉链表表示的二叉树是否是完全二叉树。【提示】根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应满足：①若某结点没有左孩子，则一定无右孩子；②若某结点缺（左或右）孩子，则其所有后继一定无孩子。因此，可采用按层次遍历二叉树的方法依次对每个结点进行判断。这里增加一个标志以表示所有已扫描过的结点均有左、右孩子，将局部判断结果存入CM中，CM表示整个二叉树是否是完全二叉树，B为1表示到目前为止所有结点均有左右孩子。intCompleteBT(BiTreeT){Init_Queue(Q);/*初始化队列Q*/B=1;CM=1;if(T!=NULL){In_Queue(Q,T);while(!Empty_Queue(Q))/*当队列不为空时执行循环*/{p=Out_Queue(Q);if(p->lchild==NULL){B=0;/*B=0表示缺少左、右孩子*/if(rchild!=NULL)CM=0;/*CM=0表示不是完全二叉树*/}else{CM=B;In_Queue(Q,p->lchild);/*左孩子入队列*/if(p->rchild==NULL)B=0;elseIn_Queue(Q,p->rchild);/*右孩子入队列*/}}return(CM);} }10．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树。BiTreeCreate(dataypeA[],inti)/*n个结点的完全二叉树存于一维数组A中，据此建立以二叉链表表示的完全二叉树,初始调用时,i=1*/{BiTreeT;if(i<=n){T=(BiTree)malloc(sizeof(BiTNode));T->data=A[i];if(2*i>n)T->lchild=NULL;elseT->lchild=Create(A,2*i);if(2*i+1>n)T->rchild=NULL;elseT->rchild=Create(A,2*i+1);}return(T);}11．编写算法判定两棵二叉树是否相似。所谓两棵二叉树s和t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。intSimilar(BiTrees,BiTreet){if(s==NULL&&q==NULL)return(1);elseif(!s&&t||s&&!t)return(0);elsereturn(Similar(s->lchild,t->lchild)&&Similar(s->rchild,t->rchild))}12．写出用逆转链方法对二叉树进行先序遍历的算法。【提示】用逆转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点的左右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的lchild或者rchild恢复。typedefstructtnode{datatypedata;inttag;/*tag的值初始为0，进入左子树时置1，从左子树回来时，再恢复为0*/structtnode*lchild,*rchild;}Bnode,*Btree;voidPreOrder(Btreebt){Bnode*r,*p,*q;/*p指向当前结点，r指向p的双亲，q指向要访问的下一结点*/if(bt==NULL)return;p=bt;r=NULL:while(p){Visit(p);/*访问p所指结点*/if(p->lchild)/*下降进入左子树*/{p->tag=1;q=p->lchild;q=p->lchild=r;r=p;p=q;} elseif(p->rchild)/*下降进入右子树*/{q=p->rchild;p->rchild=r;r=p;p=q;}else{/*上升*/whle((r&&t->tag==0)||(r&&t->tag==1&&r->rchild==NULL)){if(r&&t->tag==0){q=r->rchild;r->rchild=p;p=r;r=q;}/*从右子树回来*/else{r->tag=0;q=r->lchild;r->lchild=p;p=r;r=q;}/*从左子树回来*/if(r==NULL)return;else{r->tag=0;q=r->rchild;r->rchild=r->lchild;r->lchild=p;p=q;}/*从左子树回来，准备进入右子树*/}}}}13．对以孩子－兄弟链表表示的树编写计算树的深度的算法。【提示】采用递归算法实现。树的深度＝0若树为空Max（第一棵子树的深度＋1，兄弟子树的深度）若树非空inthigh(CSTreeT){if(T==NULL)return(0);/*若树为空，返回0*/else{h1=high(t->lchild);/**h1为T的第一棵子树的深度*/h2=high(t->nextsibling);/*h2为t的兄弟子树的深度*/return(max(h1+1,h2));}}14．对以孩子链表表示的树编写计算树的深度的算法。【提示】采用递归算法实现。树的深度＝1若根结点没有子树max(所有子树的深度)＋1若根结点有子树#defineMAXNODE树中结点的最大个数inthigh(SNodet[MAXNODE],intj){if(t[j].firstchild==NULL)return(1);/*若根结点没有子树*/else{p=t[i].firstchild;max=high(t,p->data);p=p->nextchild;while(p){h=high(t,p->data);if(h>max)max=h; p=p->nextchild;}return(max+1);}}15．对以双亲链表表示的树编写计算树的深度的算法。【提示】从每一个结点开始，从下向上搜索至根结点，记录结点的层次数，其中的最大值就是树的深度。inthigh(PNodet[],intn)/*求有n个结点的树t的深度*/{maxh=0;for(i=0;imaxh)maxh=h;}return(maxh);}6.3.1选择题1．n条边的无向图的邻接表的存储中，边结点的个数有（A）。A．nB．2nC．n/2D．n*n2．n条边的无向图的邻接多重表的存储中，边结点的个数有（A）。A．nB．2nC．n/2D．n*n3．下列哪一种图的邻接矩阵是对称矩阵？（B）。A．有向图B．无向图C．AOV网D．AOE网4．最短路径的生成算法可用（C）。A．普里姆算法B．克鲁斯卡尔算法C．迪杰斯特拉算法D．哈夫曼算法5．一个无向图的邻接表如下图所示：序号vertexfirstedge0v11v22v33v43∧203∧101∧1∧（1）从顶点v0出发进行深度优先搜索，经历的结点顺序为（B）。 A．v0,v3,v2,v1B．v0,v1,v2,v3C．v0,v2,v1,v3D．v0,v1,v3,v2（2）从顶点V0出发进行广度优先搜索，经历的结点顺序为（D）。A．v0,v3,v2,v1B．v0,v1,v2,v3C．v0,v2,v1,v3D．v0,v1,v3,v26．设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（D）。A．O(nlog2e)B．O(en)C．O(elog2n)D．O(n+e)7．含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为（A）。A．O(elog2e)B．O(en)C．O(elog2n)D．O(nlog2n)8．关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长的回路D．最短的回路9．下面关于求关键路径的说法不正确的是（C）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上10．有10个结点的无向图至少有（B）条边才能确保其是连通图。A．8B．9C．10D．116.3.2判断题1．求最小生成树的Prim算法在边较少、结点较多时效率较高。（×）2．图的最小生成树的形状可能不唯一。（√）3．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（√）4．邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×）5．任何有向网络（AOV-网络）拓扑排序的结果是唯一的。（×）6．有回路的图不能进行拓扑排序。（√）7．存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。（√）8．十字链表可以存储无向图和有向图。（×）9．任何无向图都存在生成树。（×）10．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（√）11．连通分量是无向图中的极小连通子图。（×）12．强连通分量是有向图中的极大强连通子图。（√）13．用邻接矩阵A表示图，判定任意两个结点vi和vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。（√）14．缩短关键路径上活动的工期一定能够缩短整个工程的工期。（×）15．AOE网中一定只有一条关键路径。（×）6.3.3简答题（图1）①④②③⑤⑥1．对于如图1所示的有向图，试给出：（1）每个顶点的入度和出度；（2）邻接矩阵； （3）邻接表；（4）逆邻接表；（5）强连通分量。【解答】（1）每个顶点的入度和出度：顶点1（2，1）、顶点2（2，2）、顶点3（1，3）、顶点4（3，0）、顶点5（2，3）、顶点6（1，2）。（2）邻接矩阵：000100101000000111000000110100010010（3）邻接表：013^02^345^013^14^122334^4556（4）逆邻接表：012^45^024^1^25^14^1223344556（5）强连通分量：145632v2v1v3v5v4v7v6（图2）2．设无向图G如图2所示，试给出：（1）该图的邻接矩阵；（2）该图的邻接表；（3）该图的多重邻接表；（4）从V1出发的“深度优先”遍历序列； （5）从V1出发的“广度优先”遍历序列。【解答】（1）该图的邻接矩阵：0110000101000010010000110110000100100010010000110（2）该图的邻接表：0v102^3245^36^12^02^36^45^1v22v33v44v55v66v7（3）该图的多重邻接表：v1v2v3v4v5v6v7010^231^32^343^564^6^5^（4）从v1出发的“深度优先”遍历序列：v1v2v4v3v5v7v6（5）从v1出发的“广度优先”遍历序列：v1v2v3v4v5v6v73．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？【解答】设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方。矩阵元素的个数与图的边数无关。4．设有向图G如图3所示，试画出图G的十字链表结构，并写出图G的两个拓扑序列。 v2v1v3v6v5v41图3【解答】（1）G的十字链表结构：0v1^1v22v33v4^5v64v51415^^25^43^53^54^^02^^01（2）G的两个拓扑序列：v1v2v3v6v5v4;v1v3v2v6v5v45．如图4所示AOE网：（1）列出各事件的最早、最迟发生时间；（2）列出各活动的最早、最迟发生时间；（3）找出该AOE网中的关键路径，并回答完成该工程需要的最短时间。ABCDEFGHa1=3a2=5a3=6a5=9a9=5a4=7a6=10a10=3a7=8a8=6a11=2图4（1）ve(A)=0ve(B)=ve(A)+3=3ve(C)=ve(A)+5=5ve(D)=max(ve(B)+6,ve(C)+7)=12ve(E)=ve(D)+9=21ve(G)=ve(D)+8=20ve(F)=max(ve(D)+10,ve(G)+6)=26ve(H)=max(ve(E)+E,ve(G)+2,ve(F)+3)=29vl(H)=29vl(E)=vl(H)–5=24vl(F)=vl(H)–3=26 vl(G)=min(vl(H)–2,vl(F)–6)=20vl(D)=min(vl(E)–9,vl(F)–10,vl(G)–8)=12vl(B)=vl(D)–6=6vl(C)=vl(D)–7=5vl(A)=min(vl(B)–3,vl(C)–5)=0（2）e(a1)=0e(a2)=0e(a3)=3e(a4)=5e(a5)=12e(a6)=12e(a7)=12e(a8)=20e(a9)=21e(a10)=26e(a11)=20l(a1)=3l(a2)=0l(a3)=6l(a4)=5l(a5)=15l(a6)=16(a7)=12l(a8)=20l(a9)=24l(a10)=26l(a11)=27（3）关键路径如下图，完成该工程需要的最短时间：29ACDFGHa2=5a4=7a10=3a7=8a8=67.3课后习题解答(P152)7.3.1选择题1．静态查找表与动态查找表的根本区别在于（B）A．它们的逻辑结构不一样B．施加在其上的操作不一样C．所包含的数据元素类型不一样D．存储实现不一样2．在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（A）。A．nB．1C．n+1D．n-13．顺序查找适用于存储结构为（C）的线性表。A．哈希存储B．压缩存储C．顺序存储或链式存储D．索引存储4．用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C）。A．O(log２n2)B．O(nlog２n)C．O(n)D．O(log２n)5．适用于折半查找的表的存储方式及元素排列要求为（D）。A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序6．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。A．35/12B．37/12C．39/12D．43/127．在有序表{1，3，9，12，32，41，62，75，77，82，95，100}上进行折半查找关键字为82的数据元素需要比较（C）次。A．1B．2C．4D．58．设哈希表长为14，哈希函数为H(key)=key%11。当前表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（D）。A．8B．3C．5D．99．散列函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。A．最大概率B．最小概率C．平均概率D．同等概率10．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(D)A．k-1次B．k次C．k+1次D．k（k+1）/2次 11．在哈希函数H(k)=k％m中，一般来讲，m应取（C）。A．奇数B．偶数C．素数D．充分大的数12．在采用线性探测法处理冲突所构成的哈希表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（B）A．一定是同义词B．一定不是同义词C．都相同D．不一定都是同义词13．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（B）个结点最佳。A．10B．25C．6D．62514．下列关于m阶B树的说法错误的是（D）。A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的15．m阶B树是一棵（B）。A．m叉排序树B．m叉平衡排序树C．m-1叉平衡排序树D．m+1叉平衡排序树7.3.2判断题1．顺序查找可以在顺序表上进行，不能在单链表上进行。（×）2．折半查找只能在有序的顺序表上进行。（√）3．对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。（×）4．若二叉排序树中关键字互不相同，那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（√）5．在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（√）6．将二叉排序树T1的先序遍历序列依次插入初始为空的树中，所得到的二叉排序树T2和T1的形态完全相同。（√）7．对二叉排序树进行中序遍历得到的序列是由小到大有序的。（√）8．二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（×）9．二叉排序树的查找和折半查找的时间复杂度都是O(log2n)，时间性能相同。（×）10．采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（×）11．采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（√）12．m阶B树每一个结点的子树个数都小于或等于m。（√）13．哈希表的查找效率主要取决于构造哈希表时选取的哈希函数和处理冲突的方法。（√）14．哈希法存储的基本思想是由关键码的值决定数据的存储地址。（√）15．当负载因子α小于1时，则向哈希表中插入元素时不会引起冲突。（×）16．查找表中数据元素的任何数据项都可以作为关键字。（×）17．m阶B树的任何一个结点的所有子树的高度都相等。（√）18．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（×）19．在哈希存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。 （√）20．对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。（√）7.3.3简答题1．画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。【解答】64218357910188144111216151713（1）判定树为：（2）平均查找长度为1/18(1+2*2+3*4+4*8+5*3)=32/9查找最多比较5次。2．已知如下所示长度为12的关键字有序的表：{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}（1）试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。（3）按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。【解答】（1）按关键字的顺序构造的二叉排序树：OctNovDecJulyAugSepAprMayJunJanFebMar（2）根据构造的二叉排序树，求查找成功时的平均查找长度：ASLSUCC=(1*1+2*2+3*3+4*3+5*2+6*1)/12=3.5（3）若对表中元素先进行排序构成有序表再构造二叉排序树，则构造的二叉排序树是一棵单支树，在等概率的情况下查找成功的平均查找长度则为：ASLSUCC=(1+2+…+12)/12=6.5这种情况就退化成为顺序查找。3．试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么,可知道F1=1,F2=2,.....Fn=Fn-2+Fn-1+1.含有12个结点的平衡二叉树的最大深度为５．例如：ABCDEHFGJKIL4．含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3阶B树中至少有多少个非叶子结点？4个、7个。5．试从空树开始，画出按以下次序向3阶B树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后3阶B树的状态。52686003050207070605268203052203060706．在地址空间为0～16的散列区中，对以下关键字序列构造两个哈希表：{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}（1）用线性探测开放定址法处理冲突；（2）用链地址法处理冲突。并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。【解答】（1）012345678910111213141516AprAugDecFebJanMarMayJuneJulySepOctNov平均查找长度为:31/12Aug^AprDec^Feb^JanJuly^JuneMarMay^OctNov^Sep^（2）01^234^5678^910^11^12^13^ 14^15^16^平均查找长度为:3/27．哈希函数H(key)=(3*key)%11。用开放定址法处理冲突。试在0～10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功时的平均查找长度。0123456789102267413053461301平均查找长度为:17/88．画出依次插入z，v，o，q，w，y到下图所示的5阶B树的过程。mrjdeabcfghistxzklnpmrujdeabcfghixzklstnp【解答】mrujdeabcfghiuxzklstnpmrujdeabcfghiuxzklstnopmrujdeabcfghiuxzklstnopqmrujdeabcfghiuwxzklstnopqmruxjdeabcfghiyzklstnopquw 8.3课后习题解答8.3.1选择题1．在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。A．插入排序B．选择排序C．快速排序D．归并排序2．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（C）排序法。A．冒泡排序B．快速排序C．堆排序D．基数排序3．具有12个记录的序列，采用冒泡排序最少的比较次数是（C）。A．1B．144C．11D．664．下列四种排序方法中，要求内存容量最大的是（D）。A．插入排序B．选择排序C．快速排序D．归并排序5．初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（D）。A．n2B．nlog2nC．log2nD．n-16．下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是（C）。A．直接插入排序和快速排序B．快速排序和归并排序C．直接选择排序和归并排序D．直接插入排序和归并排序7．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（B）。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38D．84，56，79，40，46，388．一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分的结果为（C）。A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，799．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：25，84，21，47，15，27，68，35，2020，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则采用的排序方法是（D）。A．选择排序B．希尔排序C．归并排序D．快速排序10．快速排序方法在（C）情况下最不利于发挥其长处。A．要排序的数据量太大B．要排序的数据中含有多个相同值C．要排序的数据已基本有序D．要排序的数据个数为奇数8.3.2判断题1．插入排序是稳定的，选择排序是不稳定的。（√）2．不稳定的排序算法是没有实用价值的。（×） 3．当待排序的元素很多时，为了交换元素的位置，移动元素要占较多的时间，这是影响时间复杂度的主要原因。（√）4．对有n个记录的集合进行归并排序，所需要的辅助空间数与初始记录的排列状况有关。（×）5．对n个记录的集合进行快速排序，所需要的附加空间数是O(n)。（×）6．堆排序所需要的附加空间数与待排序的记录个数无关。（√）7．对有n个记录的集合进行冒泡排序，所需时间决定于初始记录的排列情况，在初始记录无序的情况下最好。（×）8．对有n个记录的集合进行快速排序，所需时间决定于初始记录的排列情况，在初始记录无序的情况下最好。（√）9．对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例来。（√）10．选择排序的比较次数不会随待排序记录的关键字分布情况而改变。（√）8.3.3简答题##1．以关键字序列（tim，kay，eva，roy，dot，jon，kim，ann，tom，jim，guy，amy）为例，手工执行以下排序算法（按字典序比较关键字的大小），写出每一趟排序结束时的关键字状态：（1）直接插入排序；（2）冒泡排序；（3）直接选择排序；（4）快速排序；（5）归并排序；（6）基数排序。【解答】略。2．已知序列{50，18，12，61，8，17，87，25}，请给出采用堆排序对该序列做升序排序时的每一趟结果。【解答】堆排序过程如下图示：50387908512170897275653462615038746251217089727565390861503874621705128972756539086150361462512170897275653908876187462512170897503653908275908874625121708975036536127587462512170897908653615032758765346251217089790861503275 8790846251265389717061503275871704625126538979086150327527587897908512653275170615034624625125038976539088761170874629085126532751706189750387653908512462275170618975038750390851246227517061897653879085035124622751706189765387512503908462275170618976538765350390846227517061512897879085036534622751706151289787897503653462275170615129088790850365346227517061512897 3．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最小？为什么？【提示】采用基数排序。基数排序是一种借助多关键码排序思想对单关键码进行排序的方法，它适合n很大，而关键码较小的序列。本题中英文单词数目n>>50，而单词长度m<5，因此采用基数排序方法最佳。4．如果只想得到一个含有n个元素的序列中第k（k<2)个最大（或最小）元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。得到序列{57，11，25，36，18，80，22}的第3个最小元素之前的部分序列{11，18，22}共需14次比较：其中建堆输出11比较8次，调堆输出17和25各需要比较4次和2次。5．阅读下列排序算法，并与已学的算法比较，讨论算法中基本操作的执行次数。voidsort(SortListr){i=1;while(ir[max].key)max=j;if(min!=i){w=r[min];r[min]=r[i];r[i]=w;}if(max!=N-i+1){if(max=i){w=r[min];r[min]=r[n-i+1];r[N-i+1]=w;}else{w=r[max];r[max]=r[n-i+1];r[N-i+1]=w;}}i++;}}【解答】这是一个双向选择排序算法，每次选择关键码最小的记录放在前面，同时选择关键码最大的记录放在后面。比较n*(n-1)/2次。最好情况移动记录0次，最坏情况大约移动记录3n次。6．请回答以下关于堆的问题： （1）堆的存储结构是顺序的，还是链式的?（2）设有一个大顶堆，即堆中任意结点的关键码均大于它的左孩子和右孩子的关键码。其具有最大值的元素可能在什么地方?（3）对n个元素进行初始建堆的过程中，最多做多少次数据比较?【解答】（1）堆的存储结构是顺序的。（2）堆顶。（3）不超过4n。'