最新数据结构-c语言描述(第二版)答案-耿国华-西安电子科技大学.pdf

该【最新数据结构-c语言描述(第二版)答案-耿国华-西安电子科技大学 】是由【青山代下】上传分享，文档一共【17】页，该文档可以免费在线阅读，需要了解更多关于【最新数据结构-c语言描述(第二版)答案-耿国华-西安电子科技大学 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..第章绪论×(2)×(3)√3.(1)A(2)C(3)=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)/,求一元多项式p(x)=a+ax+ax2+…….+axn的值p(x),并确定算法中每一语n012nn0句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意:本题中的输入为a(i=0,1,…n)、x和n,输出为P(x)。算法的输入和输出采in0用下列方法(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;/*执行次数:n次*/x=x*x;}printf(“%f”,p);}算法的时间复杂度:T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn){floatp,s;inti;p=x;精品文档:..for(i=1;i<=n;i++){s=s+a[i]*p;/*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度:T(n)=O(n):(1)在顺序表中插入或删除一个元素,需要平均移动一半元素,具体移动的元素个数与插入或删除的位置有关。(2)线性表有顺序和链式两种存储结构。在顺序表中,线性表的长度在数组定义时就已经确定,是静态保存,在链式表中,整个链表由“头指针”来表示,单链表的长度是动态保存。(3)在顺序表中,逻辑上相邻的元素,其物理位置_一定_____相邻。在单链表中,逻辑上相邻的元素,其物理位置不一定相邻。(4)在带头结点的非空单链表中,头结点的存储位置由头指针指示,首元素结点的存储位置由头结点指示,除首元素结点外,其它任一元素结点的存储位置由其直接前趋的next域指示。(1)A(2)已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。:E、A。:H、L、I、E、A。:F、M。:L、J、A、G。供选择的语句有:AP->next=S;BP->next=P->next->next;CP->next=S->next;DS->next=P->next;ES->next=L;FS->next=NULL;GQ=P;Hwhile(P->next!=Q)P=P->next;Iwhile(P->next!=NULL)P=P->next;JP=Q;KP=L;LL=S;精品文档:..(3)D(4)D(5)D(6)A7试分别以不同的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表(a,a)逆置为(a,a,…,a)。12nnn-11【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num){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;if(L->next==NULL)return;/*链表为空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点,生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/{r=q->next;q->next=L->next;L->next=q;q=r;}}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;精品文档:..pb=qb;}if(pa!=NULL)p->next=pa;/*A的长度大于B的长度*/if(pb!=NULL)p->next=pb;/*B的长度大于A的长度*/C=A;Return(C);}约瑟夫环问题约瑟夫问题的一种描述为:编号的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));/*初始化单向循环链表*/链表申请不到空间L->next=NULL;r=L;请输入数据n的值for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){请输入第%d个人的密码p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;精品文档:..请输入第一个报数上限值出列的顺序为q=L;p=L->next;while(n!=1)/*计算出列的顺序*/{j=1;while(j<m)/*计算当前出列的人选p*/{q=p;/*q为当前结点p的前驱结点*/p=p->next;j++;}m=p->password;/*获得新密码*/n--;q->next=p->next;/*p出列*/r=p;p=p->next;free(r);}}(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答:(1)如进站的车厢序列为123,则可能得到的出站车厢序列是什么?(2)如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因(即写出以“S”表示进栈、“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)。3给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?【解答】(1)顺序栈(top用来存放栈顶元素的下标)判断栈S空:如果S->top==-1表示栈空。判断栈S满:如果S->top==Stack_Size-1表示栈满。(2)链栈(top为栈顶指针,指向当前栈顶元素前面的头结点)判断栈空:如果top->next==NULL表示栈空。判断栈满:当系统没有可用空间时,申请不到空间存放要进栈的元素,此时栈满。4照四则运算加、减、乘、除和幂运算的优先惯例,画出对下列表达式求值时操作数栈和运算符栈的变化过程:A-B*C/D+E↑F精品文档:..【解答】5写一个算法,判断依次读入的一个以@为结束符的字母序列,是否形如‘序列1&序列2’的字符序列。序列1和序列2中都不含‘&’,且序列2是序列1的逆序列。例如,是属于该模式的字符序列,而’1+3&3-1’则不是。【解答】算法如下:intIsHuiWen(){Stack*S;Charch,temp;InitStack(&S);Printf(“请输入字符序列:”);Ch=getchar();While(ch!=&)/*序列1入栈*/{Push(&S,ch);ch=getchar();}do/*判断序列2是否是序列1的逆序列*/{ch=getchar();Pop(&S,&temp);if(ch!=temp)/*序列2不是序列1的逆序列*/{return(FALSE);printf(“nNO”);}}while(ch!=@&&!IsEmpty(&S))if(ch==@&&IsEmpty(&S)){return(TRUE);printf(“nYES”);}/*序列2是序列1的逆序列*/else{return(FALSE);printf(“nNO”);}}/*IsHuiWen()*/8要求循环队列不损失一个空间全部都能得到利用,设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法。【解答】入队算法:intEnterQueue(SeqQueue*Q,QueueElementTypex){/*将元素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);}第章串1设,t=’GOOD’,q=’WORKER’。给出下列操作的结果:【解答】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*/{switch(-){case0:/*串T的长度等于串V的长度*/for(i=0;i<=;i++)/*用V替换T*/S->ch[pos+i]=[i];case>0:/*串T的长度大于串V的长度*/for(i=pos+;i<S->len;i--)/*将S中子串T后的所有字符S->ch[i-+]=S->ch[i];-*/for(i=0;i<=;i++)/*用V替换T*/S->ch[pos+i]=[i];精品文档:..S->len=S->len-+;case<0:/*串T的长度小于串V的长度*/if(S->len-+)<=MAXLEN/*插入后串长小于MAXLEN*/{/*-*/for(i=S->len-+;i>=pos+;i--)S->ch[i]=S->ch[i-+];for(i=0;i<=;i++)/*用V替换T*/S->ch[pos+i]=[i];S->len=S->len-+;}else{/*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+<=MAXLEN){for(i=MAXLEN-1;i>=pos+;i--)S->ch[i]=s->ch[i-+]for(i=0;i<=;i++)/*用V替换T*/S->ch[pos+i]=[i];S->len=MAXLEN;}else/*串V的部分字符要舍弃*/{for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+,T);/*求S中下一个子串T的位置*/}/*while()*/return(1);}/*StrReplace()*/,每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000,计算:(1)数组A共占用多少字节;(288)(2)数组A的最后一个元素的地址;(1282)(3)按行存储时,元素A36的地址;(1126)(4)按列存储时,元素A36的地址;(1192),将其三条对角线上的元素逐行的存于数组B[1..3n-2]中,使得n×nB[k]=a,求:(1)用i,j表示k的下标变换公式;(2)用k表示i、j的下标变换公式。ij【解答】(1)k=2(i-1)+j(2)i=[k/3]+1,j=[k/3]+k%3([]取整,%取余),将计算position[col]的方法稍加改动,使算法只占用一个辅助向量空间。【解答】算法(一)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){/*把矩阵A转置到B所指向的矩阵中去,矩阵用三元组表表示*/intcol,t,p,q;intposition[MAXSIZE];B->len=;B->n=;B->m=;if(B->len>0){精品文档:..position[1]=1;for(t=1;t<=;t++)position[[t].col+1]++;/*position[col]存放第col-1列非零元素的个数,即利用pos[col]来记录第col-1列中非零元素的个数*//*[]的位置,存放在position[col]中*/for(col=2;col<=;col++)position[col]=position[col]+position[col-1];for(p=1;p<;p++){col=[p].col;q=position[col];B->data[q].row=[p].col;B->data[q].col=[p].row;B->data[q].e=[p].e;Position[col]++;}}}算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){intcol,t,p,q;intposition[MAXSIZE];B->len=;B->n=;B->m=;if(B->len>0){for(col=1;col<=;col++)position[col]=0;for(t=1;t<=;t++)position[[t].col]++;/*计算每一列的非零元素的个数*//*[]中的位置,存放在position[col]中*/for(col=,t=;col>0;col--){t=t-position[col];position[col]=t+1;}for(p=1;p<;p++){col=[p].col;q=position[col];B->data[q].row=[p].col;B->data[q].col=[p].row;B->data[q].e=[p].e;Position[col]++;}}}:((((a),b)),(((),d),(e,f)))【解答】精品文档:..:(1)HEAD[((a,b),(c,d))];(a,b)(2)TAIL[((a,b),(c,d))];((c,d))(3)TAIL[HEAD[((a,b),(c,d))]];(b)(4)HEAD[TAIL[HEAD[((a,b),(c,d))]]];b(5)TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)。【解答】精品文档:..,n个度为2的结点,,n个度为k12k的结点,则该树中有多少个叶子结点?【解答】设树中结点总数为n,则n=n+n+……+n01k树中分支数目为B,则B=n+2n+3n+……+kn123k因为除根结点外,每个结点均对应一个进入它的分支,所以有n=B+1即n+n+……+n=n+2n+3n+……+kn+101k123k由上式可得叶子结点数为:n=n+2n+……+(k-1)n+,则该二叉树的总结点数至少应有多少个?【解答】n表示叶子结点数,n表示度为2的结点数,则n=n+10202所以n=n–1=49,当二叉树中没有度为1的结点时,总结点数n=n+n=:(1)前序序列与中序序列相同;(2)中序序列与后序序列相同;(3)前序序列与后序序列相同。【解答】(1)前序与中序相同:空树或缺左子树的单支树;(2)中序与后序相同:空树或缺右子树的单支树;(3)前序与后序相同:空树或只有根结点的二叉树。,字母在电文中出现的频率分别为:,,,,,,,。【解答】构造哈夫曼树如下:精品文档:..哈夫曼编码为:11111I:110015I:11110I:1026I:1110I:0137I:1101I:。【解答】精品文档:..,实现在中序线索二叉树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*(BiTNode*p)/*在中序线索二叉树中查找p的中序后继结点,指针返回结果*/{if(p->Rtag==1)=p->RChild;/*直接利用线索*/else{/*在p的右子树中查找“最左下端”结点*/for(q=p->RChild;q->Ltag==0;q=q->LChild);精品文档:..=q;}return();}(3)找结点的先序后继结点BiTNode*(BiTNode*p)/*在先序线索二叉树中查找p的先序后继结点,指针返回结果*/{if(p->Ltag==0)=p->LChild;=p->RChild;return();}(4)找结点的后序前驱结点BiTNode*Pre(BiTNode*p)/*在后序线索二叉树中查找p的后序前驱结点,并用pre指针返回结果*/{if(p->Ltag==1)pre=p->LChild;elsepre=p->RChild;return(pre);},利用栈的基本操作写出先序遍历非递归形式的算法。【解答】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;}}},编写算法将二叉树左右子树进行交换。【解答】算法(一)Voidexchange(BiTreeroot){p=root;if(p->LChild!=NULL||p->RChild!=NULL)精品文档:..{temp=p->LChild;p->LChild=p->RChild;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;}}【解答】5精品文档:..ASL=(1+2X2+3X4+4X3)/10=【解答】(1)ASL=(1+2X2+3X3+4X3+5X2+6)/12=(2)(3)排序为:Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找ASL=(1+2X2+3X4+4X5)/12=37/【解答】ASL=(1X4+2X3+6)/8=2精品文档:..ASL=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11精品文档