完整版数据结构-C语言描述习题及答案耿国华

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华第1章绪论习题一、问答题1,什么是数据结构？2.四类基本数据结构的名称与含义。3,算法的定义与特性。4,算法的时间复杂度.5,数据类型的概念.6,线性结构与非线性结构的差别.7,面向对象程序设计语言的特点。8,在面向对象程序设计中，类的作用是什么？9,参数传递的主要方式及特点。10.抽象数据类型的概念。二、判断题1,线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2,算法就是程序。3,在高级语言(如外或PASCAL)中，指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=1;i〈二n;i++)for(j=1；j〈=i;j++)for(k=1;k〈二j；k++)x=x+1;[提示]:i=1时：1=(1+1)X1/2=(1+12)/2i=2时：1+2=(1+2)X2/2=(2+22)/2i=3时：1+2+3=(1+3)X3/2=(3+32)/2…i=n时：1+2+3+ +n=(1+n)Xn/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(12+22+32+……+n2)]/2二[(1+n)n/2+n(n+1)(2n+1)/6]/2=n(n+1)(n+2)/6=n3/6+m/2+n/3(完整桢网版)《数据结构——0语言描述》习题及答案耿国华区分语句频度和算法复杂度:O(f(n))=O(n3)四、试编写算法求一元多项式Pn(x)=ao+a1x+a2x2+a3x3+…anxn的值Pn(x。)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求赛函数。注意：本题中的输入aJi=0,1,…，n),x和囚输出为匕(%).通常算法的输入和输出可采用下列两种方式之一：(1)通过参数表中的参数显式传递；(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]:floatPolyValue(floata[],floatx,intn){ }核心语句：p=1;(x的零次赛)s=0；i从0到n循环s=s+a[i]*p;p=p*x;或：：p=x;(x的一次赛)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案1.3计算下列程序中x=x+1的语句频度for(i=1；i〈二n;i++)for(j=1；j<=i;j++)for(k=1;k〈=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+(1+2+3)+ + (1+2+ +n)=n (n+1)(n+2)/6(完整桢网版)《数据结构——0语言描述》习题及答案耿国华1。4试编写算法，求p(x)=a+ax+ax2+…….+axn的值p(x),并确定算法中每一语句的执行次数和整个算n 0 1 2 n n0法的时间复杂度，要求时间复杂度尽可能小 ，规定算法中不能使用求赛函数。注意：本题中的输入为aji=0,1，…n)、x和％输出为Pn(x0)。算法的输入和输出采用下列方法(1)通过参数表中的参数显式传递(2)通过全局变量隐式传递.讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】(1)通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(){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]); /*执行次数：n次*/p=a[0];for(i=1;i<=n;i++){p=p+a[i]*x; /*执行次数：门次大/x=x*x;}printf(“％f",p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn){floatp,s;inti;p=x;s=a[0];for(i=1;i〈二n;i++)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华{s=s+a[i]*p; /*执行次数：门次大/p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n)第2章线性表习题描述以下三个概念的区别：头指针，头结点，首元素结点.填空：在顺序表中插入或删除一个元素，需要平均移动一半元素,具体移动的元素个数与 插入或删除的位置有关。在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻.在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示.已知L是无表头结点的单链表，且「结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列.a.在「结点后插入5结点的语句序列是：(4)、(1)。b。在P结点前插入S结点的语句序列是：(7)、(11)、(8)、(4)、(1)。c。在表首插入5结点的语句序列是：(5)、(12)。do在表尾插入S结点的语句序列是：(11)、(9)、(1)、(6)。供选择的语句有：(1)P->next=S;P->next=P-〉next->next;P一〉next=S一>next;S一〉next=P-〉next;S一〉next二L;S—>next=NULL;Q=P;while(P-〉next!=Q)P=P—〉next;while(P->next!二NULL)P=P-〉next;P=Q;(完整桢网版)《数据结构——0语言描述》习题及答案耿国华P二L；(12)L二S；(13)L二P；已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。［提示］:voidinsert(SeqList*L;ElemTypex)〈方法1〉(1)找出应插入位置h(2)移位，(3)……〈方法2〉参P。229写一算法，从顺序表中删除自第i个元素开始的k个元素。［提示］:注意检查i和k的合法性。 (集体搬迁，“新房”、“旧房”)〈方法1〉以待移动元素下标m(“旧房号”)为中心，计算应移入位置(“新房号”)：for(m=i—1+k;m〈二L—〉last; m++)L—>elem［m—k］=L—>elem［m］;<方法2>同时以待移动元素下标m和应移入位置j为中心：<方法3〉以应移入位置)为中心，计算待移动元素下标：2.6已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构.试写一高效算法，删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：mink和maxk是给定的两个参变量，它们的值为任意的整数).［提示］:注意检查mink和maxk的合法性：mink〈maxk不要一个一个的删除(多次修改next域).(1)找到第一个应删结点的前驱prepre二L; p二L一〉next;while(p!=NULL&&p—>data〈二mink){pre=p; p=p—>next; }⑵找到最后一个应删结点的后继s,边找边释放应删结点s=p；while(s!=NULL&&s—>data<maxk){t=s; s=s—>next;free(t); }(3)pre—〉next=s;2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表(a1,a2...,an)逆置为&,a-1,。。。,a1).(1)以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（完整桢网版）《数据结构——0语言描述》习题及答案耿国华(2)以单链表作存储结构。［方法1］:在原头结点后重新头插一遍［方法2］:可设三个同步移动的指针p,q,r,将q的后继r改为p2。8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表工并要求利用原表(即A表和B表的)结点空间存放表C.［提示］:参P.28例2-1〈方法1〉voidmerge(LinkListA;LinkListB;LinkList*C){……pa二A—〉next; pb=B—〉next;*C=A; (*C)—〉next=NULL;while(pa!=NULL&&pb!=NULL){if(pa-〉data<=pb—〉data){smaller=pa; pa=pa—>next;smaller—>next=(*C)—〉next; /*头插法*/(*C)—〉next二smaller;)else{smaller=pb;pb=pb—〉next;smaller—>next=(*C)—>next;(*C)—>next=smaller;)}while(pa!=NULL){smaller=pa; pa=pa—>next;smaller—>next=(*C)—>next;(大C)—>next=smaller;)while(pb!=NULL){smaller=pb;pb=pb—>next;smaller—>next=(*C)—>next;(大C)—〉next=smaller;(完整桢网版)《数据结构——0语言描述》习题及答案耿国华}〈方法2〉LinkListmerge(LinkListA;LinkListB){……LinkListC；pa二A—〉next;pb=B—>next;C=A；C—〉next二NULL；returnC;假设有一个循环链表的长度大于1,且表中既无头结点也无头指针.已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点.［提示］:设指针P指向5结点的前趋的前趋，则p与s有何关系？已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间.2。11设线性表A=(a1, a2，…，am), B=(b1,幺,…，bj,试写一个按下列规则合并A、B为线性表C的算法，使得：C二(a1,b1，…，a,b,b+1…，b)当mWn时；或者C=(a1,b1，…，a,b,a+1 …，a)当m>n时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储.［提示］:voidmerge(LinkListA；LinkListB；LinkList*C)或：LinkListmerge(LinkListA；LinkListB)2。12将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。［提示］:注明用头指针还是尾指针。建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。［提示］:可将低位放在前面。2。14设多项式P(x)采用课本中所述链接方法存储.写一算法，对给定的x值，求P(x)的值。［提示］:floatPolyValue(Polylistp；floatx){ }(完整桢网版)《数据结构——0语言描述》习题及答案耿国华实习题.将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标.要求：给定一个城市名，返回其位置坐标；给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于口的城市。.约瑟夫环问题。约瑟夫问题的一种描述是:编号为1,2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。例如巾的初值为20；n=7，7个人的密码依次是:3，1，7，2，4,8，4，出列的顺序为6，1，4,7，2,3,5。第二章答案实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2，…，n的n个人按顺时针方向围坐一圈，每个人持有一个密码(正整数).一开始任选一个报数上限值m，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数,如此下去，直至所有的人全部出列为止。试设计一个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程按照出列顺序打印出各人的编号。例如，m的初值为20；n=7，7个人的密码依次是:3,1,7,2,4，8,4，出列顺序为6,1,4，7，2,3，5。【解答】算法如下：typedefstructNode(intpassword;intnum；structNode*next；}Node,*Linklist;voidJosephus()(LinklistL;Node*p，*r,*q;intm，n,C,j；L二(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/

（完整桢网版）《数据结构——0语言描述》习题及答案耿国华if（L==NULL）{printf（"\n链表申请不到空间！"）；return;}L->next=NULL;r二L；printf(”请输入数据n的值(n>0)：")；scanf("%d"，&n);for(j=1；j〈=n;j++) /大建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第％d个人的密码：”，j)；

scanf("%d",&C);p->password=C;p->num=j;r-〉next=p;r=p;}}r-〉next=L->next;printf("请输入第一个报数上限值m(m>0):")；scanf("%d",&m);printf("*****************************************\n");printf("出列的顺序为：\n”)；q二printf("出列的顺序为：\n”)；q二L;p=L->next;while(n!=1){j=1;while(j〈m){q二p;p=p-〉next;j++;}printf(”%d->”,p->num);m=p—〉password;/*计算出列的顺序*//*计算当前出列的人选p*//*q为当前结点p的前驱结点大//*获得新密码*/(完整桢网版)《数据结构——0语言描述》习题及答案耿国华n--;q->next=p->next; /*p出列*/r二p;p=p—〉next；free(r)；)printf("%d\n",p—〉num);}即在原表的存储空间将线性表(a,%,…，an)逆*num)2.7试分别以不同的存储结构实现单线表的就地逆置算法，置为⑦」即在原表的存储空间将线性表(a,%,…，an)逆*num)【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int{intj;ElemTypetmp;for(j=0;j〈=(大num-1)/2;j++)(tmp=L[j];L[j]=L[*num-j-1];L[*num—j-1]=tmp;}}}(2)用单链表作为存储结构voidinvert(LinkListL)(Node *p,*q,*r;/*链表为空*//*链表为空*/p=L->next;/*摘下第一个结点，生成初始逆置表*//*从第二个结点起依次头插入当前逆置表大/q=p-〉next;p/*摘下第一个结点，生成初始逆置表*//*从第二个结点起依次头插入当前逆置表大/{r=q—>next;q->next=L一〉next;L—>next=q;q=r;(完整桢网版)《数据结构——0语言描述》习题及答案耿国华)2。11将线性表A=(a1,a2,……am),B=(b1,b2,……bn)合并成线性表C,C二(a1,b1,……am,bm,bm+1, bn)当m〈二n时，或C=(a1，b1, an，bn，an+1， am)当m〉n时，线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkListmerge(LinkListA,LinkListB,LinkListC){Node*pa,*qa,*pb,*qb,*p;pa=A-〉next; /*pa表示A的当前结点大/pb=B-〉next;p=A;/*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/while(pa!=NULL &&pb!=NULL) /大利用尾插法建立连接之后的链表*/{qa=pa一〉next;qb=qb-〉next;p->next=pa; /大交替选择表A和表B中的结点连接到新链表中；*/p二pa;p->next=pb;p=pb;pa=qa;pb=qb;)if(pa!二NULL) p一〉next=pa; /*A的长度大于B的长度大/if(pb!=NULL) p一〉next=pb; /*B的长度大于A的长度大/C=A;return(C);}第3章限定性线性表-栈和队列习题1,按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答:（完整桢网版）《数据结构——0语言描述》习题及答案耿国华⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？123、213、132、231、321（312）⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“5”表示进栈、以“X”表示出栈的栈操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62.设队列中有A、B、C、D、E这5个元素，其中队首元素为人。如果对这个队列重复执行下列4步操作：输出队首元素；把队首元素值插入到队尾；删除队首元素；再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：A、C、E、C、C （2）A、C、EA、C、E、C、C、C （4）A、C、E、C［提示］:A、B、C、D、E （输出队首元素A）A、B、C、D、E、A （把队首元素A插入到队尾）B、C、D、E、A（删除队首元素A）C、D、E、A （再次删除队首元素B）C、D、E、A（输出队首元素C）C、D、E、A、C（把队首元素C插入到队尾）D、E、A、C （删除队首元素C）E、A、C（再次删除队首元素D）3,给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和赛运算（T）优先关系的惯例画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B^C/D+ETF5,试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，,a+b&b+a,是属该模式的字符序列，而'1+3&3—1'则不是。［提示］:边读边入栈，直到&边读边出栈边比较，直到……6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。［提示］:(完整桢网版)《数据结构——0语言描述》习题及答案耿国华例：中缀表达式：a+b后缀表达式：ab+中缀表达式：a+bXc后缀表达式：abcX+中缀表达式:a+bXc-d 后缀表达式： abcX+d—中缀表达式：a+bXc—d/e后缀表达式：abcX+de/-中缀表达式：a+bX(c—d)-e/f 后缀表达式： abcd—X+ef/-后缀表达式的计算过程：(简便)顺序扫描表达式，(1)如果是操作数，直接入栈；(2)如果是操作符。p,则连续退栈两次，得操作数*,Y,计算XopY,并将结果入栈。如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式，(1)如果是操作数，直接输出；(2)如果是操作符op2,则与栈顶操作符0Pl比较：如口果0P2>0Pl，则0P2入栈；如果0P2=0Pl，则脱括号；如果0P2<0Pl，则输出0P1；.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。［提示］:参P。56P。70先画图。tyPedefLinkListCLQueue；intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTyPex)intDeleteQueue(CLQueueQ,QueueElementTyPe*x).要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法.［提示］:初始状态：front==0,rear——0,tag——0队空条件：front=rear, tag==0队满条件：front=rear,tag==1其它状态：front!=rear, tag==0(或1、2)入队操作：…（人队）if（front==rear）tag=1；（或直接t28二1）（完整桢网版）《数据结构——0语言描述》习题及答案耿国华出队操作:…(出队)tag=0;[问题]:如何明确区分队空、队满、非空非满三种情况？9,简述以下算法的功能(其中栈和队列的元素类型均为int)：(1)voidproc_1(StackS){iinti,n,A[255];n=0;while(!EmptyStack(S)){n++；Pop(&S, &A[n]);}for(i=1; i〈二n; i++)Push(&S,A[i]);)将栈S逆序。voidproc_2(StackS,inte){StackT;intd;InitStack(&T)；while(!EmptyStack(S))(Pop(&S,&d)；if(d!=e)Push(&T, d);)while(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);})删除栈S中所有等于e的元素。(完整桢网版)《数据结构——0语言描述》习题及答案耿国华voidproc_3(Queue*Q)(StackS；intd；InitStack(&S);while(！EmptyQueue(大Q))(DeleteQueue(Q, &d);Push(&S,d);}while(!EmptyStack(S))(Pop(&S,&d);EnterQueue(Q,d))}将队列Q逆序。实习题.回文判断。称正读与反读都相同的字符序列为“回文”序列。试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&',且序列2是序列1的逆序列。例如，,a+b&b+a'是属该模式的字符序列，而'1+3&3—1'则不是。.停车场管理。设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场机汽车按到达的先后次序，由北向南依次排列(假设大门在最南端)。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费(在便道上停留的时间不收费).试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。(提示：需另设一个栈，临时停放为让路而从车场退出的车。)车库(完整桢网版)《数据结构——0语言描述》习题及答案耿国华.商品货架管理。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近.上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。第三章答案3。1按3。1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：(1)如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因(即写出以匕”表示进栈、"X"表示出栈的栈序列操作)。【解答】(1)可能得到的出站车厢序列是：123、132、213、231、321。(2)不能得到435612的出站序列。因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1)。能得到135426的出站序列。因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？【解答】(1)顺序栈 (top用来存放栈顶元素的下标)判断栈S空：如果S—>top==-1表示栈空.判断栈S满：如果5—乂吨二5t20七5126-1表示栈满.(2)链栈(top为栈顶指针，指向当前栈顶元素前面的头结点)判断栈空：如果top—>next==NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。照四则运算加、减、乘、除和赛运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A—B*C/D+EfF

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华【解答】3。5写一个算法，判断依次读入的一个以@为结束符的字母序列,是否形如‘序列1&序列2'的字符序列.序列1和序列2中都不含‘&',且序列2是序列1的逆序列。例如，'2+13&13+2'是属于该模式的字符序列，而’1+3&3-1’则不是。【解答】算法如下：intIsHuiWen(){Stack*S;Charch,temp;InitStack(&S);Printf("\n请输入字符序列：”)；Ch二getchar();While(ch!=&){While(ch!=&){Push(&S,ch);ch二getchar();}/大序列1入栈*/do(ch二getchar();Pop(&S,&temp);if(ch!=temp)(return(FALSE);}}while(ch!=@if(ch==@ &&do(ch二getchar();Pop(&S,&temp);if(ch!=temp)(return(FALSE);}}while(ch!=@if(ch==@ &&{return(TRUE);printf&&!IsEmptyelse(“\nNO")；IsEmpty(&S))(&S))printf(“\nYES")；}/*序列2不是序列1的逆序列大//*序列2是序列1的逆序列大/{return(FALSE);}/*IsHuiWen()*/printf(“\nNO")；}/*判断序列2是否是序列1的逆序列*/3。8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法.【解答】入队算法：intEnterQueue(SeqQueue*Q,QueueElementTypex)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华{/大将元素x入队*/if(Q->front=Q-〉front&&tag==1) /大队满*/return(FALSE)；if(Q-〉front==Q->front&&tag==0) /*x入队前队空，x入队后重新设置标志*/tag=1;Q->elememt[Q-〉rear]二x;Q—>rear=(Q—>rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE)；}出队算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x){/大删除队头元素，用x返回其值*/if(Q->front==Q—>rear&&tag==0) /大队空*/return(FALSE);*x=Q-〉element[Q—〉front];Q—〉front=(Q->front+1)%MAXSIZE； /*重新设置队头指针*/if(Q—〉front==Q->rear)tag=0;/大队头元素出队后队列为空，重新设置标志域*/Return(TUUE);}编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：voidhanoi(intn,charx,chary,charz){/大将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座*/if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);)}Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):(完整桢网版)《数据结构——0语言描述》习题及答案耿国华move(A-〉C)1号搬到CMove(A-〉B) 2号搬到BHanoi(1,C,A,B)move(C—>B)1号搬到BMove(A—>C) 3号搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B—〉A)1号搬到AMove(B-〉C) 2号搬到CHanoi(1,A,B,C)move(A->C) 1号搬到C第4章串习题1.设s='IAMASTUDENT', t二'GOOD', q二'30区在^.给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7)；SubString(sub2,s,7,1)；StrIndex(s,'A',4);StrReplace(s,’STUDENT',q);StrCat(StrCat(sub1,t),StrCat(sub2,q));［参考答案］StrLength(s)=14；sub1二’IAMA_’; sub2='_'；StrIndex(s,'A',4)=6；StrReplace(s,'STUDENT',q)='IAMAWORKER?；StrCat(StrCat(sub1,t),StrCat(sub2,q))='IAMAGOODWORKER';2。编写算法，实现串的基本操作StrReplace(S,T,V)。3。假设以块链结构表示串，块的大小为1,且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T);SubString(Sub,S,pos,len)。［说明］:用单链表实现。4。叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5.已知:S="(xyz)*"，T="(x+z)*y”.试利用联接、求子串和置换等操作，将S转换为T。6。S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置.7。S是用结点大小为4的单链表存储的串，分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。以下算法用定长顺序串：8,写下列算法：将顺序串r中所有值为ch1的字符换成ch2的字符。

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华将顺序串r中所有字符按照相反的次序仍存放在r中。从顺序串r中删除其值等于ch的所有字符.从顺序串r1中第index个字符起求出首次与串r2相同的子串的起始位置。从顺序串r中删除所有与串r1相同的子串..写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。［提示］:(1)用静态顺序串(2)先移位，后复制.写算法，实现顺序串的基本操作StrCompare(s,t)。11。写算法，实现顺序串的基本操作StrReplace(&s,t,v)。［提示］:(1)被替换子串定位(相当于第9题中i)(2)被替换子串后面的字符左移或右移(为替换子串准备房间)(3)替换子串入住(复制)(4)重复上述，直到……第四章答案4。1设s='IAMASTUDENT‘，t='GOOD’，q='30区在区'。给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1='IAMA’；SubString(sub2,s,7,1) sub2二’'；StrIndex(s,4,'A')=6;StrReplace(s,’STUDENT'，q); s='IAMAWORKER';StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1='IAMAGOODWORKER’。2编写算法，实现串的基本操作StrReplace(S,T,V).【解答】算法如下：intstrReplace(SStringS,SStringT,SStringV){/大用串V替换S中的所有子串T大/intpos,i;pos二strIndex(S,1,T)； /*求S中子串T第一次出现的位置*/if(pos==0)return(0);while(pos!=0) /大用串V替换S中的所有子串T*//*串T的长度等于串V的长度大/

/大用/*串T的长度等于串V的长度大/

/大用V替换T*/for(i=0;i<=Volen;i++)（完整桢网版）《数据结构——0语言描述》习题及答案耿国华S—〉ch[pos+i]=V。ch[i]；case>0： /大串T的长度大于串V的长度*//*将S中子串T后的所有字符前移Tolen-Volen个位置*//*用/*将S中子串T后的所有字符前移Tolen-Volen个位置*//*用V替换T*/S-〉ch[i一tolen+v.len]=S->ch[i];for(i=0；i〈二V.len；i++)S->ch[pos+i]=V.ch[i];S->len=S-〉len一Tolen+Volen;case〈0:/大串T的长度小于串case〈0:if(S—〉len-T.len+Volen)<=MAXLEN/*插入后串长小于MAXLEN*/{/*将S中子串T后的所有字符后移Volen—Tolen个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i)S—>ch[i]=S->ch[i-Tolen+Volen];for(i=0；i〈二V.len;i++) /*用V替换T*/S-〉ch[pos+i]=Voch[i];S—〉len=S—>len—Tolen+V.len;}else{ /*替换后串长〉MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN){for(i=MAXLEN-1;i〉二pos+T.len;i--)S—>ch[i]=s—〉ch[i—T.len+V.len]for(i=0;i<=Volen；i++) /*用V替换T*/S-〉ch[pos+i]=Voch[i]；S-〉len=MAXLEN;}else /*串V的部分字符要舍弃*/{for(i=0；i<MAXLEN-pos;i++)S-〉ch[i+pos]=Voch[i];S-〉len=MAXLEN；}}/*switch()*/pos二pos二StrIndex(S,pos+V.len,T);}/*while()*//*求S中下一个子串T的位置*/return(1);}/*StrReplace()*/附加题：用链式结构实现定位函数0【解答】typedefstructNode{chardata;（完整桢网版）《数据结构——0语言描述》习题及答案耿国华structNode*next;}Node,*Lstring；intstrIndex(LstringS,intpos,LstringT)/*从串S的pos序号起，串T第一次出现的位置*/(Node*p,*q,*Ppos;inti=0,,j=0;if(T—>next==NULL||S->next二二NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p指向串S中第pos个字符*/{p=p->next; j++;}if(j!=pos)return(0);while(p!=NULL&&q!=NULL){Ppos=p; /*Ppos指向当前匹配的起始字符*/if(p->data二二q一〉data){p=p->next;q=q-〉next;}else /*从Ppos指向字符的下一个字符起从新匹配*/{p=Ppos->next;q=T-〉head-〉next;i++;}}if(q==NULL)return(pos+i);/*匹配成功*/elsereturn(0); /*失败*/}第五章数组和广义表习题1。假设有6行8列的二维数组人，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000,计算：数组人共占用多少字节；(288)数组A的最后一个元素的地址；(1282)按行存储时，元素屋的地址；(1126)按列存储时，元素A36的地址；(1192)

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华[注意]:本章自定义数组的下标从1开始。2.设有三对角矩阵(aj)nxn，将其三条对角线上的元素逐行地存于数组8(1：3门一2)中，使得B[k]=aj,求：(1)用i,j表示k的下标变换公式；(2)用k表示i,j的下标变换公式.i=k/3+1,j=k%3+i-1=k%3+k/3或：：i=k/3+1,j=k-2X(k/3).假设稀疏矩阵A和B均以三元组表作为存储结构.试写出矩阵相加的算法，另设三元组表C存放结果矩阵.[提示]:参考P.28例、P.47例..在稀疏矩阵的快速转置算法5。2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。[提示]:1) position[k]中为第k列非零元素个数,女二1,2,…，n2) position[0]=1;(第1列中第一个非零元素的正确位置)3) position[k]二position[k-1] +position[k ] ,k=1, 2,…，n4) position[k] =position[k-1] ,k=n,n - 1,…,1.写一个在十字链表中删除非零元素aj的算法。[提示]:“删除”两次，释放一次。.画出下面广义表的两种存储结构图示:((((a),b)),())((),d), (e,f)0e0f((((a),b)),())((),d), (e,f)0e0f第一种存储结构(自底向上看)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华.求下列广义表运算的结果：HEAD[((a,b),(c,d))];TAIL[((a,b),(c,d))]；TAIL[HEAD[((a,b),(c,d))]];HEAD[TAIL[HEAD[((a,b),(c,d))]]]；bTAIL[HEAD[TAIL[((a,b),(c,d))]]]； (d)参考题.试设计一个算法，将数组人(0:n-1)中的元素循环右移女位，并要求只用一个元素大小的附加存储，元素移动或交换次数为06)..假设按低下标优先(以最左的下标为主序)存储整数数组A(1:8,1:2,1:4,1:7)时，第一个元素的字节地址是100,每个整数占4个字节，问元素A(4,2,3,5)的存储地址是什么？10。高下标优先(以最右的下标为主序)存储整数数组人(1:8,1:2,1:4,1:7)时，顺序列出数组A的所有元素.11.试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。实习题1.若矩阵Am*”中的某个元素aj是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点.第五章答案5。2三对角矩阵人义”,将其三条对角线上的元素逐行的存于数组8[1..3”一2]中，使得B[k]=aj,求：(1)用i,j表示k的下标变换公式；(2)用k表示i、j的下标变换公式.【解答】(1)k=2(i-1)+j(2)i=[k/3]+1,j=[k/3]+k%3 ([]取整，％取余)5.4稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间.【解答】算法(一)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){/大把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/intcol,t,p,q;intposition[MAXSIZE];B-〉len=A。len;B一〉n=A.m; B-〉m=A.n;if(B—>len>0)(position[1]=1；for(t=1;t<=A.len;t++)position[Aodata[t].col+1]++； /*position[col]存放第col—1列非零元素的个数，即利用pos[col]来记录第col-1列中非零元素的个数*//*求col列中第一个非零元素在B.data[]的位置，存放在position[col]中大/for(col=2；col<=A.n;col++)position[col]=position[col]+position[col-1]；for(p=1;p〈A。len;p++){col=Aodata[p]。col;q=position[col];B-〉data[q]。row=A.data[p].col;B-〉data[q].col=A。data[p].row;B—>data[q]oe=A.data[p].e;Position[col]++;)))算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){intcol,t,p,q;intposition[MAXSIZE];B->len=A.len;B-〉n=A。m;B->m=A.n;if(B-〉len>0){for(col=1;col<=A.n;col++)position[col]=0;for(t=1;t〈二A.len;t++)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华position[Aodata[t].col]++； /*计算每一列的非零元素的个数*///从最后一列起求每一列中第一个非零元素在Bodata口中的位置，//放在position[col]中*/for(col=A.n,t=A。len;col>0;col ){t=t-position[col]；position[col]=t+1；}for(p=1;p〈A.len;p++)(col=Aodata[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q]ocol=A。data[p]。row;B-〉data[q]oe=A.data[p].e;Position[col]++;)})5o6画出下面广义表的两种存储结构图示：((((a),b)),(((),d),(e,f)))【解答】5o7求下列广义表运算的结果：HEAD[((a,b),(c,d))]; (a,b)TAIL[((a,b),(c,d))]; ((c,d))TAIL[HEAD[((a,b),(c,d))]]; (b)HEAD[TAIL[HEAD[((a,b),(c,d))]]];bTAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)第六章树和二叉树习题.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。.对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

(完整word(完整word版)《数据结构。语言描述》习题及答案耿国华.已知一棵度为k的树中有7个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？［提示］:参考Po116性质3.n=n0+n1+ + nkB=n1+2n2+3n3+ +knkn=B+1「・ n0+ n1+ + nk = n1+ 2n2 +3n3+ + knk +1「・n0=n2+2n3+ + (k—1)nk+14o假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树。［提示］:参考Po1485.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？［提示］:［方法1］(1)一个叶子结点，总结点数至多有多少个？结论：可压缩一度结点.(2)满二叉树或完全二叉树具有最少的一度结点(3)可能的最大满二叉树是几层？有多少叶结点？如何增补？25〈50<26可能的最大满二叉树是6层有25二32个叶结点假设将其中x个变为2度结点后，总叶结点数目为50则：2x+(32-x)二50得：x二18此时总结点数目二(26-1)+18X2［方法2］假设完全二叉树的最大非叶结点编号为m,则最大叶结点编号为2m+1,(2m+1)-m=50m=49总结点数目=2巾+1=99［方法3］由性质3:n0=n2+1即：50二n+12所以：n2=49令门1二0得：n=n0+n2=99(完整桢网版)《数据结构——0语言描述》习题及答案耿国华6,给出满足下列条件的所有二叉树：(1)前序和中序相同(2)中序和后序相同(3)前序和后序相同［提示］:去异存同.(1)DLR与LDR的相同点：D艮如果无L,则完全相同，如果无LR,…。(2)LDR与LRD的相同点：L口,如果无R，则完全相同.(3)DLR与LRD的相同点：口，如果无LR,则完全相同。(如果去口，则为空树)。n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个?［提示］:参考P.119.画出与下列已知序列对应的树T:树的先根次序访问序列为GFKDAIEBCHJ;树的后根次序访问序列为DIAEKFCJHBGo［提示］:(1)先画出对应的二叉树(2)树的后根序列与对应二叉树的中序序列相同.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0o07,0o19,0.02,0.06,0.32,0。03,0。21,0.10(1)请为这8个字母设计哈夫曼编码，(2)求平均编码长度..已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因.［提示］:无右子的“左下端”(完整桢网版)《数据结构——0语言描述》习题及答案耿国华12.已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。.编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。［提示］:［方法1］:(1)按先序查找；(2)超前查看子结点(3)按后序释放；voidDelSubTree(BiTree*bt,DataTypex){if(*bt!=NULL&&(*bt)->data==x){FreeTree(*bt);*bt=NULL;)elseDelTree(大bt,x)voidDelTree(BiTreebt,DataTypex){if(bt){if(bt—>LChild&&bt—〉LChild—>data=x){FreeTree(bt—>LChild);bt—>LChild二NULL；}if(bt->RChild&&bt->RChild—〉data==x){FreeTree(bt-〉RChild)；bt->RChild二NULL；}DelTree(bt—>LChild, x)；DelTree(bt->RChild,x)；)}［方法2］：(1)先序查找；(2)直接查看当前根结点(3)用指针参数；［方法3］:(1)先序查找；(2)直接查看当前根结点(3)通过函数值，返回删除后结果；(参示例程序).分别写函数完成：在先序线索二叉树T中，查找给定结点大p在先序序列中的后继。在后序线索二叉树T中，查找给定结点大p在后序序列中的前驱。［提示］:(1)先查看线索，无线索时用下面规律：（完整桢网版）《数据结构——0语言描述》习题及答案耿国华（2）结点*p在先序序列中的后继为其左子或右子；（3）结点*p在后序序列中的前驱也是其左子或右子。.分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题）.编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数.［提示］:（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。（2）可利用返回值，或全局变量..对以孩子-兄弟链表表示的树编写计算树的深度的算法。.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。（参课本）.设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。［提示］:可利用任何递归、非递归遍历算法。.计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。.证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；.二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换.实习题1.［问题描述］建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果.［基本要求］从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出.要求采用递归和非递归两种方法实现。［测试数据］ABC^BDE^G8BF^BB（其中布表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA

（完整桢网版）《数据结构——0语言描述》习题及答案耿国华后序：CGBFDBA.已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）.［提示］:（1）参习题6。20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离如图6。34所示。如图6。34所示。.按凹入表形式打印树形结构，如图6.35所示.［提示］:参P.129例，用先根遍历。EFG 图6.35第六章答案6.1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。(完整桢网版)《数据结构——0语言描述》习题及答案耿国华【解答】具有3个结点的树 具有3个结点的二叉树已知一棵度为k的树中有7个度为1的结点,％个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n，则n=n0+n1+……+nk树中分支数目为B,则B=n1+2n2+3n3+……+knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1即n0+n1+……+nk=n1+2n2+3n3+……+knk+1由上式可得叶子结点数为：n0=n2+2n3+……+(k—1)nk+16。5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0=n2+1所以n2=n0-1=49,当二叉树中没有度为1的结点时，总结点数n=,+3=99试分别找出满足以下条件的所有二叉树：(1)前序序列与中序序列相同；(2)中序序列与后序序列相同；(3)前序序列与后序序列相同。【解答】(1)前序与中序相同：空树或缺左子树的单支树；(2)中序与后序相同：空树或缺右子树的单支树；(3)前序与后序相同：空树或只有根结点的二叉树。6。9假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0。07,0.19,0。02,0。06,0。32,0。03,0。21,0.10请为这8个字母设计哈夫曼编码.【解答】构造哈夫曼树如下：哈夫曼编码为：11:11111 15：1100I：11110 I：102 6I3：1110 I7：01I4：1101 I8：006.11画出如下图所示树对应的二叉树。【解答】(完整桢网版)《数据结构——0语言描述》习题及答案耿国华6。15分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点大p在后序序列中的前驱。【解答】(1)找结点的中序前驱结点BiTNode*InPre(BiTNode*p)/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/{if(p一〉Ltag==1)pre二p一〉LChild;/大直接利用线索大/else{/大在p的左子树中查找“最右下端”结点*/for(q=p-〉LChild;q一>Rtag==0;q=q一>RChild);pre=q;)return(pre);}(2)找结点的中序后继结点BiTNode*InSucc(BiTNode*p)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/{if(p—>Rtag==1)succ=p—〉RChild；/*直接利用线索大/else{/*在p的右子树中查找“最左下端”结点*/for(q=p—〉RChild;q-〉Ltag==0;q=q-〉LChild);succ=q;)return(succ);)(3)找结点的先序后继结点BiTNode*PreSucc(BiTNode*p)/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/{if(p->Ltag==0)succ=p-〉LChild;elsesucc=p—〉RChild;return(succ);)(4)找结点的后序前驱结点BiTNode*SuccPre(BiTNode*p)(完整桢网版)《数据结构——0语言描述》习题及答案耿国华/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/{if(p—〉Ltag==1)pre=p-〉LChild；elsepre=p一〉RChild;return(pre);}6。21已知二叉树按照二叉链表方式存储，试利用栈的基本操作写出先序遍历非递归形式的算法。【解答】VoidPreOrder(BiTreeroot) /*先序遍历二叉树的非递归算法*/{InitStack(&S)；p=root;while(p!=NULL||!IsEmpty(S)){if(p!=NULL){Visit(p一〉data);push(&S,p);p=p-〉Lchild;}else{Pop(&S,&p)；p二p一〉RChild；))}6.24已知二叉树按照二叉链表方式存储，编写算法,将二叉树左右子树进行交换。【解答】算法(一)Voidexchange(BiTreeroot){p=root;if(p—〉LChild!=NULL||p-〉RChild!=NULL)(temp=p—>LChild；p—〉LChild=p-〉RChild;

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华p—>RChild二temp；exchange(p—〉LChild)；exchange(p-〉RChild);})算法(二)Voidexchange(BiTreeroot){p=root;if(p->LChild!=NULL||p-〉RChild!二NULL){exchange(p—>LChild);exchange(p—〉RChild);temp二p—〉LChild;p->LChild=p一〉RChild；p—>RChild二temp;})第七章图已知如图所示的有向图，请给出该图的:每个顶点的入度、出度；邻接矩阵；邻接表；逆邻接表；十字链表；强连通分量。

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华已知如图所示的无向图，请给出该图的：邻接多重表；(要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。)从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；(给出深度优先搜索树)从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。(给出广度优先搜索树)图7.31图7.31题7.3用图图7图7・30题7。4用图7.4已知如图7.31所示的AOE—网，试求：每个事件的最早发生时间和最晚发生时间;每个活动的最早开始时间和最晚开始时间;给出关键路径。7.5

（完整桢网版）《数据结构——0语言描述》习题及答案耿国华7.67.77.8已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。试在邻接矩阵存储结构上实现图的基本操作：InsertVertex（G，v）;InsertArc（G，v，w）；DeleteVertex（G,v）和DeleteArc（G，v，w）。试对邻接表存储结构重做题6.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点v到i顶点丫上的路径（i/j）.注意：算法中涉及的图的基本操作必须在此存储结构上实现。同上题要求。试基于图的广度优先搜索策略写一算法.试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法.算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。［提示］:利用深度搜索，增设一个深度参数，深度超过k则停止对该结点的搜索.7.11下图是带权的有向图G的邻接表表示法。从结点丫1出发，深度遍历图G所得结点序列为（A）,广度遍历图G所得结点序列为（B）;G的一个拓扑序列是（C）;从结点丫1到结点V8的最短路径为（D）；从结点丫1到结点丫8的关键路径为（E）。其中A、B、C的选择有：①V1,V2,V3,V4,V5,V6,V7,V8②V1,V2,V4,V6,V5,V3,V7,V8③V1,V2,V4,V6,V3,V5,V7,V8④V1,V2,V4,V6,V7,V3,V5,V8⑤V1,V2,V3,V8,V4,V5,V6,V7⑥V1,V2,V3,V8,V4,V5,V7,V6⑦V1,V2,V3,V8,V5,V7,V4,V6D、ED、V1,V2,V4,V5,V3,V8V1,V6,V5,V3,V8V7,V8④V1,V6,V1,V6,V5,V3,V8V7,V8④V1,V6,(完整桢网版)《数据结构——0语言描述》习题及答案耿国华7.13二叉树的层次遍历。实习题.分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。.校园导游程序。用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：查询各景点的相关信息；查询图中任意两个景点间的最短路径。查询图中任意两个景点间的所有路径。.编程求解关键路径问题.补充题1.将图7。31所示的有向网改为无向网，并要求：(1)用普里姆算法从顶点9开始，手工构造最小生成树。(最小代价连通网)(2)用克鲁斯卡尔算法手工构造最小生成树。(注：可将结点看成电脑，将权值看成电缆代价;也可将结点看成城市，将权值看成电缆代价；还可将结点看成城市，将权值看成修路代价；)

(完整桢网版)《数据结构——0语言描述》习题及答案耿国华2.将图7.31所示的AOE-网改为人0丫-网(去掉权值即可)，并给出一个拓扑序列。(要求优先输出编号小的顶点).参考题.已知有向图，试基于图的深度优先搜索策略写一算法，求顶点丫］到顶点丫上的一条简单路径(i/j)。［提示］:有向图可用邻接表存储，并在表结点中增加一个prior域.7。1已知如图所示的有向图，