数据结构 第二版 C语言版 (李云清 杨庆红 揭安全 著) 人民邮电出版社 课后答案 107页

'䇒ৢㄨḜ㔥-Ё೑㄀ϔㄨḜϟ䕑䮼᠋ㄨḜߚ㉏爱校园社区⎬ㄨḜ(ϧϮ㑻᧰㋶ᓩ᪢ЎԴᦤկ᳡ࡵ)໻ᄺ䇒ৢㄨḜ催Ё䇒ৢㄨḜ݀݅෎⸔䇒|䗮/⬉ᄤ/⬉⇨|䅵ㅫᴎ/䕃ӊ/㔥㒰/催ϔ䇒ৢㄨḜ|催Ѡ䇒ৢㄨḜ|催ϝ䇒ৢㄨḜᙃ/᭄ᄺ|⠽⧚/ܝᄺ/ໄᄺ/⛁ᄺ/࡯ᄺ|㒣⌢ᄺ/ㅵ⧚߱Ё䇒ৢㄨḜᄺ/⊩ᄺ|࣪ᄺ/⦃๗/⫳⠽/एᄺ/ࠊ㥃|ೳᓎ/ᴎẄ/ᴤ߱ϔ䇒ৢㄨḜ|߱Ѡ䇒ৢㄨḜ|߱ϝ䇒ৢㄨḜ᭭/ࠊ䗴|૆ᄺ/ᖗ⧚ᄺ/ᬓ⊏ᄺ|᭛ᄺ/৆ᄺ/໪䇁/ᬭ㗗䆩䇒ৢㄨḜ㚆|݊ᅗ㉏߿ㄝ㑻㗗䆩㉏ㄨḜ|݀ࡵਬ㗗䆩ㄨḜ⛁䮼ㄨḜ᳔ᮄ∖ࡽ᳔ᮄㄨḜᮄ㾚䞢໻ᄺ㣅䇁䇏ݭᬭ催吓Ϯ⠜㽓ᮍ㒣⌢ᄺдὖ⥛䆎Ϣ᭄⧚㒳䅵ᬭ⿟催ㄝ᭄ᄺ˄㄀Ѩ⠜˅৿C⿟ᑣ䆒䅵㄀ϝ⠜(䈁⿟ㄨḜ˄ܼ˅Ǐk乬ㄨḜ(ᖂ㾖.ᅣ㾖(㣚䆫ᵒ㨫)催Ϟϟݠ(ৠ⌢໻ᄺ⌽ᔎ㨫)⏙ढ໻ᮄ㾚䞢㣅䇁਀࡯ॳ᭛ঞ⧚䆎࡯ᄺ㄀݁⠜(જᇨ㒓ᗻҷ᭄(ৠ⌢໻ᄺᑨ21Ϫ㑾໻ᄺ㣅䇁㄀3ݠ໡বߑ᭄Ϣ⿃ߚবᤶㄨḜ䇒ৢㄨḜǏⒼᎹϮ໻ᄺ⧚䆎⫼᭄ᄺ㋏㨫)催˄1-4˅ㄨḜǏkhd㄀ಯ⠜(ᓴܗᵫ㽓ὖ⥛Ϣ᭄⧚㒳䅵㄀Ѡ,C䇁㿔⿟ᑣ䆒䅵ᬭ⿟㄀㽓ᮍ㒣⌢ᄺ(ᖂ㾖䚼ߚ)C䇁㿔⿟ᑣ䆒䅵ᬭ⿟㄀໡বߑ᭄ܼ㾷ঞᇐᄺ[㽓ϝ⠜(⌭∳໻ᄺϝ⠜(䈁⌽ᔎᓴ(催吓Ϯ㨫)ЁѠ⠜(䈁⌽ᔎᓴᅝѸ໻㄀ಯ⠜]⼒ऎ᳡ࡵ⼒ऎ⛁⚍䖯ܹ⼒ऎhttp://www.khdaw.com/2009-10-15 课后答案网www.khdaw.com数据结构（C语言版）（第2版）www.khdaw.com习题解析揭安全李云清杨庆红江西师范大学计算机信息工程学院联系方式：janquan@163.com（习题答案仅供参考）www.khdaw.com1 课后答案网www.khdaw.com第1章绪论1.1什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不www.khdaw.com一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。1.4线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。1.8算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法的时间复杂度，大写O符号给出了函数f的一个上限。其它义如下：www.khdaw.com2 课后答案网www.khdaw.com定义：f(n)=O(g(n))当且仅当存在正的常数c和n0，使得对于所有的n≥n0，有f(n)≤cg(n)。上述定义表明，函数f顶多是函数g的c倍，除非n小于n0。因此对于足够大的n(如n≥n0)，g是f的一个上限（不考虑常数因子c）。在为函数f提供一个上限函数g时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些常用的g函数及其名称。对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大于1的常数a和b都有logan=logbn/logba,所以logan和logbn都有一个相对的乘法系数1/logba，其中a是一个常量。表1-1常用的渐进函数www.khdaw.com1.9算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。（1）i++;（2）for(i=0;ia[j+1])k=j;t=a[k];a[k]=a[i];a[i]=t;}（5）for(i=0;i#defineN100/*预定义最大的数据域空间*/typedefintdatatype;/*假设数据类型为整型*/typedefstruct{datatypedata[N];/*此处假设数据元素只包含一个整型的关键字域*/www.khdaw.comintlength;/*线性表长度*/}seqlist;/*预定义的顺序表类型*/算法countx（L,x）用于求顺序表L中值为x的结点的个数。intcountx(seqlist*L,datatypex){intc=0;inti;for(i=0;ilength;i++)if(L->data[i]==x)c++;returnc;}2.4设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a[0]等于原来的最后一个元素，a[1]等于原来的倒数第2个元素，…，a的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下：voidverge(seqlist*L){intt,i,j;i=0;j=L->length-1;while(idata[i];L->data[i++]=L->data[j];L->data[j--]=t;}}2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下：www.khdaw.com5 课后答案网www.khdaw.comvoidinsertx(seqlist*L,datatypex){intj;if(L->lengthlength-1;while(j>=0&&L->data[j]>x){L->data[j+1]=L->data[j];j--;}L->data[j+1]=x;L->length++;}}www.khdaw.com2.6将下列中缀表达式转换为等价的后缀表达式。(1)5+6*7(2)(5-6)/7(3)5-6*7*8(4)5*7-8(5)5*(7-6)+8/9(6)7*(5-6*8)-9【答】：(7)5+6*7后缀表达式：567*+(8)(5-6)/7后缀表达式：56-7/(9)5-6*7*8后缀表达式：567*8*-(10)5*7-8后缀表达式：57*8-(11)5*(7-6)+8/9后缀表达式：576-*89/+(12)7*(5-6*8)-9后缀表达式：7568*-*9-2.7循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321是一个有效的出栈序列，1423不是一个有效的出栈结果（4后面比它小的两个数2，3不是倒序）。据此，本题可以通过算法产生n个数的全排列，然后将满足出栈规则的序列输出。产生n个数的全排列有递归与非递归两种实现算法。产生全排列的递归算法：www.khdaw.com6 课后答案网www.khdaw.com设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中惟一的元素；当n>1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。依此递归定义，可设计产生perm(R)的递归算法如下：递归解法：(2_8_1.c)#includeintcont=1;/*全局变量，用于记录所有可能的出栈序列个数*/voidprint(intstr[],intn);/*求整数序列str[]从k到n的全排列*/voidperm(intstr[],intk,intn)www.khdaw.com{inti,temp;if(k==n-1)print(str,n);else{for(i=k;istr[j]){if(m==0)b[m++]=str[j];else{if(str[j]>b[0]){flag=0;}elseb[0]=str[j];}}}if(flag)/*满足出栈规则则输出str[]中的序列*/{printf("%2d:",cont++);for(i=0;iintpl(intn){inta[100];/*最大处理范围为99个数*/intflag=1,flag1=0;FILE*rf;inti,j,k,x,count=0;rf=fopen("stack.txt","w");/*pl.txt用于存放进出栈序列结果*/for(i=1;i<=n;i++)/*初始序列*/a[i]=i;www.khdaw.comwhile(flag)/*还剩余未输出的排列*/{flag1=1;/*判断本次排列是否符合进栈出栈序列*/for(i=1;i<=n;i++){j=i+1;while(j<=n&&a[j]>a[i])j++;/*找a[i]后第一个比a[i]小的元素a[j]*/k=j+1;while(k<=n)/*如果a[j]后还有比a[i]小且比a[j]大的元素,则此排列无效*/{if(a[k]a[j])flag1=0;k++;}}if(flag1){for(i=1;i<=n;i++)/*输出当前排列*/{printf("%4d",a[i]);fprintf(rf,"%4d",a[i]);}printf("n");fprintf(rf,"n");count++;/*计数器加1*/}i=n;/*从后向前找相邻位置后大前小的元素值*/while(i>1&&a[i]j&&a[i]=k&&xnext==NULLB．p==NULLC．p->next==headD．p==head（3）在带头结点的单链表中查找x应选择的程序体是（C）。A．node*p=head->next;while(p&&p->info!=x)p=p->next;if(p->info==x)returnpelsereturnNULL;www.khdaw.comB．node*p=head;while(p&&p->info!=x)p=p->next;returnp;C．node*p=head->next;while(p&&p->info!=x)p=p->next;returnp;D．node*p=head;while(p->info!=x)p=p->next;returnp;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。2nA．O(1)B．O(n)C．O(n)D．O(nlog2)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D）。A．仅修改队头指针B．仅修改队尾指针C．队头、队尾指针都要修改D．队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（B）。23nA．O(n)B．O(n)C．O(n)D．O(n×log2)（8）下面哪个术语与数据的存储结构无关（D）。A．顺序表B．链表C．散列表D．队列（9）在一个单链表中，若删除p所指结点的后续结点，则执行（A）。A．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所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。A．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;3.2设计一个算法，求一个单链表中的结点个数。【答】：单链表存储结构定义如下（相关文件：linklist.h）#includewww.khdaw.com11 课后答案网www.khdaw.com#includetypedefstructnode{intdata;structnode*next;}linknode;typedeflinknode*linklist;/*尾插法创建带头结点的单链表*/linklistcreatlinklist(){linklisthead,r,x,s;head=r=(linklist)malloc(sizeof(linknode));printf("n请输入一组以0结束的整数序列：n");scanf("%d",&x);www.khdaw.comwhile(x){s=(linklist)malloc(sizeof(linknode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;returnhead;}/*输出带头结点的单链表*/voidprint(linklisthead){linklistp;p=head->next;printf("Listis:n");while(p){printf("%5d",p->data);p=p->next;}printf("n");}基于上述结构定义，求单链表中的结点个数的算法程序如下：intcount(linklisthead){intc=0;linklistp=head;while(p){c++;www.khdaw.com12 课后答案网www.khdaw.comp=p->next;}returnc;}3.3设计一个算法，求一个带头结点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c）#include"linklist.h"intcount(linklisthead){intc=0;linklistp=head->next;while(p){c++;www.khdaw.comp=p->next;}returnc;}main()/*测试函数*/{linklisthead;head=creatlinklist();print(head);printf("nLengthofheadis:%d",count(head));getch();}当输入5个数据时，产生的输出结果如下图所示：3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成为值为y的结点的前驱结点。【答】：#include"linklist.h"voidinsert(linklisthead,inty,intx){/*在值为y的结点前插入一个值为x的结点*/linklistpre,p,s;pre=head;p=head->next;www.khdaw.com13 课后答案网www.khdaw.comwhile(p&&p->data!=y){pre=p;p=p->next;}if(p)/*找到了值为y的结点*/{s=(linklist)malloc(sizeof(linknode));s->data=x;s->next=p;pre->next=s;}}voidmain()/*测试程序*/www.khdaw.com{linklisthead;inty,x;head=creatlinklist();/*创建单链表*/print(head);/*输出单链表*/printf("n请输入y与x的值:n");scanf("%d%d",&y,&x);insert(head,y,x);print(head);}程序的一种运行结果如下图所示：3.5设计一个算法，判断一个单链表中各个结点值是否有序。【答】：#include"linklist.h"intissorted(linklisthead,charc)/*当参数c=’a’时判断链表是否为升序，当参数c=’d’是判断链表是否为降序*/{intflag=1;linklistp=head->next;switch(c){case"a":/*判断带头结点的单链表head是否为升序*/www.khdaw.com14 课后答案网www.khdaw.comwhile(p&&p->next&&flag){if(p->data<=p->next->data)p=p->next;elseflag=0;}break;case"d":/*判断带头结点的单链表head是否为降序*/while(p&&p->next&&flag){if(p->data>=p->next->data)p=p->next;elseflag=0;}break;}www.khdaw.comreturnflag;}intmain()/*测试程序*/{linklisthead;head=creatlinklist();print(head);if(issorted(head,"a"))printf("单链表head是升序排列的！n");elseif(issorted(head,"d"))printf("单链表head是降序排列的！n");elseprintf("单链表head是无序的！n");}程序运行时的三种输出结果如下图所示：3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。【答】：#include"linklist.h"voidverge(linklisthead){/*本函数的功能是就地倒置带头结点的单链表*/www.khdaw.com15 课后答案网www.khdaw.comlinklistp,q;p=head->next;head->next=NULL;while(p)/*每次从原表取一个结点插入到新表的最前面*/{q=p;p=p->next;q->next=head->next;head->next=q;}}intmain()/*测试函数*/{linklisthead;www.khdaw.comhead=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/verge(head);/*就地倒置单链表*/print(head);/*输出倒置后的单链表*/}3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。【答】：#include"linklist.h"linklistsprit(linklisthead){/*将带头结点的单链表head中的奇数值结点删除生成新的单链表并返回*/linklistL,pre,p,r;L=r=(linklist)malloc(sizeof(linknode));r->next=NULL;pre=head;p=head->next;while(p){if(p->data%2==1)/*删除奇数值结点*/{pre->next=p->next;r->next=p;r=p;p=pre->next;}else/*保留偶数值结点*/{pre=p;p=p->next;}www.khdaw.com16 课后答案网www.khdaw.com}r->next=NULL;/*置链表结束标记*/returnL;}intmain()/*测试函数*/{linklisthead,L;head=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/L=sprit(head);/*分裂单链表head*/printf("n原单链表为:n");print(head);/*输出倒置后的单链表*/printf("n分裂所得奇数单链表为:n");www.khdaw.comprint(L);}本程序的一组测试情况如下图所示。3.8设计一个算法，对一个有序的单链表，删除所有值大于x而不大于y的结点。【答】：#include"linklist.h"voiddeletedata(linklisthead,datatypex,datatypey){/*删除带头结点单链表中所有结点值大于x而不大于y的结点*/linklistpre=head,p,q;p=head->next;/*初始化*/while(p&&p->data<=x)/*找第1处大于x的结点位置*/{pre=p;p=p->next;}while(p&&p->data<=y)/*找第1处小于y的位置*/p=p->next;q=pre->next;/*删除大于x而小于y的结点*/pre->next=p;pre=q->next;www.khdaw.com17 课后答案网www.khdaw.comwhile(pre!=p)/*释放被删除结点所占用的空间*/{free(q);q=pre;pre=pre->next;}}voidmain()/*测试函数*/{linklisthead,L;datatypex,y;head=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/printf("n请输入要删除的数据区间:n");www.khdaw.comscanf("%d%d",&x,&y);deletedata(head,x,y);print(head);/*输出删除后的单链表*/}3.9设计一个算法，在双链表中值为y的结点前面插入一个值为x的新结点。即使值为x的新结点成为值为y的结点的前驱结点。【答】：首先定义双链表的数据结构，相关文件dlink.h，内容如下：typedefintdatatype;/*预定义的数据类型*/typedefstructdlink_node{/*双链表结点定义*/datatypedata;structdlink_node*llink,*rlink;}dnode;typedefdnode*dlinklist;/*双链表结点指针类型定义*//*尾插法创建带头结点的双链表*/dlinklistcreatdlinklist(void){dlinklisthead,r,s;datatypex;head=r=(dlinklist)malloc(sizeof(dnode));/*建立双链表的头结点*/head->llink=head->rlink=NULL;printf("n请输入双链表的内容：（整数序列，以0结束）n");scanf("%d",&x);while(x)/*输入结点值信息，以0结束*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=r->rlink;/*将新结点s插入到双链表链尾*/www.khdaw.com18 课后答案网www.khdaw.coms->llink=r;r->rlink=s;r=s;scanf("%d",&x);}returnhead;}/*输出双链表的内容*/voidprint(dlinklisthead){dlinklistp;p=head->rlink;printf("n双链表的内容是：n");www.khdaw.comwhile(p){printf("%5d",p->data);p=p->rlink;}}本题的求解程序如下：#include#include"dlink.h"voidinsertxaty(dlinklisthead,datatypey,datatypex){dlinklists,p;/*首先在双链表中找y所在的结点，然后在y前面插入新结点*/p=head->rlink;while(p&&p->data!=y)p=p->rlink;if(!p)printf("n双链表中不存在值为y的结点,无法插入新结点!n");else/*插入值为x的新结点*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=p;s->llink=p->llink;p->llink->rlink=s;p->llink=s;}}voidmain()/*测试函数*/{dlinklisthead;datatypex,y;www.khdaw.com19 课后答案网www.khdaw.comhead=creatdlinklist();print(head);printf("n请输入要输入的位置结点值y:n");scanf("%d",&y);printf("n请输入要输入的结点值x:n");scanf("%d",&x);insertxaty(head,y,x);/*在值为y的结点前插入值为x的新结点*/print(head);/*输出新的双链表*/getch();}本程序的一组测试情况如下图所示。www.khdaw.com3.10设计一个算法，从右向左打印一个双链表中各个结点的值。【答】：本题的双链表定义同题3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实现如下：#include#include"dlink.h"voidvprint(dlinklisthead){/*递归方法从右向左打印双链表的值*/if(head->rlink){vprint(head->rlink);printf("%5d",head->rlink->data);}}voidmain()/*测试函数*/{dlinklisthead;head=creatdlinklist();print(head);printf("n从右向左打印的双链表的内容是:n");www.khdaw.com20 课后答案网www.khdaw.comvprint(head);getch();}本程序的一组测试情况如下图所示。3.11设计一个算法，将一个双链表改建成一个循环双链表。【答】：#includewww.khdaw.com#include"dlink.h"/*将一个双链表改成循环双链表*/voiddlinktocdlink(dlinklisthead){dlinklistr;r=head;while(r->rlink)/*寻找尾结点*/r=r->rlink;head->llink=r;r->rlink=head;}voidprintcdlink(dlinklisthead){/*打印双链表*/dlinklistp;p=head->rlink;while(p!=head){printf("%5d",p->data);p=p->rlink;}}intmain()/*测试函数*/{dlinklisthead;head=creatdlinklist();dlinktocdlink(head);printf("n循环双链表的内容是：n");printcdlink(head);}www.khdaw.com21 课后答案网www.khdaw.com第4章字符串、数组和特殊矩阵4.1稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。4.2设有一个10×10的对称矩阵A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素a00的地址为1，每个数据元素占2个字节，则a65的地址为（53）。4.3若串S=“software”，其子串的数目为（36）。4.4常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。4.5要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空间）。4.6对于半带宽为b的带状矩阵，它的特点是：对于矩阵元素aij，若它满足（|i-j|>b），www.khdaw.com则aij=0。4.7字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。4.8试编写一个函数，实现在顺序存储方式下字符串的strcompare（S1，S2）运算。【答】：#include#include#defineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;/*函数strcompare()的功能是：当s1>s2时返回1，当s1==s2时返回0，当s1s2.str[i]){m=1;break;}elseif(s1.str[i]s2n");elseif(m==-1)printf("s2>s1n");elseif(m==0)printf("s1=s2n");}4.9试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。【参考程序1】：www.khdaw.com/*本程序用来在顺序存储下用快速匹配模式实现在字符串S中用T2替换所有T1出现的可能*/#include#include#include#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;//求next[]函数voidgetnext(seqstring*p,intnext[]){inti,j;next[0]=-1;i=0;j=-1;while(ilength){if(j==-1||p->str[i]==p->str[j]){++i;++j;next[i]=j;}elsej=next[j];}}//快速模式匹配算法intkmp(seqstring*t,seqstring*p,intnext[],inttemppos){inti,j;www.khdaw.com23 课后答案网www.khdaw.comi=temppos,j=0;while(ilength&&jlength){if(j==-1||t->str[i]==p->str[j]){i++;j++;}elsej=next[j];}if(j==p->length)return(i-p->length);elsereturn(-1);}//替换函数voidtakeplace(seqstring*S,seqstring*T1,seqstring*T2)www.khdaw.com{intnext[maxsize],temppos=0,pos,i;intlent1,lent2;lent1=strlen(T1->str);//求T1串长度lent2=strlen(T2->str);//求T2串长度getnext(T1,next);//求T1串的next[]向量do{pos=kmp(S,T1,next,temppos);//快速模式匹配temppos=pos+T1->length;if(pos!=-1)//匹配成功{if(lent1>lent2)//T1串长度大于T2串长度{for(i=temppos;ilength;i++)//前移S->str[i-lent1+lent2]=S->str[i];for(i=0;ilength;i++)//替换S->str[pos+i]=T2->str[i];S->length-=lent1-lent2;//修改长度}elseif(lent2>lent1)//T2串长度大于T1串长度{for(i=S->length-1;i>=temppos;i--)//后移留空S->str[i+lent2-lent1]=S->str[i];for(i=0;ilength;i++)//替换www.khdaw.com24 课后答案网www.khdaw.comS->str[pos+i]=T2->str[i];S->length+=lent2-lent1;//修改长度}else//T1长度与T2长度相等{for(i=0;ilength;i++)S->str[pos+i]=T2->str[i];}temppos=pos+T2->length;//修改下一次模式匹配的起点位置}}while(pos!=-1);S->str[S->length]="";}www.khdaw.comintmain(){seqstring*S,*T1,*T2;printf("nn本程序用来实现字符串替换，将S中用T2替换T1所有出现nThisprogramisusedforcharactersbatchtakeingplace,TheT1charactersbatchwilltakeplacealltheT2"sappearancesincharactersbatchS:nn");printf("请输入S中的字符(pleseinputcharactersbatchS:)n");S=(seqstring*)malloc(sizeof(seqstring));T1=(seqstring*)malloc(sizeof(seqstring));T2=(seqstring*)malloc(sizeof(seqstring));scanf("%s",S->str);S->length=strlen(S->str);printf("输入要被替换的串(inputT1):n");scanf("%s",T1->str);T1->length=strlen(T1->str);printf("输入替换串(inputT2):n");scanf("%s",T2->str);T2->length=strlen(T2->str);takeplace(S,T1,T2);printf("替换后的字符串为：n");printf("%sn",S->str);free(S);free(T1);free(T2);}【参考程序2】：#includewww.khdaw.com25 课后答案网www.khdaw.com#defineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;voidgetnext(seqstringp,intnext[])//求模式的next函数{inti,j;next[0]=-1;i=0;j=-1;while(ilength){j=0;while(ilength&&jstr[i]==t1.str[j]){i++;j++;}elsej=next[j];}if(j==t1.length)//匹配成功{c=i-t1.length;if(t1.length==t2.length)//两串长度相等直接替换for(k=0;kstr[c+k]=t2.str[k];elseif(t1.lengthlength-1;m>i-1;m--)s->str[t2.length-t1.length+m]=s->str[m];//后移留空for(k=0;kstr[c+k]=t2.str[k];s->length=s->length-t1.length+t2.length;s->str[s->length]="";}www.khdaw.com26 课后答案网www.khdaw.comelse{for(m=i-1;mlength;m++)//前移s->str[m-t1.length+t2.length]=s->str[m];for(k=0;kstr[c+k]=t2.str[k];s->length=s->length-t1.length+t2.length;s->str[s->length]="";}i=i+t2.length-t1.length;}i++;}www.khdaw.com}intmain(){intnext[MAXSIZE];seqstrings,t1,t2;printf("Inputstrings:");//输入主串gets(s.str);printf("nInputstringt1:");//输入模式串gets(t1.str);printf("nInputstringt2:");//输入拟替换的串gets(t2.str);s.length=strlen(s.str);t1.length=strlen(t1.str);t2.length=strlen(t2.str);getnext(t1,next);replace(&s,t1,t2,next);puts(s.str);}4.10试编写一个函数，实现在链式存储方式下字符串的strcompare（S1，S2）运算。【参考程序】：/*建立字符串链式存储结构文件linkstring.h*/#include#includetypedefstructnode{chardata;structnode*next;}linkstrnode;www.khdaw.com27 课后答案网www.khdaw.comtypedeflinkstrnode*linkstring;/*---------------------------------------*//*尾插法建立单链表*//*---------------------------------------*/voidstrcreate(linkstring*S){charch;linkstrnode*p,*r;*S=NULL;r=NULL;while((ch=getchar())!="n"){p=(linkstrnode*)malloc(sizeof(linkstrnode));p->data=ch;/*产生新结点*/if(*S==NULL)/*新结点插入空表*/www.khdaw.com{*S=p;r=p;}else{r->next=p;r=p;}}if(r!=NULL)r->next=NULL;/*处理表尾结点指针域*/}/*---------------------------------------------*//*输出单链表的内容*//*---------------------------------------------*/voidprint(linkstringhead){linkstrnode*p;p=head;while(p){printf("%c-->",p->data);p=p->next;}printf("n");}#include“linkstring.h”intstrcompare(linkstrnode*S1,linkstrnode*S2){while(S1&&S2){if(S1->data>S2->data)return1;elseif(S1->datadata)www.khdaw.com28 课后答案网www.khdaw.comreturn-1;S1=S1->next;S2=S2->next;}if(S1)return1;elseif(S2)return-1;return0;}intmain(){linkstrings1,s2;intk;printf("nPleaseinputs1:");www.khdaw.comstrcreate(&s1);/*建立字符串s1*/print(s1);printf("nPleaseinputs2:");strcreate(&s2);/*建立字符串s2*/print(s2);k=strcompare(s1,s2);if(k==1)printf("s1>s2");elseif(k==-1)printf("s1data=p->data;if(L==NULL)L=r=s;else{r->next=s;www.khdaw.com29 课后答案网www.khdaw.comr=s;}p=p->next;}if(r!=NULL)r->next=NULL;returnL;}/*------------------------------------------------*//*在字符串S中用T2替换T1*//*------------------------------------------------*/linkstringreplace(linkstringS,linkstringT1,linkstringT2){linkstringp,q,r,s,pre,temp,pos;www.khdaw.comintflag=1;if(S==NULL||T1==NULL)returnS;/*若S为空或T1为空,则原串不变*/pre=NULL;pos=S;/*pos表示可能的T1串在S中的起始位置*/while(pos&&flag)/*flag表示S中存在T1*/{p=pos;q=T1;while(p&&q)/*从pos开始找子串T1*/{if(p->data==q->data){p=p->next;q=q->next;}else{pre=pos;pos=pos->next;p=pos;q=T1;}}if(q!=NULL)flag=0;/*未找到子串T1*/else{flag=1;/*找到了子串T1,用T2代替T1*/r=pos;while(r!=p)/*首先删除子串T1,最后p指向删除串T1的下一个结点*/{s=r;r=r->next;free(s);}if(T2!=NULL)/*T2不为空*/www.khdaw.com30 课后答案网www.khdaw.com{temp=r=copy(T2);/*复制一个T2串*/while(r->next!=NULL)/*找temp串的尾结点*/r=r->next;r->next=p;if(pre==NULL)/*如果T1出现在S的链头*/S=temp;/*新串成为链首*/else/*T1不是链首串*/pre->next=temp;pre=r;pos=p;/*从p开始继续找子串T1*/}else/*原T2子串为空*/www.khdaw.com{if(pre==NULL)/*T1为链首串*/S=p;elsepre->next=p;pos=p;}}}returnS;}intmain(){linkstringS,T1,T2;printf("nPleaseinputS:");strcreate(&S);/*建立字符串S*/print(S);printf("nPleaseinputT1:");strcreate(&T1);/*建立字符串T1*/print(T1);printf("nPleaseinputT2:");strcreate(&T2);/*建立字符串T2*/print(T2);S=replace(S,T1,T2);printf("nTheresultis:n");print(S);}4.12已知如下字符串，求它们的next数组值：（1）“bbdcfbbdac”www.khdaw.com31 课后答案网www.khdaw.com【答】：-1010001230（2）“aaaaaaa”【答】：-1012345（3）“babbabab”【答】：-100112324.13已知正文t=“ababbaabaa”，模式p=“aab”，试使用KMP快速模式匹配算法寻找p在t中首次出现的起始位置，给出具体的匹配过程分析。【答】：模式p的next向量如下表所示：012aab-101第一趟匹配：www.khdaw.com0123456789ababbaabaaaai=1，j=1，匹配失败，此时j取next[1]=0，即下一趟匹配从i=1，j=0开始；第二趟匹配：0123456789ababbaabaaai=1，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=2，j=0开始；第三趟匹配：0123456789ababbaabaaaai=3，j=1，匹配失败，此时j=next[1]=0，下一趟匹配从i=3，j=0开始；第四趟匹配：0123456789ababbaabaaai=3，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=4，j=0开始；第五趟匹配：0123456789ababbaabaaai=4，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=5，j=0开始；第五趟匹配：0123456789www.khdaw.com32 课后答案网www.khdaw.comababbaabaaaabi=8，j=3，匹配完成，表明匹配成功的位置是：i-j=5。4.14已知三维数组A[3][2][4]，数组首地址为100，每个元素占用1个存储单元，分别计算数组元素A[0][1][2]在按行优先和按列优先存储方式下的地址。【答】：A[0][1][2]按行优先方式在内存的存储地址为：100+0*8+1*4+2=106A[0][1][2]按列优先方式在内存的储储地址为：100+2*6+1*3+0*8=1154.15已知两个稀疏矩阵A和B，其行数和列数均对应相等，编写一个函数，计算A和B之和，假设稀疏矩阵采用三元组表示。【参考程序1】：#includewww.khdaw.comtypedefstruct{intdata[100][100];intm,n;/*分别存放稀疏矩阵的行数、列数和非零元素的个数*/}matrix;typedefintspmatrix[100][3];//三元组存储结构spmatrixc;voidadd(spmatrixa,spmatrixb,spmatrixc)//基于三元组结构的矩阵相加算法{inti,j,k,t,r;i=j=k=1;while(i<=a[0][2]&&j<=b[0][2]){if(a[i][0]b[j][0]||(a[i][0]==b[j][0]&&a[i][1]>b[j][1])){c[k][0]=b[j][0];c[k][1]=b[j][1];c[k][2]=b[j][2];j++;k++;}elseif(a[i][0]==b[j][0]&&(a[i][1]==b[j][1])){c[k][0]=a[i][0];www.khdaw.com33 课后答案网www.khdaw.comc[k][1]=a[i][1];c[k][2]=a[i][2]+b[j][2];i++;j++;if(c[k][2]!=0)k++;/*如果相加的和不为0,则生成一个有效项*/}}while(j<=b[0][2]){c[k][0]=b[j][0];c[k][1]=b[j][1];c[k][2]=b[j][2];j++;k++;}www.khdaw.comwhile(i<=a[0][2]){c[k][0]=a[i][0];c[k][1]=a[i][1];c[k][2]=a[i][2];i++;k++;}c[0][0]=a[0][0];c[0][1]=a[0][1];c[0][2]=k-1;}//函数compressmatrix将普通矩阵存储转换为三元组存储结构voidcompressmatrix(matrix*A,spmatrixB){inti,j,k;k=1;for(i=0;im;i++)for(j=0;jn;j++)if(A->data[i][j]!=0){B[k][0]=i;B[k][1]=j;B[k][2]=A->data[i][j];k++;}B[0][0]=A->m;B[0][1]=A->n;B[0][2]=k-1;www.khdaw.com34 课后答案网www.khdaw.comi=0;printf("thespmatrixis:n");while(i<=B[0][2]){printf("%d%5d%5dn",B[i][0],B[i][1],B[i][2]);i++;}}voidcreat(intr,intw,matrix*s){inti,j,data;printf("inputnumbers:n");for(i=0;idata[i][j]=data;}printf("thearrayis:n");for(i=0;idata[i][j]);printf("n");}s->m=r;s->n=w;}intmain(){matrixp,q;spmatrixa,b,c;intr,w,i;i=0;printf("inputr,w:");/*输入行和列*/scanf("%d%d",&r,&w);creat(r,w,&p);creat(r,w,&q);compressmatrix(&p,a);compressmatrix(&q,b);i=0;add(a,b,c);printf("thespmatrixcis:n");www.khdaw.com35 课后答案网www.khdaw.comwhile(i<=c[0][2]){printf("%d%5d%5dn",c[i][0],c[i][1],c[i][2]);i++;}}程序运行时先输入矩阵的行和列，然后按普通矩阵格式输入矩阵值，一组程序测试用例运行结果如下图：www.khdaw.com【参考程序2】：www.khdaw.com36 课后答案网www.khdaw.com#include#include#defineMAX100typedefstruct{intdata[MAX][3];intm,n,value;}matrix;matrix*Input(matrix*A){inti,j;A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d",&A->m,&A->n,&A->value);A->data[0][0]=A->m;www.khdaw.comA->data[0][1]=A->n;A->data[0][2]=A->value;for(i=1;i<=A->value;i++){for(j=0;j<3;j++)scanf("%d",&A->data[i][j]);}returnA;}voidOutput(matrix*A){inti,j;printf("************************************n");for(i=0;i<=A->value;i++){for(j=0;j<3;j++)printf("%d",A->data[i][j]);printf("n");}printf("************************************n");}matrix*addmatrix(matrix*A,matrix*B,matrix*C){inti=1,j=1,k=1;C=(matrix*)malloc(sizeof(matrix));while(i<=A->value&&j<=B->value){if(A->data[i][0]==B->data[j][0]){www.khdaw.com37 课后答案网www.khdaw.comif(A->data[i][1]==B->data[j][1]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2]+B->data[j][2];if(C->data[k][2]!=0)k++;i++;j++;}elseif(A->data[i][1]data[j][1]){C->data[k][0]=A->data[i][0];www.khdaw.comC->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++;}else{C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++;}}elseif(A->data[i][0]data[j][0]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++;}else{C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];www.khdaw.com38 课后答案网www.khdaw.comk++;j++;}}while(i<=A->value){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++;}www.khdaw.comwhile(j<=B->value){C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++;}C->data[0][0]=(A->data[0][0]>=B->data[0][0])?A->data[0][0]:B->data[0][0];C->data[0][1]=(A->data[0][1]>=B->data[0][1])?A->data[0][1]:B->data[0][1];C->data[0][2]=k-1;C->value=k-1;returnC;}intmain(){matrix*A=NULL,*B=NULL,*C=NULL;printf("提示：请按三元组格式输入矩阵内容。n");printf("InputAmatrix:n");A=Input(A);printf("InputBmatrix:n");B=Input(B);C=addmatrix(A,B,C);Output(C);free(A);free(B);www.khdaw.com39 课后答案网www.khdaw.comfree(C);return0;}程序运行时按照三元组的格式输入矩阵信息，程序运行结果如下图所示：www.khdaw.com4.16写出两个稀疏矩阵相乘的算法，计算：Cpn=Apm∗Bmn其中，A、B和C都采用三元组表示法存储。【答】：#include#include#defineMAX100typedefstruct{intdata[MAX][3];intm,n,value;}matrix;matrix*Input(matrix*A){inti,j;A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d",&A->m,&A->n,&A->value);A->data[0][0]=A->m;www.khdaw.com40 课后答案网www.khdaw.comA->data[0][1]=A->n;A->data[0][2]=A->value;for(i=1;i<=A->value;i++){for(j=0;j<3;j++)scanf("%d",&A->data[i][j]);}returnA;}voidOutput(matrix*A){inti,j;www.khdaw.comprintf("*******************************n");for(i=0;i<=A->value;i++){for(j=0;j<3;j++)printf("%d",A->data[i][j]);printf("n");}printf("*******************************n");}/*基于三元组存储结构的矩阵相乘算法*/matrix*MulMatrix(matrix*A,matrix*B,matrix*C){inti,j,k,r=1,p,q,s;C=(matrix*)malloc(sizeof(matrix));C->m=A->m;C->n=B->n;C->data[0][0]=C->m;C->data[0][1]=C->n;for(i=0;im;i++)for(j=0;jn;j++){s=0;for(k=0;kn;k++)//找A[i][k];{p=1;while(p<=A->value)if(A->data[p][0]==i&&A->data[p][1]==k)break;www.khdaw.com41 课后答案网www.khdaw.comelsep++;//找B[k][j];q=1;while(q<=B->value)if(B->data[q][0]==k&&B->data[q][1]==j)break;elseq++;if(p<=A->value&&q<=B->value)s=s+A->data[p][2]*B->data[q][2];}if(s!=0){C->data[r][0]=i;www.khdaw.comC->data[r][1]=j;C->data[r][2]=s;r++;}}C->data[0][2]=r-1;C->value=r-1;returnC;}intmain(){matrix*A=NULL,*B=NULL,*C=NULL;printf("提示：请按三元组格式输入矩阵内容。n");printf("InputAmatrix:n");A=Input(A);printf("InputBmatrix:n");B=Input(B);C=MulMatrix(A,B,C);Output(C);free(A);free(B);free(C);return0;}程序运行时，要求按照三元组的格式输入矩阵信息。www.khdaw.com42 课后答案网www.khdaw.comwww.khdaw.comwww.khdaw.com43 课后答案网www.khdaw.com第5章递归5.1试述递归程序设计的特点。【答】：（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有些问题的递归程序可能存在几个递归出口。（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。5.2试简述简单递归程序向非递归程序转换的方法。【答】：简单递归程序转换为非递归程序可以采用算法设计中的递推技术。递归方法与递www.khdaw.com推方法共同采用的分划技术，为使用递推技术解决递归问题奠定了基础。由于简单递归问题求解过程中无需回溯，因而要转换成非递归方式实现完全可以使用递推技术。为了使用自底向上的递推方式来解决递归问题，利用子问题已有的解构造规模较大子问题的解，进而构造原问题的解，必须建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录求解过程中递推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。5.3试简述复杂递归程序向非递归程序转换的方法，并说明栈在复杂递归程序转换成非递归程序的过程中所起的作用。【答】：复杂递归问题在求解的过程中无法保证求解动作一直向前，需要设置一些回溯点，当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所设置的回溯点。5.4试给出例题5.1中Fact(5)的执行过程分析。【答】：Fact(5)的执行过程如下图所示：2n5.5已知多项式pn(x)=a0+a1x+a2x+…+anx的系数按顺序存储在数组a中，试：（1）编写一个递归函数，求n阶多项式的值；www.khdaw.com44 课后答案网www.khdaw.com（2）编写一个非递归函数，求n阶多项式的值。【答】：#include#include#includedoublepnx1(doublea[],intn,doublex)//（1）递归函数{if(n==0)returna[0];elsereturnpnx1(a,n-1,x)+a[n]*pow(x,n);}doublepnx2(doublea[],intn,doublex)//（2）非递归迭代函数{www.khdaw.comdoublet;inti;t=a[n];for(i=n-1;i>=0;i--)t=a[i]+t*x;returnt;}intmain(){double*a,x,p;intn,i;printf("请输入n,x:n");scanf("%d%lf",&n,&x);a=(double*)malloc((n+1)*sizeof(double));printf("请输入%d项系数：n",n+1);for(i=0;i<=n;i++)scanf("%lf",&a[i]);p=pnx1(a,n,x);printf("%fn",p);p=pnx2(a,n,x);printf(“%fn”,p);free(a);}5.6已知两个一维整型数组a和b，分别采用递归和非递归方式编写函数，求两个数组的内积（数组的内积等于两个数组对应元素相乘后再相加所得到的结果）。【答】：#includeusingnamespacestd;www.khdaw.com45 课后答案网www.khdaw.comlongsum1(inta[],intb[],intn)//非递归函数{longs=0;inti;for(i=0;i>n;a=newint[n];b=newint[n];cout<<"请输入数组a的值"<>a[i];cout<<"请输入数组b的值"<>b[i];s=sum1(a,b,5);cout<<"非递归计算的和="<0且m>0【答】：//输入m,和n的值，计算Ack(m,n)#includeintAck(intm,intn){if(m==0){returnn+1;}elseif(n==0){returnAck(m-1,1);}elsewww.khdaw.com{returnAck(m-1,Ack(m,n-1));}}intmain(){intm,n;printf("Pleaseinputmnn");scanf("%d%d",&m,&n);printf("Ack(m,n)=%dn",Ack(m,n));return0;}5.8已知多项式Fn(x)的定义如下：⎧10n=⎪Fx()==⎨2xn1n⎪⎩2(xFx)−−2(1n)(Fx)n>1nn−−12试写出计算Fn(x)值的递归函数。【答】：//输入n，x计算F(x)#include//为了符合递归函数的表达这里将x作为参数传递，在实际运用中建议使用全局变量。//C++中也可以传递引用intFunction(intn,constint&x)intFunction(intn,intx){if(n==0){return1;}elseif(n==1)www.khdaw.com47 课后答案网www.khdaw.com{return2*x;}else{return2*x*Function(n-1,x)-2*(n-1)*Function(n-2,x);}}intmain(){intn,x;printf("inputn,x:n");scanf("%d%d",&n,&x);printf("F(x)=%dn",Function(n,x));return0;www.khdaw.com}5.9n阶Hanoi塔问题：设有3个分别命名为X，Y和Z的塔座，在塔座X上从上到下放有n个直径各不相同、编号依次为1，2，3，…，n的圆盘（直径大的圆盘在下，直径小的圆盘在上），现要求将X塔座上的n个圆盘移至塔座Z上，并仍然按同样的顺序叠放，且圆盘移动时必须遵循以下规则：（1）每次只能移动一个圆盘；（2）圆盘可以插在塔座X，Y和Z中任何一个塔座上；（3）任何时候都不能将一个大的圆盘压在一个小的圆盘之上。试编写一个递归程序实现该问题。【答】：#includevoidHanoi(intn,charx,chary,charz){if(n==1)printf("%c-->%cn",x,z);else{Hanoi(n-1,x,z,y);printf("%c-->%cn",x,z);Hanoi(n-1,y,x,z);}}intmain(){intn;printf("请输入盘子个数：");www.khdaw.com48 课后答案网www.khdaw.comscanf("%d",&n);Hanoi(n,"X","Y","Z");return0;}5.10八皇后问题：在一个8×8格的国际象棋棋盘上放上8个皇后，使其不能相互攻击，即任何两个皇后不能处于棋盘的同一行、同一列和同一斜线上。试编写一个函数实现八皇后问题。【答】：www.khdaw.com解法一：（程序place.cpp）解向量：(x1，x2，…，xn)显约束：xi=1，2，…，n隐约束：1）不同列：xi≠xj2）不处于同一正、反对角线：|i-j|≠|xi-xj|#include#include#definen8intx[n+1]={0};//x[i]的含义表示第i行放置在x[i]列intsum=0;//sum用于记录n后问题的所有解voidprint();//输出n后问题的解intPlace(intk)//检测第k行的皇后放置是否符后规则{for(intj=1;jn){sum++;print();//输出一种解方案getchar();www.khdaw.com49 课后答案网www.khdaw.com}elsefor(inti=1;i<=n;i++){x[t]=i;//试探在第t行放在第i列if(Place(t))Backtrack(t+1);}}voidprint()//输出n后问题的解{inti;printf("%d皇后问题的第%d种解为:n",n,sum);for(i=1;i<=n;i++)printf("%d:%dn",i,x[i]);www.khdaw.com}intmain(){Backtrack(1);}解法二：程序思想：用3个数组分别存放8列，15个左对角线和15个右对角线的值,同时用一个8元素大小的数组记录下放置的皇后的位置。初始时将三个数组全部标记为0。一，从第一行开始，从左向右开始查找。当找到第一个能够放下棋子的点x,y（其对应的列，左对角，右对角全部为0）后，将此棋子所对应的列，左对角，右对角全部设置为1，然后继续放置下一行——x+1行（调用自身的子函数）。二，当其子函数执行完毕后，将放在x,y上的点拿起，然后将这点对应的列，左对角，右对角元素全部置0，然后继续在此行的y后查找能放置的点。三，如果当前要放置的棋子为第9个棋子的时候，打印结果。程序见5_10.c（递归法）5_10_byStack.c(用栈回溯法)/*****************************************************//*八皇后问题递归解法*//*****************************************************/#includeintleft[16],right[16],row[9],queen[9],count=0;/*分别用来存放左对角线和右对角线的使用情况,row数组记录行数的棋子摆放情况，未使用的话就赋予0，使用的话就赋予1*//*row的数组用来存放列的使用情况，当第n行，第m列被使用的时候在row[n]=m*//*其中queen数组用来专门存放当前皇后的摆放情况*/www.khdaw.com50 课后答案网www.khdaw.comintprin()/*打印出皇后的放置情况*/{intm;count++;printf("The%dth",count);for(m=1;m<=8;m++)printf("%d",queen[m]);printf("n");return0;}intkaiserin(intline)/*line表示当前放棋子的列数,第一次放的时候为1列*/{inti;/*本变量用来记录当前行放子的列数*/for(i=1;i<=8;i++)www.khdaw.comif((row[i]||left[i+line-1]||right[8-i+line])==0)/*看当前的列是否可以放*/{row[i]=1;left[i+line-1]=1;right[8-i+line]=1;queen[line]=i;if(line==8)/*如果当前找到第8行了，说明找成功了，打印*/prin();elsekaiserin(line+1);/*找到了，但是还没找完，将这点放上，然后尝试下一列*/left[i+line-1]=0;row[i]=0;right[8-i+line]=0;queen[line]=0;/*不管找到没找到，重新初始化当前放子的点，开始右移放子*/}return0;}voidinit()/*将三个数组进行初始化*/{inti;for(i=1;i<16;i++)left[i]=right[i]=0;for(i=1;i<9;i++)queen[i]=row[i]=0;}intmain(){init();kaiserin(1);return0;}www.khdaw.com51 课后答案网www.khdaw.com/********************************************//*八皇后问题回溯法*//********************************************/#include#definemax10typedefstruct{/*用来存放回溯点的信息，row用来存放回溯点所放的行数，line用来存放所放的列数*/introw;intline;}node;intleft[16],right[16],row[9],queen[9],count=0;/*分别用来存放左对角线和右对角线的使用情www.khdaw.com况,row数组记录行数的棋子摆放情况，未使用的话就赋予0，使用的话就赋予1*//*row的数组用来存放列的使用情况，当第n行，第m列被使用的时候在row[n]=m*//*其中queen数组用来专门存放当前皇后的摆放情况*/voidprint()/*打印出皇后的放置情况*/{intm;count++;printf("The%dth",count);for(m=1;m<=8;m++)printf("%d",queen[m]);printf("n");}voidinit()/*将三个数组进行初始化*/{inti;for(i=1;i<16;i++)queen[i]=left[i]=right[i]=0;for(i=1;i<9;i++)row[i]=0;}intkaiserin(){nodeback[max];intopline=1,oprow=1,i,find,top=0;while(1)/*循环条件用真，用return来结束循环和整个函数*/{find=0;for(i=oprow;i<=8;i++)if((row[i]||left[i+opline-1]||right[8-i+opline])==0)/*判断当前的点是否可放*/{find=1;/*找到的话结束循环*/break;www.khdaw.com52 课后答案网www.khdaw.com}if(find)/*找到了这点*/{oprow=i;row[oprow]=1;left[oprow+opline-1]=1;right[8-oprow+opline]=1;queen[opline]=oprow;/*把这个点放上*/top++;back[top].row=oprow;back[top].line=opline;/*记录回溯点*/opline++;oprow=1;/*开始找下一行*/}else/*需要进行回溯*/{if(opline==9)www.khdaw.comprint();do{if(top==0)return0;/*如果栈取空了，说明查找结束*/oprow=back[top].row;/*如果栈中还有元素可取*/opline=back[top].line;/*取出栈顶元素*/top--;row[oprow]=0;left[oprow+opline-1]=0;/*同时将这个棋子拿起*/right[8-oprow+opline]=0;queen[opline]=0;}while(oprow==8);/*当取到的oprow的右边可以放子时，开始下一步操作*/oprow++;}}}main(){init();kaiserin();}www.khdaw.com53 课后答案网www.khdaw.com第6章树6.1树最适合用来表示具有（有序）性和（层次）性的数据。6.2在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（数据间关系）的存储。6.3对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1）。6.4已知一棵树如图6.11所示，试回答以下问题：www.khdaw.com图6.11一棵树（1）树中哪个结点为根结点？哪些结点为叶子结点？【答】：A是根结点；E，G，H，I，C，J，K，L为叶结点。（2）结点B的双亲为哪个结点？其子女为哪些结点？【答】：B的双亲结点是A，其子女结点为E和F。（3）哪些结点为结点I的祖先？哪些结点为结点B的子孙？【答】：F，B，A是结点I的祖先结点；E，F，G，H，I是B的子孙结点。（4）哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？【答】：B，C，L是结点D的兄弟结点，J是结点K的兄弟结点。（5）结点J的层次为多少？树的高度为多少？【答】：结点J的层次为3，树的高度为4。（6）结点A、C的度分别为多少？树的度为多少？【答】：结点A的度为4，结点C的度是0，树的度是4。（7）以结点B为根的子树的高度为多少？【答】：以结点B为根的子树的高度是3。（8）试给出该树的括号表示及层号表示形式。【答】：该树的括号表示为：A（B（E，F（G，H，I）），C，D（J，K），L），该树的层号表示为：10A，20B，30E，30F，40G，40H，40I，20C，20D，25J，25K，20L6.5试写出图6.11所示树的前序遍历、后序遍历和层次遍历的结果。【答】：前序遍历：ABEFGHICDJKL后序遍历：EGHIFBCJKDLA层次遍历：ABCDLEFJKGHI6.6试给出图6.11所示树的双亲表示法和数组方式孩子表示法的表示。www.khdaw.com54 课后答案网www.khdaw.com【答】：双亲表示法：dataparent0A-11B02C03D04E15F16G57H58I5www.khdaw.com9J310K311L0数组方式的孩子表示法：dataChild[0]Child[1]Child[2]Child[3]0A123111B45-1-12C-1-1-1-13D910-1-14E-1-1-1-15F678-16G-1-1-1-17H-1-1-1-18I-1-1-1-19J-1-1-1-110K-1-1-1-111L-1-1-1-16.7已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中有多少个叶子结点？【答】：树中结点总数n=n0+n1+n2+…+nm树中结点的度数之和为n-1，且有：n-1=n1+2n2+3n3+…+mnm所以叶子结点个数为：n0=n2+2n3+…+(m-1)nm6.8假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的前序遍历算法。www.khdaw.com55 课后答案网www.khdaw.com【答】：本程序在运行时请按树的括号表示法输入拟遍历的树，例如，对习题6.4图6.11所示的树为例，应输入A（B（E，F（G，H，I）），C，D（J，K），L）定义树的链式存储结构及建立树的存储结构CreateTree函数（tree.h）内容如下：#include#include#include//树的最大度定义为5#defineMAXN5#defineMAXLEN100typedefchardataType;typedefstructnode{dataTypekey;www.khdaw.comstructnode*child[MAXN];}TreeNode;/*----------------------------------------------------------------*树的括号法转化到树指针方式的孩子表示法*-----------------------------------------------------------------*/TreeNode*CreateTree(TreeNode*root,charstring[MAXLEN]){intlength;inti,j,top;TreeNode*stack[MAXLEN],*temp=NULL,*n;intchildSeq[MAXLEN];//其第几个孩子top=-1;length=strlen(string);for(i=0;ikey=string[i];for(j=0;jchild[j]=NULL;}temp=n;stack[top]->child[childSeq[top]++]=temp;}www.khdaw.comelse{root=(TreeNode*)malloc(sizeof(TreeNode));root->key=string[i];for(j=0;jchild[j]=NULL;}temp=root;}}returnroot;}voidPreOrder(TreeNode*root){inti;if(root!=NULL){printf("%5c",root->key);for(i=0;ichild[i]);}}}树的前序非递归遍历算法及其测试程序（6_8.c）如下所示：#include"tree.h"/*前序遍历（非递归）*/www.khdaw.com57 课后答案网www.khdaw.comvoidPreOrder1(TreeNode*root){TreeNode*stack[MAXLEN];inttop=-1,i;while(root||top!=-1){if(root){printf("%c",root->key);for(i=MAXN-1;i>0;i--)if(root->child[i])stack[++top]=root->child[i];root=root->child[0];}www.khdaw.comelseif(top>-1){root=stack[top--];}}}intmain(){charstring[MAXLEN];TreeNode*root=NULL;printf("请用树的括号表示法输入一棵树:n");scanf("%s",string);root=CreateTree(root,string);PreOrder1(root);return0;}6.9假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的后序遍历算法。【答】：#include"tree.h"intPostOrderByStack(TreeNode*root){TreeNode*temp;TreeNode*stack[MAXLEN];//childSeq表示当前打印到了此树第几个孩子，inttop,childSeq[MAXLEN];inti;top=-1;//初始化空栈www.khdaw.com58 课后答案网www.khdaw.comtemp=root;while(1){while(temp!=NULL){for(i=0;ichild[i]!=NULL){childSeq[++top]=i+1;stack[top]=temp;temp=temp->child[i];break;}www.khdaw.com}//如果此节点是叶子节点，则输出该结点if(i==MAXN){printf("%5c",temp->key);temp=NULL;break;}}while(top!=-1){for(i=childSeq[top];ichild[i]!=NULL){temp=stack[top]->child[i];childSeq[top]=i+1;break;}}if(i==MAXN){printf("%5c",stack[top]->key);top--;}if(temp!=NULL){break;www.khdaw.com59 课后答案网www.khdaw.com}}if(top==-1){return1;}}}intmain(){charstring[MAXLEN];TreeNode*root=NULL;printf("请用树的括号表示法输入一棵树:n");www.khdaw.comscanf("%s",string);root=CreateTree(root,string);PostOrderByStack(root);return0;}6.10假设树采用指针方式的孩子表示法表示，试编写一个函数，判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。#include"tree.h"#defineTRUE1#defineFALSE0/*--------------------------------------------------*递归比较两棵树是否相等*--------------------------------------------------*/intPreCmp(TreeNode*tree1,TreeNode*tree2){inti;if(tree1==NULL&&tree2==NULL){returnTRUE;}elseif(tree1==NULL&&tree2!=NULL||tree1!=NULL&&tree2==NULL){returnFALSE;}else{if(tree1->key!=tree2->key){www.khdaw.com60 课后答案网www.khdaw.comreturnFALSE;}for(i=0;ichild[i],tree2->child[i])==FALSE){returnFALSE;}}returnTRUE;}}www.khdaw.comintmain(){charstring[MAXLEN];TreeNode*tree1=NULL,*tree2=NULL;printf("请用树的括号表示法输入第一棵树:n");scanf("%s",string);tree1=CreateTree(tree1,string);printf("请用树的括号表示法输入第二棵树:n");scanf("%s",string);tree2=CreateTree(tree2,string);if(PreCmp(tree1,tree2)==TRUE){printf("两树相等n");}else{printf("两树不相等n");}return0;}www.khdaw.com61 课后答案网www.khdaw.com第7章二叉树7.1选择题。（1）前序遍历和中序遍历结果相同的二叉树为（F）；前序遍历和后序遍历结果相同的二叉树为（B）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子树的二叉树F．所有结点只有右子树的二叉树。（2）以下有关二叉树的说法正确的是（B）。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任一个结点的度均为2www.khdaw.com（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数为（D）。A．250B．500C．254D．501（4）一棵完全二叉树有999个结点，它的深度为（B）。A．9B．10C．11D．12（5）一棵具有5层的满二叉树所包含的结点个数为（B）。A．15B．31C．63D．327.2用一维数组存放完全二叉树：ABCDEFGHI，则后序遍历该二叉树的结点序列为（HIDEBFGCA）。7.3有n个结点的二叉树，已知叶结点个数为n0，则该树中度为1的结点的个数为k-1（n-2n0+1）；若此树是深度为k的完全二叉树，则n的最小值为（2）。7.4设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B。已知T1、T2和T3的结点数分别是n1、n2和n3，则二叉树B的左子树中有（n1-1）个结点，二叉树B的右子树中有（n2+n3）结点。k7.5高度为k的二叉树的最大结点数为（2-1），最小结点数为（k）。7.6对于一棵具有n个结点的二叉树，该二叉树中所有结点的度数之和为（n-1）。7.7已知一棵二叉树如图7.12所示，试求：（1）该二叉树前序、中序和后序遍历的结果；【答】：前序：abdgecfh；中序：dgbcafhc；后序：gdebhfca（2）该二叉树是否是满二叉树？是否是完全二叉树？【答】：该二叉树不是满二叉树，也不是完全二叉树。（3）将它转换成对应的树或森林；【答】：图7.12一棵二叉树www.khdaw.com62 课后答案网www.khdaw.com（4）这棵二叉树的深度为多少？【答】：该二叉树的深度为4。（5）试对该二叉树进行前序线索化；【答】：www.khdaw.comabc`defgh（6）试对该二叉树进行中序线索化。【答】：7.8试述树和二叉树的主要区别。www.khdaw.com63 课后答案网www.khdaw.com【答】：（1）树的结点个数至少为1，而二叉树的结点个数可以为0。（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2。（3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。7.9试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。【答】：三个结点的树有两种形态：www.khdaw.com三个结点的二叉树具有五种形态：7.10已知一棵二叉树的中序遍历的结果为ABCEFGHD，后序遍历的结果为ABFHGEDC，试画出此二叉树。【答】：7.11已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树。【答】：www.khdaw.com64 课后答案网www.khdaw.com7.12若一棵二叉树的左、右子树均有3个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试画出该二叉树。【答】：7.13分别采用递归和非递归方式编写两个函数，求一棵给定二叉树中叶子结点的个数。www.khdaw.com【答】：为方便测试二叉树相关程序，定义二叉树头文件bintree.h如下：#include#defineN100externchar*a;/*存放扩充二叉树的前序序列*/typedefstructnode/*二叉树结构定义*/{chardata;structnode*lchild,*rchild;}binnode;typedefbinnode*bintree;/*函数creat(根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/voidcreat(bintree*t){charch=*a++;if(ch=="")*t=NULL;else{*t=(bintree)malloc(sizeof(binnode));(*t)->data=ch;creat(&(*t)->lchild);creat(&(*t)->rchild);}}voidpreorder(bintreet)/*前序递归遍历二叉树*/{www.khdaw.com65 课后答案网www.khdaw.comif(t){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}/*顺序栈定义*/typedefstruct{bintreedata[N];inttop;}seqstack;www.khdaw.comvoidinit(seqstack*s)/*初始化空栈*/{s->top=-1;}intempty(seqstack*s)/*判断栈是否为空*/{if(s->top>-1)return0;elsereturn1;}intfull(seqstack*s)/*判断栈是否为满*/{if(s->top==N-1)return1;elsereturn0;}voidpush(seqstack*s,bintreex)/*进栈*/{if(!full(s))s->data[++s->top]=x;}bintreepop(seqstack*s)/*出栈*/{if(!empty(s))returns->data[s->top--];}基于上述结构，递归方法与非递归方法求二叉树中叶子结点的个数的算法分别如leaf1()www.khdaw.com66 课后答案网www.khdaw.com与leaf2()所示：#include"bintree.h"char*a="ABCDEFG";/*扩充二叉树序树t的前序序列*/intleaf1(bintreet)/*递归方法求二叉树叶子结点的个数*/{if(t==NULL)return0;elseif(!t->lchild&&!t->rchild)return1;elsereturnleaf1(t->lchild)+leaf1(t->rchild);}www.khdaw.comintleaf2(bintreet)/*非递归方法求二叉树叶子结点的个数*/{seqstacks;/*顺序栈*/intcount=0;/*叶子结点计数变量*/init(&s);/*初始化空栈*/while(t||!empty(&s)){if(t){if(!t->lchild&&!t->rchild)count++;push(&s,t);t=t->lchild;}else{t=pop(&s);t=t->rchild;}}returncount;}intmain(){bintreet;creat(&t);/*建立二叉树t的存储结构*/printf("n该二叉树一共有%d个叶子结点！n",leaf1(t));printf("n该二叉树一共有%d个叶子结点！n",leaf2(t));}7.14试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。www.khdaw.com67 课后答案网www.khdaw.com【答】：#include"bintree.h"char*a="ABCDEFG";/*扩充二叉树序树t的前序序列*/voidchange(bintreet){bintreep;if(t){p=t->lchild;t->lchild=t->rchild;t->rchild=p;change(t->lchild);change(t->rchild);www.khdaw.com}}intmain(){bintreet;creat(&t);/*建立二叉树t的存储结构*/preorder(t);change(t);printf("n");preorder(t);}7.15试编写一个函数，返回一棵给定二叉树在中序遍历下的最后一个结点。【答】：#include"bintree.h"char*a="ABCDEFG";/*扩充二叉树序树t的前序序列*/bintreeinlast(bintreet){bintreep=t;while(p&&p->rchild)p=p->rchild;returnp;}intmain(){bintreet;creat(&t);/*建立二叉树t的存储结构*/printf("二叉树中序遍历最后一个结点是%cn",inlast(t)->data);}7.16试编写一个函数，返回一棵给定二叉树在前序遍历下的最后一个结点。www.khdaw.com68 课后答案网www.khdaw.com【答】：#include"bintree.h"char*a="ABCDEFG";/*扩充二叉树序树t的前序序列*//*求二叉树前序遍历的最后一个结点*/bintreeprelast(bintreet){bintreep;if(t){p=t;while(p&&p->lchild||p->rchild)if(p->rchild)p=p->rchild;www.khdaw.comelsep=p->lchild;}returnp;}intmain(){bintreet;creat(&t);/*建立二叉树t的存储结构*/printf("二叉树前序遍历的最后一个结点是%cn",prelast(t)->data);}7.17试编写一个函数，返回一棵给定二叉树在后序遍历下的第一个结点。【答】：#include"bintree.h"char*a="ABCDEFG";/*扩充二叉树序树t的前序序列*//*求二叉树后序遍历的第一个结点*/bintreesuccfirst(bintreet){bintreep;if(t){p=t;while(p&&p->lchild||p->rchild)if(p->lchild)p=p->lchild;elsep=p->rchild;}returnp;}www.khdaw.com69 课后答案网www.khdaw.comintmain(){bintreet;creat(&t);/*建立二叉树t的存储结构*/printf("二叉树后序遍历的第一个结点是%cn",succfirst(t)->data);}7.18假设二叉树采用链式方式存储，root为其根结点，p指向二叉树中的任意一个结点，编写一个求从根结点到p所指结点之间路径长度的函数。【答】：在后序遍历非递归算法中，当访问的结点为p时，其祖先点正好全部在栈中，此时栈中结点的个数就是根结点到p所指结点之间路径长度。#include#includetypedefchardatatype;www.khdaw.comtypedefstructnode/*二叉树结点定义*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;typedefstructstack{bintreedata[100];inttag[100];inttop;}seqstack;voidcreat(bintree*t);/*函数Depth，功能：求根结点到x的路径长度*/intDepth(bintreet,datatypex){seqstacks;inti=0,j;s.top=0;while(t||s.top!=0){while(t){s.data[s.top]=t;s.tag[s.top]=0;www.khdaw.com70 课后答案网www.khdaw.coms.top++;t=t->lchild;}while(s.top>0&&s.tag[s.top-1]){s.top--;t=s.data[s.top];if(t->data==x)returns.top;//此时栈中的结点都是x的祖先结点}if(s.top>0){t=s.data[s.top-1];www.khdaw.coms.tag[s.top-1]=1;t=t->rchild;}elset=NULL;}}/*函数creat(根据扩充二叉树的前序序列建立二叉树t的存储结构*/voidcreat(bintree*t){charch;scanf("%c",&ch);if(ch=="")*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));(*t)->data=ch;creat(&(*t)->lchild);creat(&(*t)->rchild);}}intmain(){bintreeroot,p=NULL;datatypex;intk=0;printf("请输入扩充二叉树的前序序列：n");creat(&root);www.khdaw.com71 课后答案网www.khdaw.comprintf("请输入树中的1个结点值：n");scanf("%1s",&x);k=Depth(root,x);printf("根结点到%c的长度是%dn",x,k);}7.19假设二叉树采用链式方式存储，root为其根结点，p和q分别指向二叉树中任意两个结点，编写一个函数，返回p和q最近的共同祖先。【答】：方法同上题，利用后序遍历非递归算法分别求出p和q的公共祖先，然后再查找它们的最近公共祖先结点。#include#includewww.khdaw.comtypedefchardatatype;typedefstructnode/*二叉树结点定义*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;typedefstructstack//顺序栈结构定义{bintreedata[100];inttag[100];inttop;}seqstack;voidcreat(bintree*t);//创建二叉树结构函数声明/*函数SeekAncestor的功能是返回二叉树t中结点x与结点y的最近公共祖先结点*/voidSeekAncestor(bintreet,datatypex,datatypey,bintree*antor){seqstacks;bintreedata[100]={0};inti=0,j;s.top=-1;while(t||s.top>-1){while(t){s.data[++s.top]=t;s.tag[s.top]=0;t=t->lchild;}www.khdaw.com72 课后答案网www.khdaw.comwhile(s.top>-1&&s.tag[s.top]){t=s.data[s.top];if(t->data==x)while(i<=s.top)//记录x结点的所有祖先结点{data[i]=s.data[i];i++;}elseif(t->data==y){while(s.top>-1)www.khdaw.com{j=i-1;while(j>=0&&t!=data[j])//查找y与x的最近公共祖先结点j--;if(j>=0){*antor=data[j];//返回公共祖先结点地址return;}t=s.data[--s.top];}}--s.top;}if(s.top>-1){t=s.data[s.top];s.tag[s.top]=1;t=t->rchild;}elset=NULL;}}/*函数creat(根据扩充二叉树的前序序列建立二叉树t的存储结构*/voidcreat(bintree*t){charch;www.khdaw.com73 课后答案网www.khdaw.comscanf("%c",&ch);if(ch=="")*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));(*t)->data=ch;creat(&(*t)->lchild);creat(&(*t)->rchild);}}intmain(){www.khdaw.combintreeroot,p=NULL;datatypex="B",y="C";printf("请输入扩充二叉树的前序序列：n");creat(&root);printf("请输入树中的两个结点值：n");scanf("%1s%c",&x,&y);SeekAncestor(root,x,y,&p);if(p)printf("%c和%c的最近公共祖先是：%cn",x,y,p->data);}www.khdaw.com74 课后答案网www.khdaw.com第8章图8.1选择题（1）如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（D）。A．有向完全图B．连通图C．强连通图D．有向无环图（2）若邻接表中有奇数个表结点，则一定（D）。A．图中有奇数个顶点B．图中有偶数个顶点C．图为无向图D．图为有向图（3）下列关于无向连通图特性的叙述中，正确的是（A）。Ⅰ．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1www.khdaw.comⅢ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ（4）假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（B）。A．O(n)B．O(e)C．O(n+e)D．O(n*e)（5）已知一个有向图8.30所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为（A）。A．adbefcB．adcefbC．adcbfeD．adefcbbacefd图8.30有向图（6）无向图G=（V，E），其中：V={a,b,c,d,e,f}，E={（a,b），（a,e），（a,c），（b,e），（c,f），（f,d），（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（D）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b（7）下列哪一个选项不是图8.31所示有向图的拓扑排序结果（C）。A．AFBCDEB．FABCDEC．FACBDED．FADBCE图8.31AOV网www.khdaw.com75 课后答案网www.khdaw.com（8）判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（D）。A．单源最短路Dijkstra算法B．所有顶点对最短路Floyd算法C．广度优先遍历算法D．深度优先遍历算法（9）在一个带权连通图G中，权值最小的边一定包含在G的（A）。A．最小生成树中B．深度优先生成树中C．广度优先生成树中D．深度优先生成森林中（10）下图所示带权无向图的最小生成树的权为（C）。A．14B．15C．17D．18www.khdaw.com图8.32带权无向图8.2对于如图8.33所示的无向图，试给出：（1）图中每个顶点的度；（2）该图的邻接矩阵；（3）该图的邻接表与邻接多重表；（4）该图的连通分量。图8.33无向图图8.34有向图【答】：（1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=2；D（V6）=1。（2）该图的邻接矩阵如图8.33.1所示。www.khdaw.com76 课后答案网www.khdaw.com图8.33.1邻接矩阵图8.33.2邻接表（3）该图的邻接表如图8.30.2所示；该图的邻接多重表如图8.30.3所示。www.khdaw.com图8.33.3邻接多重表（4）该图的两个连通分量如图8.33.4所示。图8.33.4两个连通分量8.3对于如图8.34所示的有向图，试给出：（1）顶点D的入度与出度；（2）该图的出边表与入边表；（3）该图的强连通分量。【答】：（1）顶点D的入度是2；顶点D的出度为1。（2）该图的出边表如图8.34.1所示，该图的入边表如图8.34.2所示。www.khdaw.com77 课后答案网www.khdaw.com图8.34.1出边表图8.34.2入边表（3）该图的两个强连通分量如图8.34.3所示。ACEDwww.khdaw.comB图8.34.3两个强连通分量8.4试回答下列关于图的一些问题。（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？（2）表示一个有500个顶点，500条边的有向图的邻接矩阵有多少个非零元素？（3）G是一个非连通的无向图，共有28条边，则该图至少有多少个顶点？【答】：（1）有n个顶点的有向强连通图昨多有n(n-1)条边；最少有n-1条边。（2）500个。（3）9个顶点。8.5图8.35所示的是某个无向图的邻接表，试：（1）画出此图；（2）写出从顶点A开始的DFS遍历结果；（3）写出从顶点A开始的BFS遍历结果。【答】：图8.35题8.5的邻接表（1）图8.35邻接表对应的无向图如图8.35.1所示。图8.35.1（2）从顶点A开始的DFS遍历结果是：A，B，C，F，E，G，D（3）从顶点A开始的BFS遍历结果是：A，B，C，D，F，E，G8.6证明，用Prim算法能正确地生成一棵最小生成树。【证明】：www.khdaw.com78 课后答案网www.khdaw.comPrim算法是按照逐边加入的方法来构造最小生成树过程的。记构造过程中生成的子图为G’，显然G’始终是一棵树。这是因为初始时V(G’)={u0}，E（G’）=Ф，是一棵树。随后每一步都是向G’中添加一个顶点同时添加一条边，始终保持G’中所有顶点连通。这样，当G’有n个顶点时是仅有n-1条边的连通图，所以G’是一棵树。Prim算法在执行过程中，始终能保证G’=（V’，E’）是无向连通网络G=（V，E）上某个最小代价生成树的连通图，如果该结论正确，则随着V(G’)顶点不断增加，当V(G’)=V(G)时，G’=(V’,E’)就是G=(V,E)上的最小代价生成树。下面证明Prim算法的每一步都能保证G’=(V’,E’)是无向连通网络G=(V,E)上某个代价生成树的子连通图。初始时，G’仅有一个顶点V（G’）={u0}，E（G’）=Ф，设该树为T1，此时G’显然是G的某个最小生成树的子连通图。现假设第i步G’=(V’,E’)中含有i个顶点，不妨设该树为Ti，在G（V，E）中存在一棵最小生成树包含着Ti，在第i+1步，存在uT∈i，v∉Ti,且(u,v)是最www.khdaw.com小两栖边，将顶点{v}，边（u,v）添加到树Ti中，所得树Ti+1是包含V（Ti）+{v}顶点集的生成树，且具有i+1个顶点。根据MST性质，此时在G=(V,E)中必存在一棵最小生成树包含着Ti+1。由此可知，当i=n时，G’(Tn)即为无向图G含有n个顶点的最小生成树。当然在进行最小两栖边选择时，如果同时存在几个具有相同代价的最小两栖边，则可任选一条，因些Prim算法构造的最小生成树不是唯一的。但它们的最小（代价）总和是相等的。8.7证明，用Kruskal算法能正确地生成一棵最小生成树。【证明】：算法首先构造具有n个不同顶点的n个连通分量，然后在E（G）中选择边(u,v)，若u,v顶点属于不同的两个连通分量，则把该边添加到树T中，每添加一条边就减少一个连通分量。当添加了共n-1条边时，就把n个连通分量变成一个连通分量，此时T就是具有n个顶点n-1条边的树。由于n是有限数，E（G）中边数也是有限的，所以算法具有有穷性。不妨设T的边为（u1,v1）,(u2,v2)，…，(un-1,vn-1)，按权值从小到大排列，若存在一棵树T’的代价总和小于T的代价总和，则必在T’中存在一条边（u’,v’）∈TE’，（u’,v’）∉TE，且(u’,v’)的代价小于(un-1,vn-1)的代价，这就说明(u’,v’)边没有选取的原因是因为u’,v’在同一个连通分量，添加（u’,v’）将产生回路，说明T’不可能是树（添加一条边没有减少一个连通分量，这样T’的边数将大于n-1）。这与T’是一棵树的假设相矛盾。证毕。8.8对如图8.36所示的连通图，分别用Prim和Kruskal算法构造其最小生成树。【答】：（1）采用Prim算法求解最小生成树的过程如图8.36.1图8.36无向连通网所示。www.khdaw.com79 课后答案网www.khdaw.comAB34CD4E12F4G（a）选取（A，F）（b）选取（D,F）（c）选取（C,F）AB344CDE124www.khdaw.comFG（d）选取（F,G）（e）选取（D,E）（f）选取（D,B）图8.36.1Prim算法求解最小生成树过程（2）采用Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）5、（E,G）5、（A,D）6、（D,G）6、（A,B）7。根据Kruskal算法，构造最小生成树的过程如图8.33.2所示。（a）选取（D，F）（b）选取（C,F）（c）选取（A,F）ABAB33444CDECDE112244FGFG（d）选取（F,G）（e）选取（D,E）（f）选取（D,B）图8.36.2Kruskal算法求解最小生成树过程www.khdaw.com80 课后答案网www.khdaw.com8.9对于如图8.37所示的有向网，用Dijkstra方法求从顶点A到图中其他顶点的最短路径，并写出执行算法过程中距离向量d与路径向量p的状态变化情况。B12B4813A28E33CFAGH9C151843D403323DFIG20E图8.37有向网图8.38题8.10的AOV网【答】：对于如图8.37所示的有向网，Dijkstra方法求从顶点A到图中其它顶点的最短径时，www.khdaw.com距离向量与路径向量的状态变化如下表示：距离向量d路径向量p循环集合Sv01234560123456初始化{A}-048∞1528∞40-10-100-101{AD}3048∞15284838-10-100332{ADE}40486115284838-10400333{ADG}60486115284838-10400334{ADGB}10486015284838-10100335{ADGBF}50485715284838-10500336{ADGBFC}20485715284838-1050033从表中可以看出源点A到其它各顶点的最短距离及路径为：A→B：48路径：A→BA→C：57路径：A→D→F→CA→D：15路径：A→DA→E：28路径：A→EA→F：48路径：A→D→FA→G：38路径：A→D→G8.10试写出如图8.38所示的AOV网的4个不同的拓扑序列。【答】：图8.38所示的AOV网的4个不同的拓扑序列为：（1）ABDCEFGIH（2）ABDECFGIH（3）DABCEFGIH（4）DAECBFGIH8.11计算如图8.39所示的AOE网中各顶点所表示的事件的发生时间ve(j)，vl(j)，各边所表示的活动的开始时间e(i)，l(i)，并找出其关键路径。www.khdaw.com81 课后答案网www.khdaw.com【答】：为描述方便，将AOE网中的所有边事件记为a0-a7，如图8.39所示。按照关键路径算法，求得各顶事件的最早与最晚开始时间如下表所示。v1v4679aa2a50a7v0v33a18a10a64v3202v5a4图8.39题8.10的AOE网顶点vevl活动ell-e关键活动v000a0000√www.khdaw.comv166a1011v245a2660√v31313a3451v42222a4451v52525a513130√a613152a722220√可见，该AOE网的关键路径是a0,a2,a5,a7。（注：图中箭头指示求解的顺序）8.12无向图采用邻接表作为存储结构，试写出以下算法（1）求一个顶点的度；（2）往图中插入一个顶点；（3）往图中插入一条边；（4）删去图中某顶点；（5）删去图中某条边。【答】：本题的参考解答基于以下的存储结构：#definem20/*预定义图的最大顶点数*/typedefchardatatype;/*顶点信息数据类型*/typedefstructnode{/*边表结点*/intadjvex;/*邻接点*/structnode*next;}edgenode;typedefstructvnode{/*头结点类型*/datatypevertex;/*顶点信息*/edgenode*firstedge;/*邻接链表头指针*/}vertexnode;www.khdaw.com82 课后答案网www.khdaw.comtypedefstruct{/*邻接表类型*/vertexnodeadjlist[m];/*存放头结点的顺序表*/intn,e;/*图的顶点数与边数*/}adjgraph;（1）求一个顶点的度；/*求无向图g的第i个顶点的度*/intd(adjgraphg,inti){intk=0;edgenode*p;p=g.adjlist[i].firstedge;while(p){k++;www.khdaw.comp=p->next;}returnk;}（2）往图中插入一个顶点；voidinsertvex(adjgraph*g,datatypex){inti=0,flag=0;/*查找待插入的结点是否存在*/while(!flag&&in){if(g->adjlist[i].vertex==x)flag=1;i++;}if(flag){printf("结点已存在!");getch();exit(0);}if(g->n>m){printf("邻接表已满！");exit(0);}g->adjlist[g->n].vertex=x;g->adjlist[g->n].firstedge=NULL;g->n++;}（3）往图中插入一条边；/*在无向图g中插入无向边（i,j）*/voidinsertedge(adjgraph*g,inti,intj){edgenode*p,*s;www.khdaw.com83 课后答案网www.khdaw.comintflag=0;if(in&&jn){p=g->adjlist[i].firstedge;while(!flag&&p){if(p->adjvex==j)flag=1;p=p->next;}if(flag){printf("边已存在!");getch();exit(0);}/*插入无向边(i,j)*/www.khdaw.coms=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;/*邻接点序号为j*/s->next=g->adjlist[i].firstedge;g->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;/*邻接点序号为i*/s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;/*将新结点*s插入顶点vj的边表头部*/}elseprintf("插入边不合法!");}（4）删去图中某顶点；/*下面的函数删除无向图中顶点编号为i的顶点。由于该顶点被删除，与这个顶点相关联的边也应该被删除，具体做法是，通过邻接表查找与顶点i邻接的其它所有顶点，在这些顶点的邻接边链表中删除编号为i的边结点，再将邻接表中最后一个顶点移动到第i个顶点在邻接表中的位置，相应地修改最后一个顶点在邻接表中的顶点编号为i*/voiddeletevex(adjgraph*g,inti){intk;edgenode*pre,*p,*s;if(i>=0&&in)/*顶点下标合法*/{/*删除与原顶点i有关的所有边*/s=g->adjlist[i].firstedge;while(s){k=s->adjvex;pre=NULL;www.khdaw.com84 课后答案网www.khdaw.comp=g->adjlist[k].firstedge;while(p){if(p->adjvex==i)/*结点编号是i,应该删除*/if(!pre)/*边链表的第一个边结点*/{g->adjlist[k].firstedge=p->next;free(p);p=g->adjlist[k].firstedge;}else/*不是第一个边结点*/{pre->next=p->next;free(p);p=pre->next;www.khdaw.com}else/*结点编号不是i*/{pre=p;p=p->next;}}g->adjlist[i].firstedge=s->next;free(s);/*释放顶点i边链表上的结点*/s=g->adjlist[i].firstedge;}g->adjlist[i]=g->adjlist[g->n-1];/*将最后一个结点换到第i个结点的位置*/p=g->adjlist[i].firstedge;/*由于第n-1个结点的编号被改为i，所以调整所有与这个结点关联的边信息*/while(p){k=p->adjvex;s=g->adjlist[k].firstedge;while(s){if(s->adjvex==g->n-1)/*将最后一个结点的编号改为i*/s->adjvex=i;s=s->next;}p=p->next;}g->n--;/*结点个数减1*/}elseprintf("不存在指定的结点!n");www.khdaw.com85 课后答案网www.khdaw.com}（5）删去图中某条边。voiddeleteedge(adjgraph*g,inti,intj){edgenode*pre,*p;intk;if(i>=0&&in&&j>=0&&jn)/*判断边是否有效*/{pre=NULL;/*找无向边(i,j)并删除*/p=g->adjlist[i].firstedge;while(p&&p->adjvex!=j){pre=p;p=p->next;}www.khdaw.comif(p)/*找到了被删除边结点*/{if(!pre)/*是第一个边结点*/g->adjlist[i].firstedge=p->next;elsepre->next=p->next;free(p);pre=NULL;/*找无向边(j,i)并删除*/p=g->adjlist[j].firstedge;while(p&&p->adjvex!=i){pre=p;p=p->next;}if(!pre)g->adjlist[j].firstedge=p->next;elsepre->next=p->next;free(p);g->e--;/*边的个数减1*/}else{printf("找不到指定的边!");getch();exit(0);}}else{printf("边不合法!n");exit(0);www.khdaw.com86 课后答案网www.khdaw.com}}8.13设有向图采用邻接表的存储结构（出边表），试写出求图中一个顶点的入度的算法。【答】：/*求有向图g中顶点i的入度，g的存储结构为出边表，结构定义同题8.11*/intid(adjgraph*g,inti){intj,count=0;edgenode*p;for(j=0;jn;j++){p=g->adjlist[j].firstedge;while(p){if(p->adjvex==i)count++;www.khdaw.comp=p->next;}}returncount;}8.14设计一个算法，不利用拓扑排序判断有向图中是否存在环。【答】：对于有向图进行深度优先遍历，如果从有向图上某个顶点v出发的遍历，dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v到顶点u的环。因此判断有一个有向图中是否有环可以借助图的深度优先遍历算法。intvisited[m];voiddfs(adjgraphg,inti){edgenode*p;visited[i]=1;p=g.adjlist[i].firstedge;while(p){if(!visited[p->adjvex])dfs(g,p->adjvex);else/*深度优先遍历到已访问的结点，出现环*/{printf("foundacircle!");getch();exit(0);}p=p->next;}}voidfindcircle(adjgraphg){inti;www.khdaw.com87 课后答案网www.khdaw.comfor(i=0;i-1||p)/*当栈不空或p不空时*/{if(p)/*优先处理p不空的情况*/if(visited[p->adjvex])p=p->next;else{printf("%c",g.adjlist[p->adjvex].vertex);visited[p->adjvex]=1;stack[++top]=p;p=g.adjlist[p->adjvex].firstedge;}else/*从栈中进行回溯*/if(top>-1){p=stack[top--];p=p->next;}}}voiddfstraverse(adjgraphg){inti;www.khdaw.com88 课后答案网www.khdaw.comfor(i=0;in;i++)/*对出边表中的每一条边进行求解*/{p=gout->adjlist[i].firstedge;while(p){active[k].vi=i;/*边的起点*/active[k].vj=p->adjvex;/*边的终点*/active[k].e=ve[i];k++;p=p->next;}}}/*求AOE网中各活动的最晚允许开始时间*/voidl(aoegraph*gout,intvl[],edgeactive[]){inti,k=0;edgenode*p;for(i=0;in;i++){p=gout->adjlist[i].firstedge;www.khdaw.com89 课后答案网www.khdaw.comwhile(p){active[k].l=vl[p->adjvex]-p->len;p=p->next;k++;}}}www.khdaw.comwww.khdaw.com90 课后答案网www.khdaw.com第9章检索9.1选择题（1）在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（B）。A．4，4，3B．4，3，3C．3，4，4D．3，3，4（2）适用于折半查找的表的存储方式及元素排列要求为（D）。A．链式方式存储，元素无序B．链式方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序（3）设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查www.khdaw.com找成功时的平均查找长度为（B）。A．21B．23C．41D．62（4）已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（B）。A．1.0B．2.9C．3.4D．5.5（5）在图9.27所示的各棵二叉树中，二叉排序树是（C）。图9.27题（5）图（6）由同一关键字集合构造的各棵二叉排序树（B）。A．其形态不一定相同，但平均查找长度相同B．其形态不一定相同，平均查找长度也不一定相同C．其形态均相同，但平均查找长度不一定相同D．其形态均相同，平均查找长度也都相同（7）有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（A）的序列输入。A．37,24,12,30,53,45,96B．45,24,53,12,37,96,30C．12,24,30,37,45,53,96D．30,24,12,37,45,96,53（8）若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（C）。www.khdaw.com91 课后答案网www.khdaw.comA．4B．5C．8D．9（9）对于哈希函数H(key)=key%13，被称为同义词的关键字是（D）。A．35和41B．23和39C．15和44D．25和51（10）下列叙述中，不符合m阶B树定义要求的是（D）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接9.2在分块检索中，对256个元素的线性表分成多少块最好？每块的最佳长度是多少？若每块的长度为8，其平均检索的长度是多少？【答】：对256个元素的线性表分成16块，每块的最佳长度是17；若每块的长度为8，当采用顺序检索方法确定所在的块时平均检索长度是21，当采用二分检索方法确定所在的块时平www.khdaw.com均检索长度是9。9.3设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。【答】：共可能组成14种不同形态的二叉排序树。其中高度较小的6种如图9.28（a）所示。其它8种分别是高度为4的二叉排序树如图9.28(b)所示。（a）4个结点组成的高度较小的6棵二叉排序树（b）4个结点组成的高度为4的二叉排序树图9.284个结点输入序列构成的不同二叉排序树9.4已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出由该输入序列构成的二叉排序树，并分别给出下列操作后的二叉排序树。（1）插入数据9；（2）删除结点17；（3）再删除结点13【答】：该序列的二叉排序树如图9.29（a）所示，插入数据9后的二叉排序树如图9.29（b）所示，删除结点17后的二叉排序树如图9.29（c）所示，再删除结点13后的二叉排序树如图9.29（d）所示。www.khdaw.com92 课后答案网www.khdaw.com（a）二叉排序树（b）插入9之后的二叉排序树www.khdaw.com（c）删除17之后的二叉排序树（d）删除13之后的二叉排序树图9.29二叉树结点插入与删除操作示例9.5试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。【答】：判定二叉树是否为二叉排序树可以建立在二叉树中序遍历的基础上，在遍历中附设一指针pre指向树中当前访问结点的中序直接前驱，每访问一个结点就比较前驱结点pre和此结点是否有序；若遍历结束后各结点和其中序直接前驱均满足有序，则此二叉树即为二叉排序树，否则不是二叉排序树。二叉树存储结构定义为：typedefintdatatype;typedefstructnode/*二叉树结点定义*/{datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;函数bisorttree()用于判断二叉树t是否为二叉排序树，初始时pre=NULL；flag=1；结束时若flag==1，则此二叉树为二叉排序树，否则此二叉树不是二叉排序树。voidbisorttree(bintreet,bintree*pre,int*flag){if(t&&*flag==1){bisorttree(t->lchild,pre,flag);/*判断左子树*/if(pre==NULL)/*访问中序序列的第一个结点时不需要比较*/www.khdaw.com93 课后答案网www.khdaw.com{*flag=1;*pre=t;}else/*比较t与中序直接前驱pre的大小（假定无相同关键字）*/{if((*pre)->datadata){*flag=1;*pre=t;}else/*pre与t无序*/*flag=0;}bisorttree(t->rchild,pre,flag);/*判断右子树*/www.khdaw.com}}9.6设T是一棵给定的查找树，试编写一个在树T中删除根结点值为a的子树的程序。要求在删除的过程中释放该子树中所有结点所占用的存储空间。这里假设树T中的结点采用二叉链表存储结构。【答】：删除二叉树可以采用后序遍历方法，先删除左子树，再删除右子树，最后删除根结点。本题先在指定的树中查找值为a的结点，找到后删除该棵子树。相关函数实现如下（二叉排序树的结构定义同题9.5）/*删除以t为根的二叉树*/voiddeletetree(bintree*t){if(*t){deletetree(&(*t)->lchild);/*递归删除左子树*/deletetree(&(*t)->rchild);/*递归删除右子树*/free(*t);/*删除根结点*/}}/*删除二叉树中以根结点值为a的子树*/voiddeletea(bintree*t,datatypea){bintreepre=NULL,p=*t;while(p&&p->data!=a)/*查找值为a的结点*/{pre=p;p=(adata)?p->lchild:p->rchild;}if(!pre)*t=NULL;/*树根*/else/*非树根*/if(pre->lchild==p)pre->lchild=NULL;elsepre->rchild=NULL;www.khdaw.com94 课后答案网www.khdaw.comdeletetree(&p);/*删除以p为根的子树*/}9.7含有12个节点的平衡二叉树的最大深度是多少（设根结点深度为0），并画出一棵这样的树。【答】：含有12个节点的平衡二叉树的最大深度是4（设根结点深度为0），如果根结点的深度为1则本题的答案为5，该树如图9.30所示。www.khdaw.com图9.30具有12个结点的深度为4的平衡二叉树9.8试用Adelson插入方法依次把结点值为60，40，30，150，130，50，90，80，96，25的记录插入到初始为空的平衡二叉排序树中，使得在每次插入后保持该树仍然是平衡查找树。请依次画出每次插入后所形成的平衡查找树。【答】：由结点序列构成的平衡二叉排序树如图9.31所示。0-101260606040401000-104040306030600030150（a）空树（b）插入60（c）插入40（d）插入30（e）LL型调整（f）插入150-1-1-20404040600-200010-1306030130301304013010010000150601506015030501500130050（g）插入130（h）RL型调整（i）插入50（j）RL型调整www.khdaw.com95 课后答案网www.khdaw.com（k）插入90（l）插入80（m）插入96（n）插入25图9.31AVL树的插入过程9.9结点关键字k1，k2，k3，k4，k5为一个有序序列，它们的相对使用频率分别为p1=6，p2=8，p3=12，p4=2，p5=16，外部结点的相对使用频率分别为q0=4，q1=9，q2=8，q3=12，q4=3，q5=2。试构造出有序序列k1，k2，k3，k4，k5所组成的最优查找树。www.khdaw.com【答】：（略）9.10证明Huffman算法能正确地生成一棵具有最小带权外部路枝长度的二叉树。【答】：哈夫曼提出了一种构造最优前缀编码的贪心算法，由此产生的编码方案称为哈夫曼算法。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以C个叶结点开始，执行C-1次的“合并”运算后产生最终所要求的树T。要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。（1）贪心选择性质设C是编码字符集，C中字符c的频率为f（c）。又设x和y是C中具有最小频率的两个字符，则存在C的一个最优前缀编码使x和y具有相同码长且仅最后一们编码不同。证明：设二叉树T表示C的任意一个最优前缀码。我们要证明可以对T作适当修改后得到一棵新的二叉树T""，使得在新树中，x和y是最深中子且为兄弟。同时新树T""表示的前缀码也是CS的一个最优前缀码。如果我们能做到这一点，则x和y在T""表示的最优前缀码中就具有相同的码长且仅最后一位编码不同。设b和c是二叉树T的最深叶子且为兄弟。不失一般性，可设f（b）≤f（c）,f（x）≤f（y）。由于x和y是C中具有最小频率的两个字符，故f（x）≤f（b），f（y）≤f（c）。首先在树T中交换叶子b和x位置得到树T"，然后在树T""再交换叶子c和y的位置，得到树T""。如下图所示。图编码树T的变换由此可知，树T和T"表示的前缀码的平均码长之差为www.khdaw.com96 课后答案网www.khdaw.comB（T）-B（T"）=∑f(c)dT(c)-∑f(c)dT"(c)c∈CSc∈CS=f(x)d(x)+f(b)d(b)−f(x)d(x)−f(b)d(b)TTT"T"=f(x)d(x)+f(b)d(b)−f(x)d(b)−f(b)d(x)TTTT=(f(b)−f(x))(d(b)−d(x))≥0TT最后一个不等式是因为f（b）-f（x）和dT（b）-dT（x）均为非负。类似地，可以证明在T"中交换y与c的位置也不增加平均码长，即B（T"）-B（T""）也是非负的。由此可知B（T""）≤B（T"）≤B（T）。另一方面，由于T所表示的前缀码是最优的，故B（T）≤B（T""）。因此，B（T）=B（T""），即T""表示的前缀码也是最优前缀码，且xwww.khdaw.com和y具有最长的码长，同时仅最后一位编码不同。（2）最优子结构性质设T是表示字符集C的一个最优前缀码的二叉树。C中字符c的出现频率为f（c）。设x和y是树T中的两个叶子且为兄弟，z是它们的双亲。若将z看作是具有频率f（z）=f（x）+f（y）的字符，则树T"=T-{x，y}表示字符集C"=C-{x,y}∪{z}的确一个最优前缀码。证明：我们首先证明T的平均码长B（T）可用T"的平均码长B（T"）来表示。事实上，对任意c∈C-{x，y}有，dT(c)=dT"（c），故有f（c）dT（c）=f（c）dT"（c）。另一方面，dT（x）=dT（y）=dT"（z）+1，故f（x）dT（x）+f（y）dT（y）=（f（x）+f（y））(dT"（z）+1)=f（x）+f（y）+f（z）dT"（z）由此即知，B（T）=B（T"）+f（x）+f（y）。由T"所表示的字符集C"的前缀码不是最优的，则有T""表示的C"的前缀码使得B（T""）16,将low=mid+1;12345678516182732465126low,high26>16，将low=mid+1;12345678516182732465126highlow此时，highlength;done=1;while(done){done=0;for(k=i;k<=j;k++)if(L->r[k+1].keyr[k].key){L->r[0]=L->r[k];L->r[k]=L->r[k+1];L->r[k+1]=L->r[0];www.khdaw.comdone=1;}j--;done=0;for(k=j;k>=i;k--)if(L->r[k].keyr[k-1].key){L->r[0]=L->r[k];L->r[k]=L->r[k-1];L->r[k-1]=L->r[0];done=1;}i++;}}intmain(){tableL;/*定义表L*/input(&L,"in.txt");/*从文件in.txt中读入排序数据*/print(L);/*输出原表*/bubblesort(&L);print(L);/*输出排序后的表*/}10.5对习题10.2中给出的初始数列，给出堆排序中建堆过程示意图。10.6［计数排序］一个记录在已排序的文件中的位置，可由此文件中比该记录排序码小的记录的个数而定，由此得到一个简单的排序方法，对于每一个记录，增加一个count字段确www.khdaw.com105 课后答案网www.khdaw.com定在已排序的文件中位于该记录之前的记录的个数，写一个算法，确定一个无序文件中的每个记录的count的值，并证明若文件有n个记录，则至多进行n(n−1)/2次排序码比较，即可确定所有记录的count值。10.7设计一个算法，重新排列一组整数位置，使所有负值的整数位于正值的整数之前（不要对这一组整数进行排序，要求尽量减少算法中的交换次数）。10.8对本章中的各种排序算法，说明哪些是稳定的？哪些是不稳定的？对不稳定的排序算法举例说明。10.9总结本章中各种排序算法的特点，分析比较各算法的时间、空间复杂度及附加存储空间情况。10.10一油田欲建设一条连接油田内n口油井的主输油管道，管道由东向西，从每一口油井都有一条支输油管道和主输油管道相连。如果知道每口油井的具体位置，应该如何确定主输油管道的建设位置，使得所有支输油管道的长度之和最小。www.khdaw.com10.11某大学一、二、三年级的学生报名参加一知识竞赛，报名信息包括年级和姓名，已知这3个年级都有学生报名，报名信息中的年级用1、2、3表示，设计一个算法对所有报名参赛学生按年级排序，要求排序算法的时间复杂度是线性的。www.khdaw.com106'