数据结构课程课后习题的答案

...wd......wd......wd...?数据构造简明教程?练习题及参考答案练习题11.单项选择题〔1〕线性构造中数据元素之间是〔〕关系。A.一对多B.多对多C.多对一D.一对一答：D〔2〕数据构造中与所使用的计算机无关的是数据的〔〕构造。A.存储B.物理C.逻辑D.物理和存储答：C〔3〕算法分析的目的是〔〕。A.找出数据构造的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C〔4〕算法分析的两个主要方面是〔〕。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A〔5〕计算机算法指的是〔〕。A.计算方法B.排序方法C.求解问题的有限运算序列D.调度方法答：C〔6〕计算机算法必须具备输入、输出和〔〕等5个特性。A.可行性、可移植性和可扩大性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2.填空题〔1〕数据构造包括数据的①、数据的②和数据的③这三个方面的内容。答：①逻辑构造②存储构造③运算〔2〕数据构造按逻辑构造可分为两大类，它们分别是①和②。答：①线性构造②非线性构造〔3〕数据构造被形式地定义为〔D,R〕，其中D是①的有限集合，R是D上的②有限集合。答：①数据元素②关系〔4〕在线性构造中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。答：①没有②没有〔5〕在树形构造中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。答：①前驱②1③后继④任意多个〔6〕在图形构造中，每个结点的前驱结点数和后继结点数可以是〔〕。答：任意多个〔7〕数据的存储构造主要有四种，它们分别是①、②、③和④存储构造。答：①顺序②链式③索引④哈希〔8〕一个算法的效率可分为①效率和②效率。答：①时间②空间3.简答题〔1〕数据构造和数据类型两个概念之间有区别吗答：简单地说，数据构造定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。〔2〕简述线性构造、树形构造和图形构造的不同点。答：线性构造反映结点间的逻辑关系是一对一的，树形线性构造反映结点间的逻辑关系是一对多的，图在构造反映结点间的逻辑关系是多对多的。〔3〕设有采用二元组表示的数据逻辑构造S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开场结点，哪些结点是终端结点答：该逻辑构造为树形构造，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。〔4〕以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)。〔5〕分析下面程序段中循环语句的执行次数。intj=0,s=0,n=100;do{ j=j+1; s=s+10*j;}while(j<n&&s<n);答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，s=60。第4次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。〔6〕执行下面的语句时，语句s++的执行次数为多少ints=0;for(i=1;i<n-1;i++) for(j=n;j>=i;j--)s++;答：语句s的执行次数。〔7〕设n为问题规模，求以下算法的时间复杂度。voidfun1(intn){ intx=0,i; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++)x++;}答：其中x++语句属基本运算语句，=O(n2)。〔8〕设n为问题规模，是一个正偶数，试计算以下算法完毕时m的值，并给出该算法的时间复杂度。voidfun2(intn){ intm=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;}答：由，该程序段的时间复杂度为O(n2)。上机实验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。解：maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：#include<stdio.h>voidmaxs(inta[],intn,int&max1,int&max2){ inti; max1=max2=a[0]; for(i=1;i<n;i++) if(a[i]>max1) { max2=max1; max1=a[i]; } elseif(a[i]>max2) max2=a[i];}voidmain(){ inta[]={1,4,10,6,8,3,5,7,9,2}; intn=10; intmax1,max2;maxs(a,n,max1,max2); printf("最大元素值=%d,次大元素值=%d\n",max1,max2);}练习题21.单项选择题〔1〕数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序一样并且是连续的，称之为〔〕。A.存储构造B.逻辑构造C.顺序存储构造D.链式存储构造答：C〔2〕在n个结点的顺序表中，算法的时间复杂度是O〔1〕的操作是〔〕。A.访问第i个结点〔1≤i≤n〕和求第i〔2≤i≤n〕个结点的前驱结点B.在第i〔1≤i≤n〕个结点后插入一个新结点C.删除第i个结点〔1≤i≤n〕D.将n个结点从小到大排序答：A〔3〕向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动〔〕个元素。A.8B.63.5C.63D.7答：B〔4〕链式存储构造所占存储空间〔〕。A.分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针B.只有一局部，存放结点值C.只有一局部，存储表示结点间关系的指针D.分两局部，一局部存放结点值，另一局部存放结点所占单元数答：A〔5〕线性表假设采用链式存储构造时，要求内存中可用存储单元的地址〔〕。A.必须是连续的B.局部地址必须是连续的C.一定是不连续的D.连续或不连续都可以答：D〔6〕一个线性表在〔〕情况下适用于采用链式存储构造。A.需经常修改其中的结点值B.需不断对其进展删除插入C.其中含有大量的结点D.其中结点构造复杂答：B〔7〕单链表的存储密度〔〕A.大于1B.等于1C.小于1D.不能确定答：C2.填空题〔1〕在顺序表中插入或删除一个元素时，需要平均移动〔①〕元素，具体移动的元素个数与〔②〕有关。答：①表中一半②表长和该元素在表中的位置〔2〕向一个长度为n的顺序表的第i个元素〔1≤i≤n+1〕之前插入一个元素时，需向后移动〔〕个元素。答：n-i+1〔3〕向一个长度为n的顺序表中删除第i个元素〔1≤i≤n〕时，需向前移动〔〕个元素。答：n-i〔4〕在顺序表中访问任意一个元素的时间复杂度均为〔①〕，因此顺序表也称为〔②〕的数据构造。答：①O(1)②随机存取〔5〕顺序表中逻辑上相邻的元素的物理位置〔①〕相邻。单链表中逻辑上相邻的元素的物理位置〔②〕相邻。答：①一定②不一定〔6〕在带头结点的单链表中，除头结点外，任一结点的存储位置由〔〕指示。答：其前驱结点的链域的值〔7〕在含有n个数据结点的单链表中要删除结点*p，需找到它的〔①〕，其时间复杂度为〔②〕。答：①前驱结点的地址②O(n)〔8〕含有n〔n>1〕个结点的循环双向链表中，为空的指针域数为〔〕。答：03.简答题〔1〕试比较顺序存储构造和链式存储构造的优缺点。在什么情况下用顺序表比链表好答：顺序存储构造中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储构造中，相邻数据元素可随意存放，但所占存储空间分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。假设线性表的长度变化不大，且其主要操作是查找，那么采用顺序表；假设线性表的长度变化较大，且其主要操作是插入、删除操作，那么采用链表。〔2〕对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少删除一个元素所需要移动的平均个数为多少答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。〔3〕在链表中设置头结点的作用是什么答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作〔如插入和删除〕在各种情况下统一，从而简化了算法的实现过程。〔4〕对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。〔5〕某含有n〔n>1〕结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，那么采用以下哪种存储方式最节省运算时间。①单链表；②仅有头指针不带头结点的循环单链表；③双链表；④仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。4.算法设计题〔1〕设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。解：遍历顺序表L的前半局部元素，对于元素L.data[i]〔0≤i＜L.length/2〕，将其与后半局部对应元素L.data[L.length-i-1]进展交换。对应的算法如下：voidreverse(SqList&L){ inti; ElemTypex; for(i=0;i<L.length/2;i++) { x=L.data[i]; //L.data[i]与L.data[L.length-i-1]交换L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=x;}}本算法的时间复杂度为O(n)。〔2〕设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：对于顺序表L，用i从1开场遍历其元素，设L.data[0..j]〔j的初值为0〕中没有重复的元素。检测L.data[i]〔j<i<L.length〕，假设L.data[i]和L.data[0..j]中任何一个元素都不一样，那么将L.data[i]存入L.data[j+1]中。对应的算法如下：voiddelsame(SqList&L)//L为引用型参数{ inti,j=0,k; for(i=1;i<L.length;i++){ k=0; while(k<=j&&L.data[k]!=L.data[i]) k++; if(k>j) //表示L.data[i]和L.data[0..j]中所有元素都不一样{ j++; L.data[j]=L.data[i]; }}L.length=j+1;//顺序表长度置新值}本算法的时间复杂度为O(n2)，空间复杂度为O(1)。〔3〕设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data[0..0]，置e=L.data[0]，用i从1开场遍历L的所有元素：当L.data[i]≠e时，将它放在L.data[k]中，k增1，置e=L.data[i]，最后将L的length置为k。对应的算法如下：voiddelsame1(SqList&L) //L为引用型参数{ inti,k=1; //k保存不重复的元素个数 ElemTypee;e=L.data[0]; for(i=1;i<L.length;i++){ if(L.data[i]!=e) //只保存不重复的元素{ L.data[k]=L.data[i];k++; e=L.data[i]; } } L.length=k; //顺序表长度置新值}本算法是一个高效算法，其时间复杂度为O(n)，空间复杂度为O(1)。如果每次遇到重复的元素，都通过移动其后所有元素来删除它，这样的时间复杂度会变成O(n2)。〔4〕设计一个算法删除单链表L中第一个值为x的结点。解：用p、q遍历整个单链表，p指向*q的前驱结点，q用于查找第一个值为x的结点，当找到后将*q结点删除，返回1；否那么返回0。对应的算法如下：intdelx(SLink*&L,ElemTypex){ SLink*p=L,*q=p->next; //p指向*q的前驱结点 while(q!=NULL&&q->data!=x) { p=q; q=q->next; } if(q!=NULL) //找到值为x的结点 { p->next=q->next; free(q); return1; } elsereturn0; //未找到值为x的结点}〔5〕设计一个算法判定单链表L是否是递增的。解：判定链表L从第2个结点开场的每个结点的值是否比其前驱的值大。假设有一个不成立，那么整个链表便不是递增的；否那么是递增的。对应的算法如下：intincrease(SLink*L){ SLink*pre=L->next,*p; //pre指向第一个数据结点 p=pre->next; //p指向*pre结点的后继结点 while(p!=NULL) { if(p->data>=pre->data) //假设正序那么继续判断下一个结点 { pre=p; //pre、p同步后移 p=p->next; } elsereturn0; } return1;}〔6〕有一个整数元素建设的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建设新表A、B。用p遍历原单链表A的所有数据结点，假设为偶数结点，将其链到A中，假设为奇数结点，将其链到B中。对应的算法如下：voidSplit(SLink*&A,SLink*&B){SLink*p=A->next,*ra,*rb; ra=A; B=(SLink*)malloc(sizeof(SLink)); //建设头结点 rb=B; //r总是指向B链表的尾结点 while(p!=NULL) { if(p->data%2==0) //偶数结点 { ra->next=p; //将*p结点链到A中 ra=p; p=p->next; } else //奇数结点 { rb->next=p; //将*p结点链到B中 rb=p; p=p->next; } } ra->next=rb->next=NULL;}本算法的时间复杂度为O(n)，空间复杂度为O(1)。〔7〕有一个有序单链表〔从小到大排列〕，表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。解：先建设一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：voidinorderList(SLink*&L,ElemTypex){ SLink*s,*p,*q; s=(SLink*)malloc(sizeof(SLink));//建设一个待插入的结点 s->data=x;s->next=NULL; if(L==NULL||x<L->data) //假设单链表为空或x小于第1个结点date域 { s->next=L; //把*s结点插入到头结点之后L=s; } else { q=L; //寻找插入位置,p指向待比较的结点,q指向p的前驱结点 p=q->next; while(p!=NULL&&x>p->data) //假设x小于p所指结点的data域值 if(x>p->data) { q=p; p=p->next; } s->next=p; //将s结点插入到*q和*p之间 q->next=s;}}〔8〕有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：用p遍历单链表，用r遍历*p结点之后的结点，q始终指向*r结点的直接前驱结点，假设r->data==p->data，那么删除*r结点，否那么q、r同步后移一个结点。对应的算法如下：voiddels1(SLink*&L){ SLink*p=L->next,*q,*r,*t; while(p!=NULL) { q=p; r=q->next; while(r!=NULL) { if(r->data==p->data) //r指向被删结点 { t=r->next; q->next=t;free(r); r=t; } else { q=r;r=r->next; } } p=p->next; }}本算法的时间复杂度为O(n2)。〔9〕有一个递增有序单链表〔允许出现值域重复的结点〕，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：由于是有序表，所以一样值域的结点都是相邻的。用p遍历递增单链表，假设*p结点的值域等于其后结点的值域，那么删除后者。对应的算法如下：voiddels(SLink*&L){ SLink*p=L->next,*q; while(p->next!=NULL) { if(p->data==p->next->data) //找到重复值的结点 { q=p->next; //q指向这个重复值的结点 p->next=q->next; //删除*q结点 free(q); } elsep=p->next; }}本算法的时间复杂度为O(n)。〔10〕有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进展交换。解：先找到第一个元素值为x的结点*p，q指向其后继结点，此题是将*p结点移到*q结点之后，实现过程是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：intswap(DLink*L,ElemTypex){ DLink*p=L->next,*q; while(p!=NULL&&p->data!=x) p=p->next; if(p==NULL) //未找到值为x的结点 return0; else //找到值为x的结点*p { q=p->next; //q指向*p的后继结点 if(q!=NULL) //*p结点不是尾结点 { p->prior->next=q; //先删除*p结点 q->prior=p->prior; p->next=q->next; //将*p结点插入到*q结点之后 if(q->next!=NULL) q->next->prior=p; q->next=p; p->prior=q; return1; } else //*p结点是尾结点 return0; //无法与后继结点交换，返回0 }}〔11〕对于有n〔n≥1〕个数据结点的循环单链表L，设计一个算法将所有结点逆置。解：采用头插法重建循环单链表L的思路，先建设一个空的循环单链表，用p遍历所有数据结点，每次将*p结点插入到前端。对应的算法如下：voidReverse(SLink*&L){ SLink*p=L->next,*q; L->next=L; //建设一个空循环单链表 while(p!=L) { q=p->next; p->next=L->next; //将*p结点插入到前端 L->next=p; p=q; }}上机实验题2有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进展测试。#include<stdio.h>#include"SLink.h"voidUnion(SLink*L1,SLink*L2,SLink*&L3) //求并集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } else { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } while(q!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } tc->next=NULL;}voidInterSection(SLink*L1,SLink*L2,SLink*&L3) //求交集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) p=p->next; elseif(p->data>q->data) q=q->next; else //p->data=q->data { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } tc->next=NULL;}voidSubs(SLink*L1,SLink*L2,SLink*&L3) //求差集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) q=q->next; else //p->data=q->data { p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } tc->next=NULL;}voidmain(){ SLink*A,*B,*C,*D,*E; ElemTypea[]={1,3,6,8,10,20}; CreateListR(A,a,6); //尾插法建表 printf("集合A:");DispList(A); ElemTypeb[]={2,5,6,10,16,20,30}; CreateListR(B,b,7); //尾插法建表 printf("集合B:");DispList(B); printf("求A、B并集C\n"); Union(A,B,C); //求A、B并集C printf("集合C:");DispList(C); printf("求A、B交集C\n"); InterSection(A,B,D); //求A、B并集D printf("集合D:");DispList(D); printf("求A、B差集E\n"); Subs(A,B,E); //求A、B差集E printf("集合E:");DispList(E); DestroyList(A); DestroyList(B); DestroyList(C); DestroyList(D); DestroyList(E);}练习题31.单项选择题〔1〕栈中元素的进出原那么是〔〕。A.先进先出 B.后进先出C.栈空那么进D.栈满那么出答：B〔2〕设一个栈的进栈序列是A、B、C、D〔即元素A～D依次通过该栈〕，那么借助该栈所得到的输出序列不可能是〔〕。A.A,B,C,D B.D,C,B,AC.A,C,D,B D.D,A,B,C答：D〔3〕一个栈的进栈序列是a、b、c、d、e，那么栈的不可能的输出序列是〔〕。A.edcba B.decba C.dceab D.abcde答：C〔4〕一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i〔1≤i≤n〕那么第j〔1≤j≤n〕个出栈元素是〔〕。A.i B.n-iC.j-i+1D.不确定答：D〔5〕设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，那么判定st栈为栈空的条件为〔〕。A.st.top==-1 B.st.top!=-1C.st.top!=MaxSize D.st.top==MaxSize答：A〔6〕设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，那么判定st栈为栈满的条件是。A.st.top!=-1B.st.top==-1C.st.top!=MaxSize-1 D.st.top==MaxSize-1答：D〔7〕队列中元素的进出原那么是〔〕。A.先进先出B.后进先出C.栈空那么进D.栈满那么出答：A〔8〕元素A、B、C、D顺序连续进入队列qu后，队头元素是〔①〕，队尾元素是〔②〕。A.A B.BC.C D.D答：①A②D。〔9〕一个队列的入列序列为1234，那么队列可能的输出序列是〔〕。A.4321 B.1234C.1432 D.3241答：B〔10〕循环队列qu〔队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置〕的队满条件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontA.qu.rear==qu.front答：C〔11〕循环队列qu〔队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置〕的队空条件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D〔12〕设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r〔队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置〕，那么其元素个数为〔〕。A.r-f B.r-f-1C.(r-f)％N+1 D.(r-f+N)％N答：D〔13〕设有4个数据元素a、b、c和d，对其分别进展栈操作或队操作。在进栈或进队操作时，按a、b、c、d次序每次进入一个元素。假设栈或队的初始状态都是空。现要进展的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是〔①〕，第二次出栈得到的元素是〔②〕；类似地，考虑对这4个数据元素进展的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是〔③〕，第二次出队得到的元素是〔④〕。经操作后，最后在栈中或队中的元素还有〔⑤〕个。①～④：A.a B.b C.c D.d⑤： A.1 B.2 C.3 D.0答：①B②D③A④B⑤B〔14〕设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出后即进队列Q，假设6个元素出队的序列是e2、e4、e3、e6、e5、e1，那么栈S的容量至少应该是〔〕。A.5 B.4 C.3 D.2答：C2.填空题〔1〕栈是一种特殊的线性表，允许插入和删除运算的一端称为〔①〕。不允许插入和删除运算的一端称为〔②〕。答：①栈顶②栈底〔2〕一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为〔〕。答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。〔3〕有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈〔即C第一个且D第二个出栈〕的次序有〔〕。答：CDBAE、CDEBA、CDBEA。〔4〕顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，那么元素x进栈的操作是〔〕。答：data[top]=x;top++;〔5〕顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，那么出栈元素x的操作是〔〕。答：top--;x=data[top];〔6〕〔〕是被限定为只能在表的一端进展插入运算，在表的另一端进展删除运算的线性表。答：队列〔7〕设有数组A[0..m]作为循环队列的存储空间，front为队头指针〔它指向队首元素的前一位置〕，rear为队尾指针〔它指向队尾元素的位置〕，那么元素x执行入队的操作是〔〕。答：rear=(rear+1)%(m+1);A[rear]=x;〔8〕设有数组A[0..m]作为循环队列的存储空间，front为队头指针〔它指向队首元素的前一位置〕，rear为队尾指针〔它指向队尾元素的位置〕，那么元素出队并保存到x中的操作是〔〕。答：front=(front+1)%(m+1);x=A[rear];3.简答题〔1〕简要说明线性表、栈与队的异同点。答：一样点：都属地线性构造，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规那么不同，线性表为随机存取，而栈是只允许在一端进展插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进展插入、另一端进展删除运算，因而是先进先出表FIFO。②用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令存放及其他运算等等。〔2〕顺序队的“假溢出〞是怎样产生的如何知道循环队列是空还是满答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出〞。采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的方法如下：①设置一个布尔变量以区别队满还是队空；②浪费一个元素的空间，用于区别队满还是队空。③使用一个计数器记录队列中元素个数〔即队列长度〕。通常采用法②，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置，这样判断循环队列队空标志是：front=rear，队满标志是：(rear+1)%MaxSize=front。4.算法设计题〔1〕假设采用顺序栈存储构造，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成，不能直接用st.data[0]来得到栈底元素。解：假定采用顺序栈构造。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。对应算法如下：intGetBottom(SqStackst,ElemType&x){ ElemTypee;SqStacktmpst; //定义临时栈 InitStack(tmpst); //初始化临时栈 if(StackEmpty(st)) //空栈返回0 return0; while(!StackEmpty(st)) //临时栈tmpst中包含st栈中逆转元素 { Pop(st,x); Push(tmpst,x); } while(!StackEmpty(tmpst)) //恢复st栈中原来的内容 { Pop(tmpst,e); Push(st,e); } return1; //返回1表示成功}〔2〕设计一个算法，采用一个顺序栈逆向输出单链表L中所有元素。解：此题并不需要改变单链表L的构造。设置一个顺序栈st，先遍历单链表并将所有元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下：voidReverseDisp(SLink*L){ ElemTypex; structnode { ElemTypedata[MaxSize]; inttop; }st; //定义一个顺序栈 st.top=-1;SLink*p=L->next; while(p!=NULL) //遍历单链表，将所有元素进栈 { st.top++; st.data[st.top]=p->data; p=p->next; } while(st.top!=-1) //栈不空循环，输出栈中所有元素 { x=st.data[st.top]; st.top--; printf("%d",x); } printf("\n");}〔3〕设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空〔0〕或可能满〔1〕，这样加上front==rear可以作为队空或队满的条件。要求设计队列的相关基本运算算法。解：设计的队列的类型如下：typedefstruct{ ElemTypedata[MaxSize]; intfront,rear; //队头和队尾指针 inttag; //为0表示队空,为1时表示不空}QueueType;初始时tag=0，进展成功的插入操作后tag=1，进展成功的删除操作后tag=0；因为只有在插入操作后队列才有可能满，只有在删除操作后队列才有可能空，因此，这样的队列的基本要素如下：初始时：tag=0，front=rear队空条件：qu.front==qu.rear&&qu.tag==0队满条件：qu.front==qu.rear&&qu.tag==1对应的算法如下：//-----初始化队列算法-----voidInitQueue1(QueueType&qu){ qu.front=qu.rear=0; qu.tag=0; //为0表示队空可能为空}//-----判队空算法-----intQueueEmpty1(QueueTypequ){ return(qu.front==qu.rear&&qu.tag==0);}//-----判队满算法-----intQueueFull1(QueueTypequ){ return(qu.tag==1&&qu.front==qu.rear);}//-----进队算法-----intenQueue1(QueueType&qu,ElemTypex){ if(QueueFull1(qu)==1) //队满 return0; qu.rear=(qu.rear+1)%MaxSize;qu.data[qu.rear]=x;qu.tag=1; //至少有一个元素,可能满 return1;}//-----出队算法-----intdeQueue1(QueueType&qu,ElemType&x)//出队{ if(QueueEmpty1(qu)==1) //队空 return0; qu.front=(qu.front+1)%MaxSize;x=qu.data[qu.front];qu.tag=0; //出队一个元素,可能空 return1;}〔4〕假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，设计出相应的队初始化、进队、出队和判队空的算法。解：假设链队是不带头结点的循环单链表，其示意图如图3.1所示。队空条件：rear==NULL；进队操作：在*rear结点之后插入结点并让rear指向该结点；出队操作：删除*rear结点之后的一个结点。对应的算法如下：图3.1不带头结点的循环单链表表示队列typedefstructnode{ ElemTypedata; structnode*next;}QNode; //链队结点类型//-----初始化队列-----voidInitQueue(QNode*&rear){ rear=NULL;}//-----进队算法-----voidEnQueue(QNode*&rear,ElemTypex){ QNode*s; s=(QNode*)malloc(sizeof(QNode));//创立新结点 s->data=x; if(rear==NULL) //原链队为空 { s->next=s; //构成循环链表 rear=s; } else { s->next=rear->next; //将*s结点插入到*rear结点之后 rear->next=s; rear=s; //让rear指向这个新插入的结点 }}//-----出队算法-----intDeQueue(QNode*&rear,ElemType&x){ QNode*q; if(rear==NULL) //队空 return0; elseif(rear->next==rear) //原队中只有一个结点 { x=rear->data; free(rear); rear=NULL; } else //原队中有两个或以上的结点 { q=rear->next; x=q->data; rear->next=q->next; free(q); } return1;}//-----判队空算法-----intQueueEmpty(QNode*rear){ return(rear==NULL);}上机实验题3假设以I和O字符分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。设计一个算法判定所给的操作序列是否合法。假设合法返回1；否那么返回0。〔假设被判定的操作序列已存入一维数组中〕。并用相关数据进展测试。解：采用一个链栈来判断操作序列是否合法，其中str为存放操作序列的字符数组，n为该数组的元素个数〔这里的ElemType类型设定为char〕。对应的算法如下：#include<stdio.h>#include<malloc.h>typedefstructnode{ chardata; structnode*next;}LStack; //链栈结点类型voidInitStack(LStack*&ls) //初始化栈运算算法{ ls=NULL;}voidDestroyStack(LStack*&ls) //销毁栈运算算法{ LStack*pre=ls,*p; if(pre==NULL)return; //考虑空栈的情况 p=pre->next; while(p!=NULL) { free(pre); //释放*pre结点 pre=p;p=p->next; //pre、p同步后移 } free(pre); //释放尾结点}voidPush(LStack*&ls,charx) //进栈运算算法{ LStack*p; p=(LStack*)malloc(sizeof(LStack)); p->data=x; //创立结点*p用于存放x p->next=ls; //插入*p结点作为栈顶结点 ls=p;}intPop(LStack*&ls,char&x) //出栈运算算法{ LStack*p; if(ls==NULL) //栈空,下溢出返回0 return0; else //栈不空时出栈元素x并返回1 { p=ls; //p指向栈顶结点 x=p->data; //取栈顶元素x ls=p->next; //删除结点*p free(p); //释放*p结点 return1; }}intStackEmpty(LStack*ls) //判断栈空运算算法{ if(ls==NULL)return1; elsereturn0;}intjudge(charstr[],intn) //判断str序列的合法性{ inti,tag;charx;LStack*ls; InitStack(ls); //链栈ls初始化 for(i=0;i<n;i++) { if(str[i]=='I') //为I时进栈 Push(ls,str[i]); elseif(str[i]=='O') //为O时出栈 { if(StackEmpty(ls)) { DestroyStack(ls); return0; //栈空时返回0 } elsePop(ls,x); } else { DestroyStack(ls); return0; //其他值无效退出 } } tag=StackEmpty(ls); DestroyStack(ls); returntag; //栈为空时返回1,否那么返回0}voidmain(){ charstr1[]="IOIIOIOO"; charstr2[]="IOOIOIIO"; charstr3[]="IIIOIOIO"; charstr4[]="IIIOOIOO"; printf("各序列判断结果如下:\n"); printf("%s序列%s合法的\n",str1,judge(str1,8)?"是":"不是"); printf("%s序列%s合法的\n",str2,judge(str2,8)?"是":"不是"); printf("%s序列%s合法的\n",str3,judge(str3,8)?"是":"不是"); printf("%s序列%s合法的\n",str4,judge(str4,8)?"是":"不是");}练习题41.单项选择题〔1〕串是一种特殊的线性表，其特殊性表达在〔〕。A.可以顺序存储 B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符答：B〔2〕以下〔〕是"abcd321ABCD"串的子串。A.abcd B.321AB C."abcABC" D."21AB"答：D〔3〕两个串相等必有串长度相等且〔〕。A.串的各位置字符任意 B.串中各对应位置字符均相等C.两个串含有一样的字符 D.两个所含字符任意答：B2.填空题〔1〕空串是指〔①〕，空白串是指〔②〕。答：①不包含任何字符〔长度为0〕的串②由一个或多个空格〔仅由空格符〕组成的串〔2〕对于带头结点的链串s，串为空的条件是〔〕。答：s->next==NULL。〔3〕对于一个含有n个字符的链串s，查找第i个元素的算法的时间复杂度为〔〕。答：O(n)3.简答题〔1〕设s为一个长度为n的串，其中的字符各不一样，那么s中的互异的非平凡子串〔非空且不同于s本身〕的个数是多少答：由串s的特性可知，1个字符的子串有n个，2个字符的子串有n-1个，3个字符的子串有n-2个，…，n-2个字符的子串有3个，n-1个字符的子串有2个。所以，非平凡子串的个数=n+(n-1)+(n-2)+…+2=。〔2〕假设s1和s2为串，给出使s1//s2=s2//s1成立的所有可能的条件〔其中，“//〞表示两个串连接运算符〕。答：所有可能的条件为：〔1〕s1和s2为空串〔2〕s1或s2其中之一为空串〔3〕s1和s2为一样的串〔4〕假设两串长度不等，那么长串由整数个短串组成。4.算法设计题〔1〕设计一个算法RepChar(s,x,y)，将顺序串s中所有字符x替换成字符y。要求空间复杂度为O(1)。解：因要求算法空间复杂度为O(1)，所以只能对串s直接替换。从头开场遍历串s，一旦找到字符x便将其替换成y。对应算法如下：voidRepStr(SqString&s,charx,chary){ inti; for(i=0;i<s.length;i++) if(s.data[i]==x) s.data[i]=y;}〔2〕设计一个算法，判断链串s中所有元素是否为递增排列的。解：用p和q指向链串s的两个连续结点，p先指向开场结点，当q->data≥p->data时，p和q同步后移一个结点；否那么返回0。当所有元素是递增排列时返回1。对应算法如下：intincrease(LinkString*s){ LinkString*p=s->next,*q; if(p!=NULL) { while(p->next!=NULL) { q=p->next; //q指向*p的后续结点 if(q->data>=p->data) p=q; else //逆序时返回0 return0; } } return1;}〔3〕假设以链式构造存储一个串s，设计一个算法求串s中最长等值子串。解：假设串用带头结点的单链表存储串s。用max存放最大平台长度，扫描串s，计算一个平台的长度n，假设n大于max，那么置max为n。对应的算法如下：intmaxlength(LinkString*s){ intn,max=0;LinkString*p=s->next,*q; while(p!=NULL) { n=1; q=p;p=p->next; while(p!=NULL&&p->data==q->data) { n++; p=p->next; } if(n>max)max=n; } returnmax;}上机实验题4两个非空串s和t采用顺序存储构造存储，设计一个算法求这两个串最大公共子串，并用相关数据进展测试。解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下：#include<stdio.h>#include"SqString.h" //包含顺序串的基本运算函数SqStringmaxcomstr(SqStrings,SqStringt){ SqStringstr; intmidx=0,mlen=0,tlen,i=0,j,k; //用(midx,mlen)保存最大公共子串 while(i<s.length) //用i扫描串s { j=0; //用j扫描串t while(j<t.length) { if(s.data[i]==t.data[j]) //找一子串,在s中下标为i,长度为tlen { tlen=1; for(k=1;i+k<s.length&&j+k<t.length &&s.data[i+k]==t.data[j+k];k++) tlen++; if(tlen>mlen) //将较大长度者赋给midx与mlen { midx=i; mlen=tlen; } j+=tlen; //继续扫描t中第j+tlen字符之后的字符 } elsej++; } i++; //继续扫描s中第i字符之后的字符 } for(i=0;i<mlen;i++) //将最大公共子串复制到str中 str.data[i]=s.data[midx+i]; str.length=mlen; returnstr; //返回最大公共子串}voidmain(){ SqStrings,t,str; Assign(s,"aababcabcdabcde"); Assign(t,"aabcd"); printf("s:");DispStr(s); printf("t:");DispStr(t); printf("求s、t的最大公共子串str\n"); str=maxcomstr(s,t); printf("str:");DispStr(str);}练习题51.单项选择题〔1〕假设有60行70列的二维数组a[1..60,1..70]〔数组下标从1开场〕以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为〔〕。A.16902 B.16904 C.14454D.以上都不对答：A〔2〕对特殊矩阵采用压缩存储的目的主要是为了〔〕。A.表达变得简单 B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素 D.减少不必要的存储空间答：D〔3〕一个n×n的对称矩阵，如果采用压缩存储以行或列为主序放入内存，那么压缩存储的容量是〔〕。A.n2 B.n2/2 C.n(n+1)/2 D.(n+1)2/2答：C〔4〕设矩阵a是一个对称矩阵，为了节省存储，将其下三角局部按行序存放在一维数组b[1..n(n-1)/2]中〔数组下标均从1开场〕，对下三角局部中任一元素ai,j〔i≤j〕在一维数组b中下标k的值是〔〕。A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j答：B〔5〕有一个二维数组A，行下标的范围是0～8，列下标的范围是1～5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是〔①〕。假设按行存储，那么A[3,5]和A[5,3]的第一个字节的地址分别是〔②〕和〔③〕。假设按列存储，那么A[7,1]和A[2,4]的第一个字节的地址分别是〔④〕和〔⑤〕。A.28B.44C.76D.92E.108F.116G.132H.176I.184J.188答：①H②C③E④A⑤F〔6〕有一个二维数组A，行下标的范围是1～6，列下标的范围是0～7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是〔①〕个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，那么存储数组A的最后一个元素的第一个字节的地址是〔②〕。假设按行存储，那么A[2,4]的第一个字节的地址是〔③〕。假设按列存储，那么A[5,7]的第一个字节的地址是〔④〕。A.12 B.66 C.72 D.96 E.114 F.120G.156 H.234I.276J.282K.283L.288答：①L②J③C④I〔7〕稀疏矩阵一般的压缩存储方法有两种，即〔〕。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表答：C2.填空题〔1〕三维数组A[c1..d1,c2..d2,c3..d3]〔c1≤d1，c2≤d2，c3≤d3〕共含有〔〕个元素。答：(d1-c1+1)×(d2-c2+1)×(d3-c3+1)。〔2〕二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，那么A[i][j]的地址是〔〕。答：LOC(A[0][0])+(n×i+j)×k。〔3〕二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，那么A[6][12]的地址是〔〕。答：326〔4〕二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，那么A[18][9]的地址是〔〕。答：1208〔5〕有一个10阶对称矩阵A，采用压缩存储方式〔以行序为主存储下三角局部，且A[0][0]存放在B[1]中〕，那么A[8][5]在B中的地址是〔〕。答：42〔6〕设n阶下三角矩阵A[1..n][1..n]已压缩到一维数组S[1..n(n+1)/2]中，假设按行序为主存储，那么A[i][j]对应的S中的存储位置是〔〕。答：i(i-1)/2+j。〔7〕稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的〔〕。答：行下标、列下标和元素值3.算法设计题〔1〕假定数组A[0..n-1]的n个元素中有多个零元素，设计一个算法将A中所有的非零元素依次移到A的前端。解：从前向后找为零的元素A[i]，从后向前找非零的元素A[j]，将A[i]和A[j]进展交换。对应的算法如下：voidmove(ElemTypeA[],intn){ inti=0,j=n-1; ElemTypetmp;while(i<j) { while(A[i]!=0)i++; while(A[j]==0)j--; if(i<j) { tmp=A[i]; A[i]=A[j]; A[j]=tmp; } }}〔2〕一个n×n矩阵B按行优先存于一个一维数组A[0..n(n-1)]中，试给出一个就地算法将原矩阵转置后仍存于数组A中。解：矩阵转置是将矩阵中第i行第j列的元素与第j行第i列的元素互换位置。因此先应确定矩阵与一维数组的映射关系：bi,j在一维数组A中的下标为i～n+j，bj,i在一维数组A中的下标为j×n+i。对应的算法如下：voidtrans(ElemTypeA[],intn){ inti,j; ElemTypetmp; for(i=0;i<n;i++) for(j=0;j<i;j++) { tmp=A[i*n+j];A[i*n+j]=A[j*n+i]; A[j*n+i]=tmp;}}〔3〕如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，那么称之为该矩阵的一个马鞍点。设计一个算法求出m×n的矩阵A的所有马鞍点。解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，假设某元素既在min[i]中，又在max[j]中，那么该元素A[i][j]便是马鞍点，找出所有这样的元素，即找到了所有马鞍点。实现程序如下：#include<stdio.h>#definem3#definen4voidminmax(intA[m][n]){ inti,j,have=0;intmin[m],max[n]; for(i=0;i<m;i++) //计算出每行的最小值元素，放入min[m]之中 { min[i]=A[i][0]; for(j=1;j<n;j++) if(A[i][j]<min[i]) min[i]=A[i][j]; } for(j=0;j<n;j++) //计算出每列的最大值元素，放入max[1..n]之中{ max[j]=A[0][j]; for(i=1;i<m;i++) if(A[i][j]>max[j]) max[j]=A[i][j]; } for(i=0;i<m;i++) //判定是否为马鞍点 for(j=0;j<n;j++) if(min[i]==max[j]) { printf("(%d,%d):%d\n",i,j,A[i][j]);//显示马鞍点 have=1; } if(!have) printf("没有鞍点\n");}voidmain(){ inta[m][n]; inti,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); minmax(a); //调用minmax()找马鞍点}〔4〕设有二维数组A[m][n]，其元素为整数，每行每列都按从小到大有序，试给出一个算法求数组中值为x的元素的行号i和列号j。设值x在A中存在，要求比较次数不多于m+n次。解：由于算法要求比较次数不多于m+n次，因此不能按行扫描数组的每一元素，否那么比较次数在最坏情况下可达m×n次。根据该数组的特点可从矩阵右上角按副对角线方向向左下角查找，算法如下：intfind(inta[M][N],intx,intm,intn){ inti=0,j=n-1,flag=0;while(i<m&&j>=0) if(a[i][j]!=x) if(a[i][j]>x)j--; //修改列号 elsei++; //修改行号 else //a[i][j]==x { flag=1; break; } returnflag;}上机实验题5采用一维动态数组模拟二维数组的操作，即将一个二维数组的元素存放在一个一维数组中，一维数组的空间根据二维数组的大小动态分配。设计一个算法实现两个二维数组的相加运算。并用相关数据进展测试。解：对应的程序如下：#include<stdio.h>#include<malloc.h>typedefintElemType;typedefstruct{ ElemType*p; //存放二维数组元素 intm,n; //存放二维数组的行数和列数}Mat2;voidInitMat(Mat2&M,intx,inty) //初始化二维数组M{ M.m=x;M.n=y; M.p=(ElemType*)malloc(x*y*sizeof(ElemType));}intSetij(Mat2&M,inti,intj,ElemTypex) //置二维数组(i,j)位置值为x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j; M.p[k]=x; return1; //成功赋值返回1 } elsereturn0; //参数错误返回0}intGetij(Mat2M,inti,intj,ElemType&x) //取二维数组(i,j)位置值并赋给x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j;x=M.p[k]; return1; //成功取值返回1 } elsereturn0; //参数错误返回0}voidDispMat(Mat2M) //输出二维数组{ inti,j,k; for(i=0;i<M.m;i++){ for(j=0;j<M.n;j++) { k=i*M.n+j; printf("%3d",M.p[k]); } printf("\n"); }}intAddMat(Mat2A,Mat2B,Mat2&C) //两个二维数组相加运算{ inti,j;ElemTypex,y; if(A.m!=B.m||A.n!=B.n) return0; //两数组行列数不同返回0 for(i=0;i<A.m;i++) for(j=0;j<A.n;j++) { Getij(A,i,j,x);Getij(B,i,j,y); Setij(C,i,j,x+y);} return1;}voidDestroyMat(Mat2M) //销毁二维数组M{ free(M.p);}voidmain(){ Mat2A,B,C; InitMat(A,2,3); Setij(A,0,0,1);Setij(A,0,1,1);Setij(A,0,2,1); Setij(A,1,0,1);Setij(A,1,1,1);Setij(A,1,2,1);printf("A:\n");DispMat(A);InitMat(B,2,3); Setij(B,0,0,2);Setij(B,0,1,2);Setij(B,0,2,2); Setij(B,1,0,2);Setij(B,1,1,2);Setij(B,1,2,2);printf("B:\n");DispMat(B); InitMat(C,2,3);printf("C=A+B\n");AddMat(A,B,C); printf("C:\n");DispMat(C); DestroyMat(A); DestroyMat(B); DestroyMat(C);}练习题61.单项选择题〔1〕树最适合用来表示〔〕。A.有序数据元素 B.无序数据元素C.元素之间具有层次关系的数据 D.元素之间无联系的数据答：C〔2〕树是结点的有限集合，它〔①〕根结点，记为T。其余的结点分成为m〔m≥0〕个〔②〕的集合T1、T2、…、Tm，每个集合又都是树，此时结点T称为Ti的双亲结点，Ti称为T的子树〔1≤i≤m〕。一个结点的子