数据结构课后习题部分参考答案.doc 20页

'数据结构课后习题部分参考答案第一章一、选择题1．C2．C　3．A　4．D　5．B二、判断题1．╳2．╳3．╳4．╳　5．∨三、简答题1．常见逻辑结构：集合结构，数据元素之间的关系仅仅是属于同一个集合。线性结构，除第一个元素只有一个直接后继、最后一个元素只有一个直接前驱，其余元素有且只有唯一一个直接前驱、有且只有唯一一个直接后继，数据元素之间存在一对一的关系。树形结构，树中只有唯一一个根元素，除根元素之外，其余元素只有一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。图形结构，元素之间关系任意，数据元素之间存在多对多的关系。常用的存储结构：顺序存储，把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。通常用数组实现。链式存储，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。通常用指针来实现。除上述两种方法外，有时为了查找方便还采用索引存储方法和散列存储方法。索引存储：在存储结点信息的同时，还建立附加的索引表来标识结点的地址。散列存储：根据元素的关键码确定元素存储位置的存储方式。2．算法与程序的区别：程序不一定满足有穷性(如操作系统)；程序中的指令必须是机器可执行的，算法中的指令则无此限制；算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);数据结构+算法=程序。3．例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑结构——线形结构。那么我们怎样把这个表中的数据存储到里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录（顺序存储）还是随机存放各结点数据再用指针进行链接（链式存储）呢?这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。4．例如栈和队列，两个数据结构的逻辑结构和存储方式完全相同，只是对于运算（如插入、删除）的定义不同，两个结构具有显著不同的特性。5．语句频度（1）n-1（2）1（3）n(n+1)/2（4）n/2-1（5）100 6．时间复杂度（1）O(log3n)（2）O(n2)（3）O(n2)7．算法思想：P(x，n)=(…((anx+an-1)x+an-2)x+…+a1)x+a0语句：y=0;for(i=n;i>=0;i--)y=y*x+ai;函数：voidp(){floatx,y;intn,i,a;scanf("%f",&x);scanf("%d",&n);y=0;for(i=n;i>=0;i--){scanf("%d",&a);y=y*x+a;}printf("x=%4.2f,y=%6.4f",x,y);}第二章一、选择题1．A2．A　3．D　4．C　5．D6．B7．C　8．B　9．A　10．D11．B12．D二、判断题1．╳2．∨3．╳4．∨　5．╳　　6．∨　7．╳8．∨　9．∨　10．╳11．╳　12．╳三、算法设计题1．第一种方法（从后往前比较）：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后，插入该位置后面即可。　　在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。　　算法如下：voidInsertIncreaseList1(seqlist*L,datatypex){inti;if(L->elemnum==maxsize)printf("overflow");//L->elemnum中存放当前顺序表中的元素个数for(i=L->elemnum-1;i>=0&&L->data[i]>x;i--)L->data[i+1]=L->data[i];//从后往前比较并移动元素L->data[i+1]=x; L->elemnum++;}第二种方法（从前往后比较）：voidInsertIncreaseList2(seqlist*L,datatypex){inti,j;if(L->elemnum==maxsize)printf("overflow");i=0;while((i<=L->elemnum-1)&&(L->data[i]elemnum-1;j>=i;j--)L->data[j+1]=L->data[j];//腾位置L->data[i]=x;//插入L->elemnum++;}　　　2（思路同算法2-16）6（同1类似，最好也做一下。1是顺序存储，6是链式存储。做完同1比较一下）7（看算法2-17,尾插实现）第三章一、选择题1．C2．B　3．D　4．B　5．B6．C7．B　8．D　9．C　10．C二、判断题1．∨2．∨3．∨4．╳　5．╳　　三、简答题1循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"通常有两种方法：（1）另设一个变量num记录当前队列中的元素个数,当num==0时队空，num==maxsize时队满。（2）少用一个存储单元(即少存一个元素),队空条件为front==rear，队满条件为(rear+1)%maxsize==front。2．栈的特点是先进后出，队列的特点是先进先出。先进后出用栈；先进先出用队列。3．一个直接调用自己或通过一系列调用间接调用自己的过程称为递归。递归程序结构清晰，可读性强，而且容易用数学归纳法来证明程序的正确性。递归程序运行效率低，不论是耗费的计算时间还是占用的存储空间都比非递归程序要多。4．1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321（十四种可能）四、算法设计题1．思想：将一半字符入栈) 算法为：　//以下为顺序栈的存储结构定义　#defineStackSize100 //假定预分配的栈空间最多为100个元素　typedefcharDataType;//假定栈元素的数据类型为字符　typedefstruct{　　DataTypedata[StackSize];　　inttop;　}SeqStack; 　intIsHuiwen(char*t)　　{//判断t字符向量是否为回文，若是，返回1，否则返回0　　　SeqStacks;　　　inti,len;　　　chartemp;　　　InitStack(&s);　　　len=strlen(t);//求向量长度　　　for(i=0;i此树的WPL并非最小...那么此树就不是哈夫曼树...=>假设错误...=>结点数大于1的哈夫曼树不存在度为1的结点7.n0=n2+1,n=n0+n1+n2=n0+0+n0-1=2n0-18.用数学归纳法证明。结点数n=1时，成立；假定n<=m-1时成立，证明n=m时成立。9.解：设该树中的叶子数为n0个。该树中的总结点数为n个，则有：        n=n0+n1+n2+…+nm(1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：        n-1=0*n0+1*n1+2*n2+…+m*nm(2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm非终端结点数：n-n0=n1+n2+…+nm 10．2，n-1,n,1,n-111.2h–1,2h–113．Eb不aGcaDdJeaCaIgaFaBaHaKAD14．Eb不aAGcaKDdJeaDICaIgaBFaGHBaHaCKFADLKDd15． EGEb不aAGcaIJeaHCaJIgaBFaCBaFHaDKGAD16．解： (1)哈夫曼编码111111000000ab不acadeafaga0.0840.040.31040.20040.100.11040.160840.210840.410840.1260840.28160840.59160841.00哈夫曼编码树   根据上图可得编码表：　　　a:01　　　b:001　　　c:110　　　d:0001　　　e:111　　　f:10　　　g:0000　　(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：      2*0.31+3*0.16+3*0.10+4*0.08+3*0.11+2*0.20+4*0.04=2.61      2.61 /3=0.87=87%     其平均码长是等长码的87%。   所以平均压缩率为13%。四、算法设计题1.第一种方法（使用全局变量）：intn=0;voidnodenum1(BiTreeroot){if(root!=NULL){n++;nodenum1(root->lchild);nodenum1(root->rchild);}}第二种方法（不用全局变量）：求结点数的递归定义为：　　若为空树，结点数为0　　若只有根结点，则结点数为1；　　否则，结点数为根结点的左子树结点数+右子树结点数+1intnodenum2(BiTreeroot){if(root==NULL)return0;elsereturn(1+nodenum2(root->lchild)+nodenum2(root->rchild));}第六章一、选择题1．B3.B4.C5.(1)B(2)D　7.B　10.B二、判断题1．╳　2．∨　3．∨　4．╳　7．∨9.╳　11．╳　12．∨三、简答题1.(1)每个顶点入度和出度：　　ID(v1)=2　OD(v1)=1　　ID(v2)=2　OD(v2)=2　　ID(v3)=1　OD(v3)=3　　ID(v4)=3　OD(v4)=0ID(v5)=2　OD(v5)=3　　ID(v6)=1　OD(v6)=2(2)邻接矩阵：000100       101000       000111        000000        110100        010010(3)邻接表：13∧∧4∧∧1236∧∧544∧54∧∧2165∧∧22.(1)0110000       1001000       1001000        0110110       0001001        0001001       00001103∧∧2∧(2)V14∧∧1∧V2V34∧∧1∧V46∧∧5∧3∧2∧V57∧∧4∧V67∧∧4∧V76∧∧5∧(4)v1,v2,v4,v3,v5,v7,v6(5)v1,v2,v3,v4,v5,v6,v73.用邻接矩阵表示图时，矩阵元素的个数与顶点个数有关（矩阵元素的个数是顶点个数的平方），与边的条数无关（矩阵中非零元素的个数与边的条数有关）。四、算法设计题 8．（1）intPATHDFS(ALGraph*G，inti,intj){ 　　　//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0　　　EdgeNode*p；　　　visited[i]=TRUE；//标记vi已访问　　　p=G->adjlist[i].firstedge；//取vi边表的头指针　　　while(p){//依次搜索vi的邻接点vk，这里k=p->adjvex　　　　　if（!visited[p->adjvex])//若vk尚未被访问　　　　　　　if(p->adjvex==j)　　　　　　　　　return1;　　　　　　　elseruturnPATHDFS(g，p->adjvex,j);//则以Vk为出发点向纵深搜索　　　　　p=p->next；//找vi的下一邻接点　　　　}　　　return0;　　}//PATHDFS（2）intBFS(ALGraph*G，inti,intj)　　　　{//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0　　　　　inti；　　　　　CirQueueQ；//须将队列定义中DataType改为int　　　　　EdgeNode*p；　　　　　InitQueue(&Q)；//队列初始化　　　　　visited[i]=TRUE； 　　　　　EnQueue(&Q，i)；//vi已访问，将其人队。（实际上是将其序号人队）　　　　　while(!QueueEmpty(&Q)){//队非空则执行　　　　　　　i=DeQueue(&Q)；//相当于vi出队　　　　　　　p=G->adjlist[i].firstedge；//取vi的边表头指针　　　　　   while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)　　　　　　　　　　　　if(!visited[p->adjvex])//若vk未访问过　　　　　　　　　　　　　　if(p->adjvex==j)　　　　　　　　　　　　　　　　　　return1;　　　　　　　　　　　　　　else{　　　　　　　　　　　　　　　　　　visited[P->adjvex]=TRUE； 　　　　　　　　　　　　　　　　　　EnQueue(&Q，p->adjvex)；　　　　　　　　　　　　　　　　}//访问过的vk人队                       p=p->next；//找vi的下一邻接点                     }//endwhile           }//endwhile         return0;   }//endofpathBFS10．voidShortestPath(ALGraph*G,intP[],intD[]){intfinal[MaxVerNum],i,j,k,min; EdgeNode*s;final[0]=1;/*初始时集合S中只有0号顶点*/D[0]=0;P[0]=-1;/*0号顶点无前驱顶点，用-1表示*/for(i=1;in;i++){final[i]=0;D[i]=INFINITY;P[i]=0;/*P[i]存放i号顶点的前驱顶点*/}s=G->adjlist[0].firstedge;while(s!=NULL){D[s->adjvex]=s->weight;s=s->next;}for(i=1;in;i++)/*重复G->n-1次*/{min=INFINITY;for(k=0;kn;k++)if(final[k]==0&&D[k]adjlist[j].firstedge;while(s!=NULL){if((final[s->adjvex]==0)&&(D[j]+s->weightadjvex])){D[s->adjvex]=D[j]+s->weight;P[s->adjvex]=j;}s=s->next;}}}第七章一、选择题1．B2.C3.C4.C5.D6.B7.C8.D9.D10.D11.C12.D13.B二、判断题1．╳2.∨3.╳4.∨5.╳6.∨7.∨8.∨9.╳10.╳11.∨13.∨14.∨15.╳16.∨18.╳19.∨20.∨三、简答题1．答：　　　　　　 　　等概率情况下，查找成功的平均查找长度为：　　　　ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 　　查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5。２．解：(1)ASLSUCC=(1+2X2+3X3+4X3+5X2+6)/12=3.5(2)排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找ASLSUCC=(1+2X2+3X4+4X5)/12=37/12６．（1）012345678910111213141516AprAugDecFebJanMarMayJuneJulySepOctNovASLSUCC=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12ASLUNSUCC=(1+2+3+4+5+1+2+3+4+5+6+7+8+9)/14=60/14 (2)AprAug∧∧Dec∧Feb∧∧July∧JuneJanMay∧MarOct∧Nov∧Sep∧∧∧∧∧∧∧∧ASLSUCC=(7x1+4x2+1x3)/12=18/12ASLUNSUCC=12/14(按照平均查找长度的定义，“Ci”指的是：“关键字和给定值比较的个数”，则在用链地址处理冲突时，和“空指针”的比较不计在内。否则，ASLUNSUCC=（7x1+3x2+3x3+1x4)/14=26/14）手工计算等概率情况下查找成功的平均查找长度规则如下：ASLsucc＝ 其中Ci为置入每个元素时所需的比较次数手工计算等概率情况下查找不成功的平均查找长度规则如下：ASLunsucc＝ 其中Ci为函数取值为i时确定查找不成功时比较次数四、算法设计题1.解: typedefstruct{　　　KeyType key；　　　InfoTypeotherinfo；//此类型依赖于应用　　}NodeType；　typedefNodeTypeSeqList[n+1]；//n号单元用作哨兵　intSeqSearch(SeqlistR，KeyTypeK)　　　{//在顺序表R[0..n-1]中顺序查找关键字为K的结点，　　　　//成功时返回找到的结点位置，失败时返回-1　　　　inti；　　　　R[n].key=K；//设置哨兵　　　　i=0;while(R[i].key!=k)i++;/*从表前往后找*/　　　if(ih)return(0);m=(l+h)/2;if(a[m].key==kx)return(m);if(a[m].keykx)return(bs(a,l,m-1,kx));}3.解：voidbins(seqlist*L，datatypex)//seqlist为顺序表类型，datatype为元素类型,元素按关键字升序排列{intlow,high,mid,i;low=0;high=L->last;mid=(low+high)/2;while(low<=high){if(x.keydata[mid].key)high=mid-1;elselow=mid+1;mid=(low+high)/2;}for(i=L->last;i>=low;i--)L->data[i+1]=L->data[i]; L->data[low]=x;L->last++;}4.解：voidoutput(btree*t){if(t!=NULL){output(t->rchild);printf(“%d”,t->data);output(t->lchild);}}9.解：　　由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。　typedefBinTNode*DataType;//循环队列中元素为二叉树结点指针 　intBinSortStree(BinTreeT)　　{ CirQueueQ;　　　BinTNode*p;　　　if(!T)return1;//空树为二叉排序树　　　InitQueue(&Q);　　　EnQueue(&Q,T);　　　while(!QueueEmpty(&Q))　　　　{p=DeQueue(&Q);　　　　　if(p->lchild)　　　　　　if(p->datalchild->data)return-1;//不是二叉排序树　　　　　　elseEnQueue(&Q,p->lchild);　　　　　if(p->rchild)　　　　　　if(p->data>p->rchild->data)return-1;//不是二叉排序树　　　　　　elseEnQueue(&Q,p->rchild);　　　　}　　　return1;//是二叉排序树　　　}第八章一、选择题1.A2.C3.C4.D5.D6.C7.B8.C9.D10.C二、判断题1.╳2.╳3.╳4.╳5.╳6.∨7.╳8.∨9.∨10.╳三、简答题 1． 原序列：(Tim,Kay,Eva,Roy,Dot,Jon,Kim,Ann,Tom,Jim,Guy,Amy) （1） 直接插入排序 (Tim)KayEvaRoyDotJonKimAnnTomJimGuyAmy(KayTim)EvaRoyDotJonKimAnnTomJimGuyAmy(EvaKayTim)RoyDotJonKimAnnTomJimGuyAmy(EvaKayRoyTim)DotJonKimAnnTomJimGuyAmy(DotEvaKayRoyTim)JonKimAnnTomJimGuyAmy(DotEvaJonKayRoyTim)KimAnnTomJimGuyAmy(DotEvaJonKayKimRoyTim)AnnTomJimGuyAmy(AnnDotEvaJonKayKimRoyTim)TomJimGuyAmy(AnnDotEvaJonKayKimRoyTimTom)JimGuyAmy(AnnDotEvaJimJonKayKimRoyTimTom)GuyAmy(AnnDotEvaGuyJimJonKayKimRoyTimTom)Amy(AnnAmyDotEvaGuyJimJonKayKimRoyTimTom)（2） 冒泡排序 TimKayEvaRoyDotJonKimAnnTomJimGuyAmyAmyTimKayEvaRoyDotJonKimAnnTomJimGuyAmyAnnTimKayEvaRoyDotJonKimGuyTomJimAmyAnnDotTimKayEvaRoyGuyJonKimJimTomAmyAnnDotEvaTimKayGuyRoyJimJonKimTom AmyAnnDotEvaGuyTimKayJimRoyJonKimTom AmyAnnDotEvaGuyJimTimKayJonRoyKimTomAmyAnnDotEvaGuyJimJonTimKayKimRoyTom AmyAnnDotEvaGuyJimJonKayTimKimRoyTom AmyAnnDotEvaGuyJimJonKayKimTimRoyTom AmyAnnDotEvaGuyJimJonKayKimRoyTimTom  （3）选择排序 AmyKayEvaRoyDotJonKimAnnTomJimGuyTimAmyAnnEvaRoyDotJonKimKayTomJimGuyTimAmyAnnDotRoyEvaJonKimKayTomJimGuyTimAmyAnnDotEvaRoyJonKimKayTomJimGuyTimAmyAnnDotEvaGuyJonKimKayTomJimRoyTimAmyAnnDotEvaGuyJimKimKayTomJonRoyTimAmyAnnDotEvaGuyJimJonKayTomKimRoyTimAmyAnnDotEvaGuyJimJonKayTomKimRoyTimAmyAnnDotEvaGuyJimJonKayKimTomRoyTimAmyAnnDotEvaGuyJimJonKayKimRoyTomTimAmyAnnDotEvaGuyJimJonKayKimRoyTimTom（4）快速排序TimKayEvaRoyDotJonKimAnnTomJimGuyAmyAmyKayEvaRoyDotJonKimAnnGuyJimTimTomAmyKayEvaRoyDotJonKimAnnGuyJimTimTomAmyJimEvaGuyDotJonAnnKayKimRoyTimTom AmyAnnEvaGuyDotJimJonKayKimRoyTimTomAmyAnnEvaGuyDotJimJonKayKimRoyTimTomAmyAnnDotEvaGuyJimJonKayKimRoyTimTom（5）归并排序TimKayEvaRoyDotJonKimAnnTomJimGuyAmy(KayTim)(EvaRoy)(DotJon)(AnnKim)(JimTom)(AmyGuy)(EvaKayTimRoy)(AnnDotJonKim)(AmyGuyJimTom)(AnnDotEvaJonKayKimTimRoy)(AmyGuyJimTom)(AmyAnnDotEvaGuyJimJonKayKimRoyTimTom)（6）基数排序TimKayEvaRoyDotJonKimAnnTomJimGuyAmyEvaTimKimTomJimJonAnnDotKayRoyGuyAmyKayTimKimJimAmyAnnTomJonDotRoyGuyEvaAmyAnnDotEvaGuyJimJonKayKimRoyTimTom2．50，18，12，61，8，17，87，2587，61，50，25，8，17，12，18（初始堆）第一趟18，61，50，25，8，17，12，87第二趟12，25，50，18，8，17，61，87第三趟12，25，17，18，8，50，61，87第四趟8，18，17，12，25，50，61，87第五趟8，12，17，18，25，50，61，87第六趟8，12，17，18，25，50，61，87第七趟8，12，17，18，25，50，61，873．基数排序6．（1）堆同一般二叉树一样既可采用顺序存储，也可采用链接存储。但因为堆是一棵完全二叉 树，所以适宜采用顺序存储，这样能够充分利用其存储空间。 （2）堆顶（3）4n'