数据结构习题答案

《数据结构习题答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机科学与工程学院二OO五年三月目录第一章绪论3第二章线性表5第三章栈和队列9第三章串10第五章数组与广义表12第六章树和二叉树14第七章图18第八章查找22第九章内部排序24第一章绪论1.2.3综合题14、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;While(i<=n-1){@k+=10*I;i++;}答：n-1(2)i=1;k=0;do{@k+=10*I;i++;}while(I<=n-1);答：n-1(3)i=1;k=0;While(i<=n-1){i++;@k+=10*i;}答：n-1(4)k=0;for(i=1;i<=n;i++){for

2、(j=i;j<=n;j++)@k++;}答：(n+1)*n/2(5)for(i=1;i<=n;i++){for(j=i;j<=n;j++){for(k=1;k<=j;k++)@x+=delta;}答：1/6*n*(n+1)*(n+2)(6)i=1;j=0;While(i+j<=n){@if(i>j)j++;elsei++;}答：n(7)x=n;y=o;while(x>=(y+1)*(y+1)){@y++;}答：ëÖnû(1)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}答：11001.2.3综合题20、voidprint_desc

3、ending(intx,inty,intz)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(xy;//<->为表示交换的双目运算符,以下同if(yz;if(xy;//冒泡排序printf("%d%d%d",x,y,z);}//print_descending1.2.3综合题22试编写算法，计算i!.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中（I=1,2,….,n）。假设计算机中允许的整数最大值为maxint,则当n>arrsize或对某个k(1≤k≤n)使k!.2k>maxint时，应

4、按出错处理，注意选择你认为较好的出错处理方法。解：Statusalgo119(inta[ARRSIZE])//求i!*2^i序列的值且不超过maxint{  last=1;  for(i=1;i<=ARRSIZE;i++)  {a[i-1]=last*2*i;  if((a[i-1]/last)!=(2*i))reurnOVERFLOW;  last=a[i-1];  returnOK;  }}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.第二章线性表作业：2.2.2综合题3、编写一个函数将一个向量A（有n个元素且任何元素均不为0）分拆成两个向量

5、，使A中大于0的元素存放在B中，小于0的元素存放在C中。解：本题的算法思想是：依次遍历A的元素，比较当前的元素值，大于0者赋给B（假设有p个元素），小于0者赋给C（假设有q个元素）。实现本题功能的函数如下：voidret(vectorA，intn，vectorB，int*p，vectorC，int*q){inti；*p=0；*q=0；for(i=0；i<=n-1；i++){if(A[i]>0){(*p)++；B[*p]=A[i]；}if(A[i]<0){(*q)++；C[*q]=A[i]；}}}2.2.2综合题5、编写一个函数从一给定的向量A中删除元素值在x到y(x≤y)之间的所有元素，要

6、求以较高的效率来实现。解：本题的算法思想是：从0开始扫描向量A，以k记录下元素值在x到y之间的元素个数，对于不满足该条件的元素，前移k个位置。最后返回向量的新长度，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下：intdel(A，n，x，y)vectorA；intn;ElemTypex,y;{inti=0，k=0；while(i=x&&A[i]<=y)k++；elseA[i-k]=A[i];/*前移k个位置*/i++;}return(n-k);}2.2.2综合题8、有两个向量A（有m个元素）和B（有n个元素），其元素均以从小到大的升序

7、排列，编写一个函数将它们合并成一个向量C，要求C的元素也是以从小到大的升序排列。解：本题的算法思想是：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个向量扫描完毕，然后将未完的一个向量的余下所有元素赋给C即可。实现本题功能的函数如下：intlink(vectora,intm,vectorb,intn,vectorc){inti=0,j=0,l,k=0;while(i