《数据结构与算法(徐凤生)》习题答案.doc 66页

'《数据结构与算法》习题答案66 目录第1章——————————————————2第2章——————————————————7第3章——————————————————13第4章——————————————————21第5章——————————————————26第6章——————————————————32第7章——————————————————42第8章——————————————————54第9章——————————————————60第10章——————————————————6466 习题11.解释下列术语：数据、数据元素、数据对象、数据结构。解：数据是用于描述客观事物的数值、字符以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合，是计算机操作的对象的总称。数据元素是数据的基本单位，它是数据中的一个“个体”。有时，一个数据元素可有若干数据项组成，。数据项是数据的不可分割的最小单位。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？解：数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如，C语言中的整型变量，其值为某个区间上的整数(依赖于机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。抽象数据类型(AbstractDataType，简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，“整数”是一个抽象数据类型，其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。ADT的定义取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部的使用。抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西，忽略非本质的细节，从而使所设计的数据结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节，使用者仅需了解抽象操作，或界面服务，通过界面中的服务来访问这些数据。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分。3.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。(4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。66 4.简述数据结构的三个层次、五个要素。解：数据结构的三个层次是指抽象、实现和评价三个层次，五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面。5.举一个数据结构的例子，说明其逻辑结构、存储结构及其运算三个方面的内容。并说明数据的逻辑结构、存储结构及其运算之间的关系。解：例如复数数据结构，其逻辑结构是复数的表示，而存储结构是指复数在计算机内的表示，运算是指对复数初始化、相加等操作。数据的逻辑结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。6.设为整数，试给出下列各程序段中标号为@的语句的频度。（1）i=1;while(ij)j++;elsei++;}（5）x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}（6）x=91;y=100;while(y>0){66 @if(x>100){x-=10;y--;}elsex++;}解：（1）ëû；（2）n-1；（3）n-1；（4）éù；（5）ëû；（6）1007.调用下列C函数，回答下列问题：（1）试指出值的大小，并写出值的推导过程。（2）假定=5，试指出值的大小和执行时的输出结果。intf(intn){inti,j,k,sum=0;for(i=1;ii-1;j--)for(k=1;knext。（1）while(p!=NULL&&p->data!=x)p=p->next;if(p==NULL)returnNULL;//查找失败elsereturnp;//查找成功（2）while(p!=NULL&&p->datanext;if(p==NULL||p->data>x)returnNULL;//查找失败elsereturnp;//查找成功（3）while(p!=NULL&&p->data>x)p=p->next;if(p==NULL||p->datanext;//L是一带头结点的单链表，结点有数据域data和指针域nextif(pre!=NULL)while(pre->next!=NULL){p=pre->next;if(p->data>=pre->data)pre=p;66 elsereturn(FALSE);}return(TUURE);解：该算法的功能是判断链表L是否非递减有序，若是则返回TRUE，否则返回FALSE。pre指向当前结点，p指向pre的后继。7.设、分别指向两个带头结点的有序（从小到大）单链表。阅读下列程序，并回答问题：（1）程序的功能；（2）、2中的值的含义；（3）、中值的含义。voidexam(LinkListpa,LinkListpb){p1=pa->next;p2=pb->next;pa->next=NULL;s1=0;s2=0;while(p1&&p2){switch{case(p1->datadata):p=p1;p1=p1->next;s2++;deletep;case(p1->data>p2->data):p2=p2->next;case(p1->data=p2->data):p=p1;p1=p1->next;p2->next=p2->next;pa->next=p;p2=p2->next;s1++;}while(p1){p=p1;p1=p1->next;deletep;s2++;}}}解：本程序的功能是将pa和pb链表中值相同的结点保留在pa链表中（pa中与pb中不同的结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。s1记结果链表中结点个数（即pa与pb中相等的元素个数），s2记原pa链表中删除的结点个数。8.假设长度大于1的循环单链表中，既无头结点也无头指针，为指向该链表中某一结点的指针，编写一算法删除该结点的前驱结点。解：intDelete_Pre(LNode*p){LNode*q,*temp;q=p;while(q->next->next!=p)q=q->next;temp=q->next;q->next=p;deletetemp;returnOK;}66 9.已知两个单链表La和Lb分别表示两个集合，其元素递增排列。编写一算法求其交集Lc，要求Lc以元素递减的单链表形式存储。解：voidInter_set(LinkListLa,LinkListLb,LinkList&Lc){LNode*pa,*pb,*pc;pa=La->next;pb=Lb->next;Lc=newLNode;Lc->next=NULL;while(pa&&pb){if(pa->data==pb->data){pc=newLNode;pc->data=pa->data;pc->next=Lc->next;Lc->next=pc;pa=pa->next;pb=pb->next;}elseif(pa->datadata)pa=pa->next;elsepb=pb->next;}}10.已知单链表是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。解：voidDelete_Between(LinkList&L,intmin,intmax){LNode*p,*q,*s;p=L;while(p->next->data<=min)p=p->next;if(p){q=p->next;while(q&&q->datanext;deletes;}p->next=q;}}11.已知非空单链表的头指针为，试写一算法，交换所指结点与其下一个结点在链表中的位置（设66 指向的不是链表最后那个结点）。解：voidExchange(LinkList&L,LNode*p){LNode*q,*pre;q=L->next;pre=L;while(q!=NULL&&q!=p){pre=q;q=q->next;}if(p->next==NULL)printf("p无后继结点n");else{q=p->next;pre->next=q;p->next=q->next;q->next=p;}}12.线性表中有n个元素，每个元素是一个字符，现存于数组R[n]中，试写一算法，使R中元素的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的空间，元素移动次数最小。解：voidprocess(charR[],intn){intlow,high;chark;low=0;high=n-1;while(lownext;pre=L;q=p;while(p->next!=NULL){if(p->next->datadata){pre=p;q=p->next;}p=p->next;}pre->next=q->next;deleteq;}14.已知两个单链表La和Lb，其元素递增排列。编写一算法，将La和Lb归并成一个单链表Lc，其元素递减排列（允许表中有相同的元素），要求不另辟新的空间。解：voidinteraction(LinkList&La,LinkListLb){LNode*pa,*pb,*s;pa=La->next;pb=Lb->next;La->next=NULL;deleteLb;while(pa&&pb)if(pa->datadata){s=pa;pa=pa->next;s->next=La->next;La->next=s;}else{s=pb;pb=pb->next;s->next=La->next;La->next=s;}while(pa){s=pa;pa=pa->next;s->next=La->next;La->next=s;}while(pb){s=pb;pb=pb->next;s->next=La->next;La->next=s;}}15.设以带头结点的双向循环链表表示的线性表。试写一时间复杂度为的算法，将改造为。解：voidOEReform(CirDuLinkList&L){DuLNode*p;p=L->next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}if(p->next==L)p->next=L->prior->prior;66 elsep->next=L->prior;p=p->next;while(p->prior->prior!=L){p->next=p->prior->prior;p=p->next;}p->next=L;for(p=L;p->next!=L;p=p->next)p->next->prior=p;L->prior=p;}16.设有一双向循环链表，每个结点除有prior、data和next三个域外，还有一个访问频度域frep。在链表被起用之前，频度域frep的值为0，而每当对链表进行一次LocateElem(L，e)的操作后，被访问的结点的频度域frep的值增1，同时调整链表中结点之间的顺序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试写出符合上述要求的LocateElem操作的算法。解：voidLocateElem(CirDuLinkList&L,intx){DuLNode*p=L->next,*q;while(p->data!=x&&p)p=p->next;if(p){p->frep++;q=p->prior;while(q->frepfrep&&q!=L)q=q->prior;if(q!=p->prior){p->prior->next=p->next;p->next->prior=p->prior;q->next->prior=p;p->next=q->next;q->next=p;p->prior=q;}}}习题31.名词解释：栈、队列、循环队列。解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。66 队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。3.试证明：若借助栈由输入序列1，2，…，得到序列，，…，(它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着<<，使得<<。解：如果<，说明在入栈前先出栈。而对于>的情况，则说明要将压到之上，也就是在出栈之后才能出栈。这说明，对于<<，不可能出现<<的输出序列。4.当函数递归调用自身时，函数内定义的局部变量在函数的2次调用期间是否占用同一数据区？为什么？解：函数递归调用自身时，函数内定义的局部变量在函数的2次调用期间不占用同一数据区。每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。解：循环队列的数据结构略。typedefstruct{ElemType*elem;intfront;intrear;}SqQueue,Q;（1）初始状态:Q.front=Q.rear=0;（2）队列空:Q.front=Q.rear=0;（3）队列满:Q.front=(Q.rear+1)%MAXSIZE;6.设一个双端队列，元素进入该队列的次序为1，2，3，4.求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。66 解：既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是：4，2，3，1。7.简述以下算法的功能。(1)voidalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);};for(i=1;i<=n;i++)Push(S,A[i]);}(2)voidalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}(3)voidalgo3(Queue&Q){//栈和队列的元素类型均为intStackS;intd;InitStack(T);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}解：（1）将栈中元素逆置。（2）将栈中的0元素删除。（3）将队列中元素逆置。8.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中不含字符@，且序列2是序列1的逆序列。解：intIsReverse(){//判断输入的字符串中"&"前和"&"后部分是否为逆串,是则返回1,否则返回0SqStacks;charc,x;InitStack(s);while((c=getchar())!="&")Push(s,c);while((c=getchar())!="@"){if(StackEmpty(s))return0;Pop(s,x);if(x!=c)return0;66 }if(!StackEmpty(s))return0;return1;}9.在火车调度站的入口处有节硬席或软席车厢(分别以H和S表示)等待调度，试写一算法，输出对这节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。解：typedefcharSS[MAX];voidTrain_arrange(SS&train){//这里用字符串train表示火车,"H"表示硬席,"S"表示软席SqStacks;char*p,*q,c;p=train;q=train;InitStack(s);while(*p){if(*p=="H")Push(s,*p);//把"H"存入栈中else*(q++)=*p;//把"S"调到前部p++;}while(!StackEmpty(s)){Pop(s,c);*(q++)=c;//把"H"接在后部}}10.试写出求递归函数的递归算法，并消除递归：解：intF_recursive(intn,int&s){//递归算法if(n<0)returnERROR;if(n==0)s=n+1;else{F_recursive(n/2,s);s=n*s;}returnOK;66 }//F_recursivetypedefstruct{ElemTypea;ElemTypeb;}node;typedefstruct{node*data;inttop;//栈顶指针intstacksize;}SqStack;voidF_nonrecursive(intn,int&s){//非递归算法SqStackT;nodex,t;if(n<0)exit(0);if(n==0)s=n+1;else{InitStack(T);while(n!=0){x.a=n;x.b=n/2;Push(T,x);n=x.b;}//whiles=1;while(!StackEmpty(T)){Pop(T,t);s*=t.a;}//while}}//F_nonrecursive11.试将下列递归函数改为非递归函数。voidtest(int&sum){intx;scanf("%d",&x);if(x==0)sum=0;else{test(sum);sum+=x;}66 printf("sum=%dn",sum);}解：voidtest(){intx,sum=0,top=-1,s[10];scanf("%d",&x);while(x!=0){s[++top]=x;scanf("%d",&x);}printf("sum=%d",sum);while(top>-1){sum+=s[top--];printf("sum=%dn",sum);}};12.设整数列，，…，，给出求解最大值的递归程序。解：intMaxValue(inta[],intn){intmax;if(n==1)max=a[0];elseif(a[n-1]>MaxValue(a,n-1))max=a[n-1];elsemax=MaxValue(a,n-1);returnmax;}13.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队和出队的算法。解：(1)voidInitQueue(CirLinkList&rear){rear=newLNode;rear->next=rear;}(2)voidEnQueue(CirLinkList&rear,ElemTypex){LNode*s;s=newLNode;s->data=x;s->next=rear->next;rear->next=s;rear=s;66 }(3)voidDnQueue(CirLinkList&rear,ElemType&x){LNode*s;if(rear->next==rear){printf("队空n");exit(0);}s=rear->next->next;//s指向队头元素rear->next->next=s->next;//队头元素出队x=s->data;if(s==rear)rear=rear->next;//空队deletes;}14.假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个亿@为结束符的字符序列是否是“回文”。解：intTest(){//判别输入的字符串是否回文序列,是则返回1,否则返回0SqStackS;SqQueueQ;charc;ElemTypea,b;InitStack(S);InitQueue(Q);while((c=getchar())!="@"){Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构}while(!StackEmpty(S)){Pop(S,a);DeQueue(Q,b);if(a!=b)returnERROR;}returnOK;}15.写一算法，借助于栈将一个单链表逆序输出。解：voidprocess(LinkList&L){LNode*p;SqStacks;66 ElemTypex;p=L->next;InitStack(s);while(p){Push(s,p->data);p=p->next;}while(!StackEmpty(s)){Pop(s,x);printf("%d",x);}}16.假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：typedefstruct{ElemType*base;//动态分配存储空间intlength;//队列长度intrear;//尾指针，指向队列尾元素}SqQueue;intEnQueue(SqQueue&Q,ElemTypex){//带length域的循环队列入队算法if(Q.length==MAX)returnERROR;//队列满Q.rear=(Q.rear+1)%MAX;Q.base[Q.rear]=x;Q.length++;returnOK;}intDeQueue(SqQueue&Q,ElemType&x){//带length域的循环队列出队算法inthead;if(Q.length==0)returnERROR;//队列空head=(Q.rear-Q.length+1)%MAX;x=Q.base[head];Q.length--;returnOK;}intInitQueue(SqQueue&Q){//构造一个空循环队列QQ.base=newElemType[MAX];if(!Q.base)exit(OVERFLOW);Q.rear=0;Q.length=0;returnOK;66 }习题41.名词解释：串、空串、空格串、子串。解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。空串是不含任何字符的串，其长度为0。66 空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。串中任意连续的若干字符组成的子序列称为该串的子串。2.已知三个字符串分别为，，。利用串的基本运算得到结果串为，要求写出得到结果串所用的函数及执行算法。解：串可看作由以下两部分组成：和，设这两部分分别叫串s1和s2，要设法从、、中得到这两部分，然后使用连接操作连接s1和s2得到。i=index();//s1=substr(,i,length()-i+1);//取出串s1j=index(,);//求串在串中的起始位置，串中后是s2=substr(,j+3,length()-j-2);//形成串s2=concat(s1,s2);3.已知字符串中存放一段英文，写出算法，将其按给定的长度格式化成两端对齐的字符串，其多余的字符存入。解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n格式化为两端对齐的字符串”，即长度为n且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n，第n个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。voidformat(char*S1,char*S2,char*S3,intn){char*p=S1,*q=S2;inti=0;while(*p!=""&&*p=="")p++;//滤掉S1左端空格if(*p==""){printf("字符串S1为空串或空格串n");exit(0);}while(*p!=""&&it[0]){//找到了与t匹配的子串for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]];//左移删除s[0]-=t[0];num++;}}//for}//Delete_SubString6.编写算法，实现堆存储结构的串的置换操作Replace(&S,T,V)。解：voidHString_Replace(HString&S,HStringT,HStringV,int&num){//堆结构串上的置换操作,返回置换次数66 inti,j,k,m;for(i=0;i<=S.length-T.length;i++){for(j=i,k=0;k=i+T.length;m--)S.ch[m+V.length-T.length]=S.ch[m];for(m=0;mch[i]);//将前半段的字符入串elseif(k>(S.curlen+1)/2){Pop(S,c);//将后半段的字符与栈中的元素相匹配if(p->ch[i]!=c)return0;//失配}if(++i==CHUNKSIZE){//转到下一个元素,当为块中最后一个元素时,转到下一块p=p->next;i=0;}}//forreturn1;//成功匹配}//LString_Palindrome9.令，，试分别求出它们的next函数值和nextval函数值。解：j1234567串Sabcabaanext[j]0111232nextval[j]0110132J1234567891011121314151617181920串Tabcaabbabcabaacbacbanext[j]01112231234532211211Nextval[j]0110213011053221021010.已知主串，模式串，写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。解：j12345678910串Tadabbadadanextval[j]0102101040匹配过程略。66 习题51.假设有7行5列的二维数组A（下标从1开始），每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：(1)数组A共占用多少存储单元；(2)数组A的最后一个元素的地址；(3)按行存储时元素A53的地址；66 (4)按列存储时元素A53的地址。解：(1)数组A所占存储单元个数m=7*5*6=210。(2)数组A最后一个元素的地址d=1000+（5*7-1）*6=1204。(3)按行存储时元素A53的地址d53=1000+（4*5+2）*6=1132。(4)按列存储时元素A53的地址d53=1000+（4*7+2）*6=11802.若矩阵中的某个元素是第i行的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写求出矩阵中所有马鞍点的算法，并分析算法在最坏情况下的时间复杂度。解：算法思想：先找到一行的最小元素，然后扫描该元素所在的列，看他是否是该列的最大元素，若是则判为鞍点并输出，如此逐行进行处理直至完毕。voidGet_Saddle(intA[m][n]){//求矩阵A中的马鞍点for(i=0;iB.data[pb].j){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}else{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;}}//whilewhile(A.data[pa]==x){//插入A中剩余的元素(第x行)C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;}while(B.data[pb]==x){//插入B中剩余的元素(第x行)C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;66 }}//forC.tu=pc-1;}//TSMatrix_Add5.试编写以十字链表存储表示将稀疏矩阵B加到稀疏矩阵A上的算法。解：voidOLMatrix_Add(OLMatrix&A,OLMatrixB){//把十字链表表示的矩阵B加到A上for(j=1;j<=A.nu;j++)cp[j]=A.chead[j];//向量cp存储每一列当前最后一个元素的指针for(i=1;i<=A.mu;i++){pa=A.rhead[i];pb=B.rhead[i];pre=NULL;while(pb){if(pa==NULL||pa->j>pb->j){//新插入一个结点p=(OLNode*)malloc(sizeof(OLNode));if(!pre)A.rhead[i]=p;elsepre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e;//插入行链表中if(!A.chead[p->j]){A.chead[p->j]=p;p->down=NULL;}else{while(cp[p->j]->down)cp[p->j]=cp[p->j]->down;p->down=cp[p->j]->down;cp[p->j]->down=p;}cp[p->j]=p;//插入列链表中}//ifelseif(pa->jj){pre=pa;pa=pa->right;}//pa右移一步elseif(pa->e+pb->e){pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;}//直接相加else{66 if(!pre)A.rhead[i]=pa->right;elsepre->right=pa->right;p=pa;pa=pa->right;//从行链表中删除if(A.chead[p->j]==p)A.chead[p->j]=cp[p->j]=p->down;elsecp[p->j]->down=p->down;//从列链表中删除free(p);}//else}//while}//for}//OLMatrix_Add6.求下列广义表操作的结果：(1)GetHead((a,b),(c,d))(2)GetTail(a,b,(c,d))(3)GetHead(GetTail((a,b),(c,d)))(4)GetTail(GetHead(a,b,(c,d)))(5)GetTail(GetHead(GetTail(a,(b,(c,d)))))解：(1)(a,b)；(2)(b,(c,d))；(3)(c,d)；(4)NULL；(5)((c,d))。7.利用广义表的GetHead和GetTail操作将原子b分别从下列广义表中分离出来。(1)((a,b),(c,d))(2)(a,b,(c,d))(3)(a,(b,(c,d)))(4)((a,b,c),d,(e,f))解：(1)GetHead(GetTail(GetHead((a,b),(c,d))))。(2)GetHead(GetTail(a,b,(c,d)))。(3)GetHead(GetHead(GetTail(a,(b,(c,d)))))。(4)GetHead(GetTail(GetHead((a,b,c),d,(e,f))))8.画出下列广义表的两种存储结构图((),a,(b,(c,d)),(e,f))解：略。9.按教材中广义表的类型定义写出求广义表的表头和表尾的算法。解：(1)求表头GListGetHead(GListL){//初始条件:广义表L存在。操作结果:取广义表L的头GListh;h=NULL;66 if(!L||L->tag==LIST&&!L->ptr.hp){printf("空表无表头!");returnNULL;}h=(GList)malloc(sizeof(GLNode));if(!h)printf("error");h->tag=L->ptr.hp->tag;h->ptr.tp=NULL;if(h->tag==ATOM)h->atom=L->ptr.hp->atom;elseCopyGList(h->ptr.hp,L->ptr.hp);returnh;}(2)求表尾GListGetTail(GListL){//初始条件:广义表L存在。操作结果:取广义表L的尾GListT;if(!L){printf("空表无表尾!");returnNULL;}T=(GList)malloc(sizeof(GLNode));if(!T)printf("error");T->tag=LIST;T->ptr.tp=NULL;CopyGList(T->ptr.hp,L->ptr.tp->ptr.hp);returnT;}10.按教材中广义表的类型定义写出求复制广义表的递归算法。解：intCopyGList(Glist&T,GlistL){if(!L)T=NULL;else{if(!(T=(GList)malloc(sizeof(GLNode))))exit(OVERFLOW);T->tag=L->tag;66 if(L->tag==ATOM)T->atom=L->atom;else{CopyGList(T->ptr.hp,L->ptr.hp);CopyGList(T->ptr.tp,L->ptr.tp);}}returnOK;}CopyGList习题61.树与二叉树之间有什么区别与联系？解：树与二叉树逻辑上都是树形结构，区别有三点：（1）二叉树的度至多为2，树无此限制。（2）二叉树有左右子树之分，树无此限制。（3）二叉树允许为空，树一般不允许为空。二叉树不是树的特例。66 2.高度为的完全二叉树至少有多少个结点？至多有多少个结点？解：至少有个结点，至多有个结点。和结点数之间的关系是ëû+1。3.已知A[1..n]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？解：根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号为ëi/2û，故A[i]和A[j]的最近的共同祖先可如下求出：while(i/2!j/2)if(i>j)i=i/2;elsej=j/2;退出while后，若i/2=0，则最近共同祖先为根结点，否则共同祖先为i/2。4.已知A[1..n]是一棵顺序存储的完全二叉树，求序号最小的叶子结点的下标。解：根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是ën/2û，这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是ën/2û+1。5.一棵深度为L的满k叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：(1)各层的结点数是多少？(2)编号为n的结点的双亲结点(若存在)的编号是多少？(3)编号为n的结点的第i个孩子结点(若存在)的编号是多少？(4)编号为n的结点有左右兄弟结点的条件是什么？如果有，其右兄弟结点的编号是多少？解：(1)kh-1(h为层数)。(2)因为该树上每层上均有kh-1个结点，从根开始编号为1，则结点i的从右向左数第2个孩子的结点编号为ki。设n为结点i的子女，则关系式(i-1)*k+2ni*k+1成立，因i是整数，故结点n的双亲i的编号为ën/kû+1。(3)结点(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点n的第i个孩子的编号是(n-1)*k+1+i。(4)根据以上分析，结点n有右兄弟的条件是，它不仅双亲的从右边的第一个子女，即(n-1)%k!=0，其右兄弟编号是n+1。6.试证明，在具有n(n≥1)个结点的m叉树中，有n(m-1)+1个指针域是空的。解：具有n个结点的m叉树共用n*m个指针。除根结点外，其余n-1个结点均有指针所指，故空指针数为n*m-(n-1)=n*(m-1)+1。7.试找出满足下列条件的二叉树：(1)先序序列与后序序列相同；(2)中序序列与后序序列相同；(3)先序序列与中序序列相同；(4)中序序列与层次遍历序列相同。解：(1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。66 (2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。(3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。(4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。8.设有一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF。请画出这棵二叉树。解：按层次遍历，第一个结点（树不空）为根，该结点在中序序列中把序列分成左右两部分——左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若左子树为空，则层次序列中第二个结点为右子树的根。对右子树分析类似。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。解：HIDJKEBLFGCA。10.已知一棵二叉树的中序遍历序列为DGBAECHIF，后序遍历序列为：GDBEIHFCA。(1)试画出该二叉树；(2)试画出该二叉树的中序线索树；(3)试画出该二叉树对应的森林。解：（1）（2）略（3）66 11.设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短。解：字符A、B、C、D出现的次数为9、1、5、3。其哈夫曼编码如下：A：1，B：000，C：01，D：001。其哈夫曼树为：12.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树T中，写出计算该算术表达式值的算法。解：typedefstructNode{ElemTypedata;floatval;charoptr;//只取+、-、*、/structNode*lchild,*rchild}BiNode,*BiTree;floatPostEval(BiTreet){//以后序遍历算法求以二叉树表示的算术表达式的值floatlv,rv;if(t!=NULL){lv=PostEval(t->lchild);//rv=PostEval(t->rchild);//switch(t->optr){case"+":value=lv+rv;break;case"-":value=lv-rv;break;case"*":value=lv*rv;break;case"/":value=lv/rv;break;}}returnvalue;}66 13.假设二叉链表为二叉树的存储结构，编写判断给定的二叉树是否相似的算法。所谓二叉树t1和t2相似指的是：t1和t2都是空树；或者t1和t2的根结点是相似的，以及t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。解：intLike(BiTreet1,BiTreet2){intlike1,like2;if(t1==NULL&&t2==NULL)return1;elseif(t1==NULL||t2==NULL)return0;else{like1=Like(t1->lchild,t2->lchild);like2=Like(t1->rchild,t2->rchild);return(like1&like2);}}14.假设二叉链表为二叉树的存储结构，编写递归算法，将二叉树中所有结点的左、右子树相互交换。解：voidExchange(BiTree&t){if(t){BiTrees;s=t->lchild;t->lchild=t->rchild;t->rchild=s;Exchange(t->lchild);Exchange(t->rchild);}}15.编写求双亲表示法表示的树的深度的算法。解：intDepth(PTreet){intmaxdepth=0,i,temp,f;for(i=0;i-1){temp++;f=t.nodes[f].parent;}if(temp>maxdepth)maxdepth=temp;}returnmaxdepth;}16.假设二叉链表为二叉树的存储结构，编写按层次遍历方式计算二叉树结点个数的算法。66 解：intLevel(BiTreet){intnum=0;LinkQueueQ;BiTreep;if(t){InitQueue(Q);EnQueue(Q,t);while(!QueueEmpty(Q)){DeQueue(Q,p);num++;if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}//while}//ifreturnnum;}17.编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双向链表，算法返回头结点的指针。解：BiTreehead,pre;//全局变量链表头指针head，prevoidCreateLeafList(BiTreet){if(t){CreateLeafList(t->lchild);//中序遍历左子树if(t->lchild==NULL&&t->rchild==NULL)//叶子结点if(head==NULL){//第一个叶子结点head=newBiTNode;//生成头结点head->lchild=NULL;head->rchild=t;//头结点的左链为空，右链指向第一个叶子结点t->lchild=head;pre=t;//第一个叶子结点左链指向头结点，pre指向当前叶子结点}else{pre->rchild=t;t->lchild=pre;pre=t;};CreateLeafList(t->rchild);pre->rchild=NULL;}}18.假设二叉链表为二叉树的存储结构，编写算法，按照括号表示法输出二叉树的所有结点。解：其过程是：对于非空二叉树t，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“（”符号，然后递归处理左子树，输出一个“，”符号，递归处理右子树，最后输出一个“）”符号。66 voidDispBiTree(BiTreet){if(t){printf("%c",t->data);if(t->lchild!=NULL||t->rchild!=NULL){printf("(");DispBiTree(t->lchild);if(t->rchild!=NULL)printf(",");DispBiTree(t->rchild);printf(")");}}}19.假设二叉链表为二叉树的存储结构，编写算法，输出二叉树的所有叶子结点。解：voidDispLeaf(BiTreet){if(t){if(t->lchild==NULL&&t->rchild==NULL)printf("%c",t->data);DispLeaf(t->lchild);DispLeaf(t->rchild);}}20.假设二叉链表为二叉树的存储结构，编写算法，输出值为x的结点的所有祖先。解：intAncestor(BiTreet,ElemTypex){if(t==NULL)return0;if(t->data==x)return1;if(Ancestor(t->lchild,x)||Ancestor(t->rchild,x)){printf("%c",t->data);return1;}}21.假设二叉链表为二叉树的存储结构，编写算法，输出所有叶子结点到根结点的路径。解：利用后序非递归遍历的特点，将其中访问结点改为判断结点是否为叶子结点，若是，输出栈中所有结点值voidAllPathAncestor(BiTreet){66 BiTNode*St[100];BiTNode*p;intflag,i,top=-1;//栈指针初始化if(t){do{while(t){//t的所有左结点进栈top++;St[top]=t;t=t->lchild;}p=NULL;//p指向栈顶结点的前一个已访问的结点flag=1;//设置t的访问标记为已访问过while(top!=-1&&flag){t=St[top];//出栈if(t->rchild==p){if(t->lchild==NULL&&t->rchild==NULL){//若为叶子结点for(i=top;i>0;i--)printf("%c->",St[i]->data);//输出栈中所有结点printf("%cn",St[0]->data);}top--;p=t;//p指向刚访问过的结点}else{t=t->rchild;//t指向右孩子结点flag=0;//设置未访问标记}}}while(top!=-1);printf("n");}}22.编写算法，将二叉树的顺序存储结构转化为二叉链表存储结构。解：typedefcharElemType;typedefstruct{//结点结构ElemType*data;//数据元素66 intn;//左右孩子指针}SqBTree;BiTreeTrans(SqBTreea,inti){//数据元素放在数组a的从下标为1开始的单元中BiTreet;if(i>a.n)returnNULL;//当i大于a的结点个数if(a.data[i]=="#")returnNULL;//当i对于的结点为空t=newBiTNode;t->data=a.data[i];t->lchild=Trans(a,2*i);t->rchild=Trans(a,2*i+1);returnt;}23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。解：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若p左右子女均无，设其中序左线索指向其祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其右子女是p在后序下的前驱，若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，p在中序和后序下均无前驱。BiThrTreeInPostPre(BiThrTreet,BiThrTreep){BiThrNode*q;if(p->RTag==0)q=p->rchild;//若p有右子女，则右子女是其后序前驱elseif(p->LTag==0)q=p->lchild;//若p无右子女而有左子女，则左子女是其后序前驱elseif(p->lchild==NULL)q=NULL;//p是中序序列第一个结点，无后序前驱else{//顺左线索向上找p的祖先，若存在，再找祖先的左子女while(p->LTag==1&&p->lchild!=NULL)p=p->lchild;if(p->LTag==0)q=p->lchild;//p结点的祖先的左子女是其后序前驱elseq=NULL;//仅右单支树（p是叶子），已上到根结点，p结点无后序前驱}returnq;}24.写出按后序序列遍历中序线索二叉树的算法。解：BiThrTreeLeftMost(BiThrTreet){//求结点t的最左子孙的左线索BiThrTreep=t;while(p->LTag==0)p=p->lchild;66 if(p->lchild!=NULL&&p->lchild!=t)return(p->lchild);elsereturnNULL;}BiThrTreeRightMost(BiThrTreet){//求结点t的最右子孙的右线索BiThrTreep=t;while(p->RTag==0)p=p->rchild;if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild);elsereturnNULL;}intISRightChild(BiThrTreet,BiThrTree&father){//若t是father的右孩子，返回1，否则返回0father=LeftMost(t);if(father&&father->rchild==t)return1;elsereturn0;}voidPostOrderInThr(BiThrTreet){//后序遍历中序线索二叉树tBiThrTreefather,p=t->lchild;intflag;while(p!=t){while(p->LTag==0)p=p->lchild;//沿左分子向下if(p->RTag==0)flag=0;//左孩子为线索，右孩子为链，相当从左返回，p为叶子，相当从右返回elseflag=1;while(flag==1){printf("%c",p->data);//访问结点if(ISRightChild(p,father)){p=father;flag=1;}//修改p指向双亲else{//p是左孩子，用最右子孙的右线索找双亲p=RightMost(p);if(p&&p->RTag==1)flag=1;elseflag=0;}}//while(flag==1)if(flag==0&&p!=t)p=p->rchild;//转向当前结点的右分支}}25.已知中序线索二叉树T的右子树不空。设计算法，将s所指结点作为T的右子树的一个叶子结点插入进去，并使之成为T的右子树的(中序序列)第一个结点。66 解：若使新插入的结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左边的结点（设为p）处插入，使S成为结点p的左孩子。则S的前驱是T，后继是p。voidThrTreeInsert(BiThrTreeT,BiThrTreeS){BiThrTreep=T->rchild;//用p指向T的右子树中最左边的结点while(p->LTag==0)p=p->lchild;S->LTag=1;S->RTag=1;//S是叶子结点，其左右标记均为1S->lchild=p->lchild;S->rchild=p;//S的前驱是根结点T，后继是结点pp->lchild=S;p->LTag=0;//将p的左指针指向S，并修改左标记为0}26.写出在中序线索二叉树中找指定结点在中序下的前驱结点的算法。解：BiThrTreeInorderPre(BiThrTreep){BiThrTreeq;if(p->LTag==1)//结点的左子树为空，结点左指针域为左线索，指向其前驱return(p->lchild);else{q=p->lchild;//p结点左子树最右边结点时p结点的中序前驱while(q->RTag)q=q->rchild;returnq;}//if}习题71.对于图7-21所示的有向图，试给出：(1)该图每个顶点的入度和出度；(2)该图的邻接矩阵；(3)该图的邻接表；(4)该图的逆邻接表(5)该图的强连通分量。解：（1）12345666 顶点入度321122出度0223123（2）邻接矩阵（3）邻接表（4）逆邻接表（5）强连通分量2.对于图7-22所示的无向图，试给出：(1)该图的邻接矩阵；(2)该图的邻接表；(3)该图的多重邻接表(4)从顶点0出发的“深度优先”遍历序列；(5)从顶点0出发的“广度优先”遍历序列。解：（1）邻接矩阵66 （2）邻接表（3）多重邻接表（4）0，1，2，3。（5）0，1，2，3。3.试写一算法由图的邻接表存储得到图的十字链表存储。解：voidALGraphToOLGraph(ALGraphG1,OLGraph&G2){ArcNode*p;ArcBox*q;for(inti=0;inextarc){j=p->adjvex;q=newArcBox;q->tailvex=i;q->headvex=j;66 q->hlink=G2.xlist[j].firstin;q->tlink=G2.xlist[i].firstout;G2.xlist[j].firstin=q;G2.xlist[i].firstout=q;}}}4.试证明求最短路径的Dijkstra算法的正确性。解：dist[i]定义为从源点v到其它各点vi的仅经S中顶点的最短路径长度。其初始状态满足定义，且往S中每加入一个顶点，调整dist各分量值之后仍满足定义。5.采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为的简单路径的算法。解：intvisited[MAX];intDFSsearch(ALGraphG,intk,inta,intb){//为了方便，让a，b为结点在数组中的下标visited[a]=1;ArcNode*w=G.adjlist[a].firstarc;while(w){intu=w->adjvex;if(!visited[u]){if(k==1&&u==b)return1;elseif(k==1)w=w->nextarc;elseif(u==b)w=w->nextarc;elseif(DFSsearch(G,k-1,u,b))return1;elsereturn0;}}visited[a]=0;return0;}intfindpath(ALGraphG,intk,inta,intb){for(inti=0;iadjvex]++;p=p->nextarc;}}intS[100],top=-1;//栈初始化for(i=0;i-1){i=S[top];top--;//出栈newbh[i]=n--;//记录结点的拓扑逆序序号count++;for(p=G.adjlist[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k])){top++;S[top]=k;}}//for}//whileif(count0){sum=0;//sum表示通过本结点的路径数66 visited[i]=1;for(p=G.adjlist[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k])sum+=GetPathNum_Len(G,k,j,len-1);//剩余路径长度减一}//forvisited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中}//elsereturnsum;}8.已有邻接表表示的有向图G，编写算法求有向图中顶点到顶点的所有简单回路。解：voidGetAllPath(ALGraphG,intu,intv){//求有向图中到的所有简单回路ArcNode*p;intS[MAX],top=-1,visited[MAX],i;top++;S[top]=u;visited[u]=1;while(top>-1||p){p=G.adjlist[S[top]].firstarc;//第一个邻接点while(p!=NULL&&visited[p->adjvex]==1)p=p->nextarc;if(p==NULL)top--;//出栈else{i=p->adjvex;//取邻接点（编号）if(i==v){//找到从i到j的一条简单路径，输出for(intk=0;k<=top;k++)printf("%d",S[k]);printf("%dn",v);top--;}//ifelse{visited[i]=1;top++;S[top]=i;}//深度优先遍历}//else}//while}9.已知邻接表表示的无向图G，编写求其的连通分量的算法，要求输出每一个连通分量的结点。解：intvisited[MAX];voidDFS(ALGraphG,inti){ArcNode*p;visited[i]=1;printf("%d",i);//输出连通分量的结点66 p=G.adjlist[i].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}voidCount(ALGraphG){//求连通分量的个数inti,k=0;for(i=0;iadjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}visited[v]=0;//恢复顶点v}voidJudgeRoot(ALGraphG){inti;;for(i=0;imaxlen&&!G.adjlist[i].firstarc){//新的最长路径for(j=0;j<=len;j++)MLP[j]=path[j];//保存下来maxlen=len;}else{for(p=G.adjlist[i].firstarc;p;p=p->nextarc){j=p->adjvex;if(!visited[j])DFS(G,j,len+1);}}//elsepath[i]=0;visited[i]=0;}//DFSvoidGet_Longest_Path(ALGraphG){//求一个有向无环图中最长的路径inti,j;ArcNode*p;maxlen=0;for(i=0;iadjvex]++;p=p->nextarc;}}for(i=0;inextarc){dut=p->dut;if(ve[i]+dut>ve[p->adjvex])ve[p->adjvex]=ve[i]+dut;DFS1(G,p->adjvex);}}//DFS1voidDFS2(ALGraphG,inti){intdut;ArcNode*p;if(!G.adjlist[i].firstarc)vl[i]=ve[i];else{for(p=G.adjlist[i].firstarc;p;p=p->nextarc){DFS2(G,p->adjvex);dut=p->dut;if(vl[p->adjvex]-dutadjvex]-dut;}}//else}//DFS266 voidCritical_Path(ALGraphG){//利用深度优先遍历求网的关键路径inti;ArcNode*p;for(i=0;iadjvex]++;p=p->nextarc;}}for(i=0;i的算法。解：voidDeleteEdge(ALGraph&G,inti,intj){p=G.adjlist[i].firstarc;pre=NULL;//删除顶点i的边结点，pre是前驱指针while(p)if(p->adjvex==j){if(pre==NULL)G.adjlist[i].firstarc=p->nextarc;elsepre->nextarc=p->nextarc;deletep;p=NULL;}//释放结点空间else{pre=p;p=p->nextarc;}//沿链表继续查找p=G.adjlist[j].firstarc;pre=NULL;//删除顶点j的边结点while(p)if(p->adjvex==i){if(pre==NULL)G.adjlist[j].firstarc=p->nextarc;66 elsepre->nextarc=p->nextarc;deletep;p=NULL;}else{pre=p;p=p->nextarc;}}14.设有向图用邻接表表示，图中有个顶点，表示为1至，试写一算法求顶点()的入度。解：intcount(ALGraphG,intk){//结点k放在下标为k-1的单链表内intcount=0;for(i=0;iadjvex==k-1)count++;p=p->nextarc;}}//ifreturncount;//}15.假设一个有向图G用十字链表存储，试写一个判断该图是否有回路的算法。解：intindegree[MAX];intTopsor(OLGraphG){ArcBox*p;inttop=-1;//用作栈顶指针for(i=0;iheadvex==i)p=p->hlink;elsep=p->tlink;//找顶点i的邻接点}//while(p)}//forfor(i=0;itailvex==i)k=p->headvex;elsek=p->tailvex;//找顶点i的邻接点indegree[k]--;//邻接点入度减1if(indegree[k]==0){indegree[k]=top;top=k;}//入度为0的顶点入栈if(p->headvex==i)p=p->hlink;elsep=p->tlink;//找顶点i的下一个邻接点}//while(p)}//while(top<>0)if(md[u]+G.Edges[u][j]){d[j]=d[u]+G.Edges[u][j];p[j]=u;}}//forfor(i=0;idata.key=A[i];s->bf=0;s->lchild=NULL;s->rchild=NULL;InsertAVL(T,s);}}10.编写一个算法，输出在一棵二叉排序树中查找某个关键字经过的路径。解：voidPrintBST(BSTreeT,KeyTypekval){if(!T)exit(0);printf("%d",T->data.key);if(kval==T->data.key)exit(0);elseif(kvaldata.key)PrintBST(T->lchild,kval);elsePrintBST(T->rchild,kval);}11.编写一个算法，判断给定的二叉树是否是二叉排序树。解：intlast=0,flag=1;intIs_BSTree(BSTreeT){//判断二叉树T是否二叉排序树,是则返回1,否则返回066 if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data.keydata.key;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree12.编写一个算法，利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。解：voidInsert(SSTableL,ElemTypex){low=1;high=L.length;while(low<=high){mid=(low+high)/2;if(x.keyL.elem[mid].key)low=mid+1;elsereturn;}for(i=L.length;i>=low;i--)L.elem[i+1]=L.elem[i];L.elem[low]=x;return;}13.假设哈希表长为，哈希函数为H(key)，用链地址法解决冲突。试编写输入一组关键字并建立哈希表的算法。解：typedefstructNode{ElemTypedata;structNode*next;}Node,*Hlist;voidCreateHList(HlistL[],intm){intx,k;Node*s;for(inti=0;idata.key=x;66 s->next=L[k];L[k]=s;}}14.请分别为4种平衡化旋转构造四个关键字插入序列，使得在构造平衡二叉排序树时该旋转至少发生一次。解：(1)14，13，12，15，在插入12时需要进行一次LL型调整。(2)12，13，14，15，在插入14时需要进行一次RR型调整。(3)15，13，14，11，在插入14时需要进行一次LR型调整。(4)12，15，14，13，在插入12时需要进行一次RL型调整。15.写出从哈希表中删除关键字为的一个记录的算法，设哈希函数为H(key)，解决冲突的方法为链地址法。解：voidDelete(HlistL[],KeyTypek){inti;i=H(k);//用哈希函数确定关键字k的哈希地址if(!L[i]){printf("无被删除记录n");exit(0);}Node*p,*q;p=L[i];q=p;//p指向当前记录（关键字），q是p的前驱while(p&&p->data.key!=k){q=p;p=p->next;}if(!p){printf("无被删除记录");exit(0);}if(q==L[i]){L[i]=p->next;deletep;}//被删除关键字是链表中的第一个结点else{q->next=p->next;deletep;}}16.设二叉排序树的各元素值互不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。解：(1)递归算法voidDecPrint(BSTreeT){if(T){DecPrint(T->rchild);if(!T->lchild&&T->rchild)printf(T->data.key);DecPrint(T->lchild);}}(2)非递归算法voidDecPrint(BSTreeT){66 BSTreeS[MAX];//S是二叉排序树结点指针的栈，容量足够大inttop=0;while(T||top>0){while(T){S[++top]=T;T=T->rchild;}//沿右分支向下if(top>0){T=S[top--];if(!T->lchild&&T->rchild)printf(T->data.key);T=T->lchild;//去左分支}//if}//while}习题91.在各种排序方法中，哪些是稳定的？哪些是不稳定的？对不稳定的排序方法举出一个不稳定的例子。解：排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序折半插入排序二路插入排序表插入排序起泡排序直接选择排序希尔排序快速排序堆排序2-路归并排序基数排序稳定稳定稳定稳定稳定不稳定不稳定不稳定不稳定稳定稳定2,2,13,2,2,1(d=2，d=1)2,2,12,1,1(大顶堆)66 2.若不考虑基数排序，则排序的两种基本操作是什么？解：关键字的比较和记录的移动。3.外排序的基本操作是什么？解：生成有序归并段，归并。4.分别采用堆排序、快速排序、起泡排序和归并排序，对初始状态为有序的表，则最省时间的是哪种排序方法？最费时间的是哪种排序方法？解：起泡排序，快速排序。5.不受待排序初始序列的影响的排序算法是哪种？其时间复杂度是多少？解：简单选择排序，时间复杂度是。6.直接插入排序设置监视哨的作用是什么？解：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。7.从平均时间性能而言，哪种排序方法最佳？解：快速排序。8.设待排序的记录有10个，其关键字分别为{75，23，98，44，57，12，29，64，38，82}。手工执行以下排序算法(按字典序比较关键字的大小)，写出每一堂排序结束时的关键字的状态：(1)直接插入排序(2)折半插入排序(3)起泡排序(4)简单选择排序(5)快速排序(6)希尔排序(7)2-路归并排序(8)基数排序解：略9.已知记录序列R[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组C[1..n]，对每个记录R[i]，统计序列中关键字比它小的记录个数存于C[i]，则C[i]=0的记录必为关键字最小的记录，然后依C[i]值的大小对R中记录进行重新排列，试编写实现上述排序的算法。解：voidCount_Sort(intR[],intn){//计数排序算法intC[MAX];for(i=0;iR[i+1]，则将两者交换，以后重复上述二趟过程，直到整个数组有序。(1)试问排序结束的条件是什么？(2)编写一个实现上述排序过程的算法。解：voidOE_Sort(intR[],intn){//奇偶交换排序的算法change=1;while(change){change=0;for(i=1;iR[i+1]){temp=R[i];R[i]=R[i+1];R[i+1]=temp;change=1;}for(i=0;iR[i+1]){temp=R[i];R[i]=R[i+1];R[i+1]=temp;change=1;}}//while}//OE_Sort本算法的结束条件是连续两趟比较无交换发生。11.编写算法，对n个关键字取整数值的记录进行整理，使得所有关键字为负值的记录排在关键字为非负值的记录之前，要求：(1)采用顺序存储结构，至多使用一个记录的辅助存储空间。(2)算法的时间复杂度为。(3)讨论算法中记录的最大移动次数。解：voidDivide(intR[],intn){//把数组R中所有值为负的记录调到非负的记录之前low=0;high=n-1;while(low=0)high--;//以0作为虚拟的枢轴记录temp=R[low];R[low]=R[high];R[high]=temp;66 while(lowL.r[i].key)b[i].gt++;elseif(L.r[j].key