《数据结构课后习题答案(耿国华版.docx》由会员分享，可在线阅读，更多相关《数据结构课后习题答案(耿国华版.docx（17页珍藏版）》请在课桌文档上搜索。
1、第1章绪论2、(1)(2)(3)3、(1)A(2)C(3)Cf*骷下3中“日得语句频度for(j=ly=i;j+)for(k=l;k=j;k+)x=x+l;【解答】=+l得语句频度为：T(n)=1+(1+2)+(1+2+3)+.+(1+2+n)=n(n+l)(n2)6编写算法，求一元多项式p。(X)=a。+a,x+azX2+aXn得值P(X)并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数.注意：本题中得输入为a,(i=01,n)、X与n,输出为P。(x)。算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式
2、传递。讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(int,in;floatx,alp;printf(hn=,3;scanff%fj(fen);PrintfrX=;)seanf(tt%fx);for(i=0;in;i+)scanf
3、(%f,&ai;/*执行次数：n次P=aO;for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n次*/X=x*x;)printf(%f,p);)算法得时间复杂度：T(nMXn)通过参数表中得参数显式传递fIoatPolyValue(floata,floatx,intn)f1oatp,s;int;i9;for(=l;inext=S;BP-next=Pnext-next;CP-next=Snext;DSneXt=P-next;ES-nexl=L;FS-neXt=NULL;GQ=P;Hwhile(P-next!=Q)P=P-next;Iwhile(Pnext!=NULL)P=Pnext;
4、JP=Q;KP=L:1.L=S;ML=P;(3)D(5)D(6)A试分别以不同得存储结构实现单线表得就地逆置算法，即在原表得存储空间将线性表a,a)逆置为(a,a-,.,a)。【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num)i11tj;ElemTyPe【mp;for(j=0;jnext=NULL)return;*链表为空*/p=L-next;q=p-next;pnext=NULL;/*摘下第一个结点，生成初始逆置表*/whik(q!=NULL)/*从第二个结点起挨次头插入当前逆置表*/r=q-next;q-neXt=L-next;1.-next=q
5、;q=r;将线性表A=(al,a2,am),B=(bl,b2,bn)合并成线性表C,C=(al,bl,am,bm,bm+l,、bn)当mn时，线性表A、B、C以单链表作为存储结构，且C表利用A表与B表中得结点空间构成.注意：单链表得长度值m与n均未显式存储.【解答】算法如下：1.inkListmerge(LinkListA,LinkListBLinkListC)Node*pa,*qa,*pb,*qb,*p;pa=Anext;*pa表示A得当前结点*/pb=B-next;p=A;/利用P来指向新连接得表得表尾，初始值指向表A得头结点*/while(pa!=NULL&pb!=NULL)/利用尾插法
6、建立连接之后得链表*/qa=pa-nextqb=qbnext;p-next=pa;/咬替选择表A与表B中得结点连接到新链表中；*/P=P也pnext=pb;P=Pb;pa=qa;pb=qb;if(p!=NULDpnext=p；*A得长度大于B得长度*/if(pb!=NULL)p-next=pb;*B得长度大于A得长度*/C=A;Return(C)；实习题约瑟夫环问题约瑟夫问题得一种描述为:编号1,2,n得n个人按顺时针方向围坐一圈,每一个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时住手报数.报m得人出列，将她得密码作为新得m值，从她在顺时
7、针方向上得下一个人开始重新从1报数，如此下去，直至所有得人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构摹拟此过程，按照出列顺序打印出各人得编号。例如m得初值为20；n=7,7个人得密码挨次就是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,35【解答】算法如下：typfcfstroctNode(irtpesswOhiitnum；stnictNode*next；No*Liribtvet!JCSephis0(1.irtfctLNOde*p,*r,*q;intm,n,C,j；1.=(Node*)ma11oc(sizeof(Node);/*初始化单向循环链表*/
8、if(L=NULL)Pintfr链表申请不到空间！)；return；=NULL;r=Lrint请输入数据n得值(n)0):今SCanf(%d”,&nKfor(j=l：j=n：j+)*建立链表*/(p=(Node*)malloc(sizeof(Node)；ifp(!=MUL)(Printf(请输入第d个人得密码：scanf(%,&C)；ppassWord=C;p-nUm=j；next=r=p;p)next=L-next；print请输入第一个报数上限值m(m0):;) sc a n R%d.&m);n)；printf,出列得顺序为：nq=L;P=Lnext;while(n!=l)/针算出列得顺序
9、*/(j=LWhilenext;j+;)printf(dnum);m=ppassword;/获得新密码*/n-,qnext=pnext;*p出列r=p;p=p-next;free(r);printf(n-num);第3章限定性线性表一栈与队列第三章答案按3、1(b)所示铁道(两侧铁道均为单向行驶道)进行车箱调度，回答：(1)如进站得车箱序列为123,则可能得到得出站车箱序列就是什么？(2)如进站得车箱序列为123456,能否得到435612与135426得出站序列，并说明原因(即写出以“表示进栈、“表示出栈得栈序列操作)。【解答】(1)可能得到得出站车箱序列就是：123、132、213、231
10、、32k(2)不能得到435612得出站序列.因为有S(I)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“后进先出”得原则，出栈得顺序必须为X(2)X(1).能得到135426得出站序列。因为有S(I)X(I)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3给出栈得两种存储结构形式名称，在这两种栈得存储结构中如何判别栈空与栈满？【解答】(1)顺序栈(IoP用来存放栈顶元素得下标)判断栈S空：如果S-Xop=I表示栈空.判断栈S满：如果Stop=Stack_Size-1表示栈满。(2)链栈(top为栈顶指针，指向当前栈顶元素前面得
11、头结点)判断栈空：如果Iop-next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈得元素，此时栈满。4照四则运算加、减、乘、除与基运算得优先惯例，画出对下列表达式求值时操作数栈与运算符栈得变化过程：A-B*CD+ETF【解答】写一个算法，判断挨次读入得一个以为结束符得字母序列，就是否形如，序列1&序列2,得字符序列.序列1与序列2中都不含，且序列2就是序列1得逆序列.例如，,a+bfeba,就是属于该模式得字符序列，而1+&3-1，则不就是。【解答】算法如下：intIsHuiWenOStack*S;Charch,temp;InitStack(&S);PrintH”
12、请输入字符序列：0Ch=getchar();While(ch!=&)Push(fint=Q-front&tag=l)队满*/return(FALSE)；if(Q-front=Q-fint&tag=0)*x入队前队空，X入队后重新设置标志*/tag=bQ)dememtQoiear=x;Qrea=(Q-rear+1)%MXSIZE；产设置队尾指针*/Retum(TRUE)；出队算法：intDclctcQueue(ScqQueue*Q,QueueEIementType*x)*删除队头元素用X返回其值*/ilQ-frOnt=Q-rear&tag=O)/*队空*/return(FALSE)；*X=Qde
13、mentQ)front；Q-fr0nt=(Qfront+1)%MAXSIZE；/*重新设置队头指针*/if(Q一fint=Q-rear)tag=O;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE)；第4章串第四章答案1设S=IAMSTUEENTHGDq=WORKER，。给出下列操作得结果：【答】StrLength(s14;SubString(sub151，7)subl-IAMA；SubString(sub2,s,7,1)sub2=,；StrIndex(s,4,A)=6；StReplace(s,STUDENT,q);s=,IAMAWORKER,;SoCat(StrCat(S
14、ub1,tStCat(sub2,q)subl-IAMAGOODWORKERo2编写算法,实现串得基本操作StRcplace(S,T,V)。答】算法如下：intStrRep1Me(SStringS,SStringT,SStringV)/*用串V替换S中得所有子串T*/intpos,i;Pcs=StrWe(S,1,T);/*求S中子串T第一次浮现得位置*/if(p0s=0)retum(0X岫iIe()0s!=Q/*用串V替换S中得所有子串T*/(swifch(TIen-VxIen)(caseQ/*串T得长度等于串V得长度*/for(i=0;ichpos+i=Vchi;case0:*串T得长度大于串
15、V得长度*/得所有字符for(i=pos+t、ien；ilen=S-ch(j;前移T、Ien-V、Ien个位置*/T*/for(i=;Oichi;S-len=S-lenT、1en+Vlen；/*用V替case小于串V得长度*/Ien-TxIen+V、len)len-Tlen+V、Ien;i)=pos+Tlen;i)S-chi=S-chi-TIen+Vlen；ir(i=;OiV=V、len；i+)*用V替T*/S-chpos+i=Vchi;S-len=S-)len-Tlen+Vlen;Jelse产替后串长MAXLEZ,但串V可以全部替*/if(pos+V、len=pos+Tlen;-i)Schi
16、=s-)chiT、len+V、lenfor(i=0；ilen;i+)*用V替T*/Schpos+i=V、chi;SIen=MAXLEN;else*串V得部份字符要舍弃*/for(i=0：ichi；S-len=MAXLEN；*swith*/poS=StrIndex(S,PoS+V、len,T)；/*求S中下一个子串T得位置*/)*while()return(1)；)*StrReplace()*/第五章数组与广义表第五章答案1、假设有6行8列得二维数组A,每一个元素占用6个字节，存储器按字节编址。已知A得基地址为1000,计算：(1)数组A共占用多少字节；(288)(2数组A得最后一个元素得地址；
17、(1282(3按行存储时，元素A36得地址；(1126(4按列存储时,元素A36得地址；(11924、设有三对角矩阵A-，将其三条对角线上得元素逐行得存于数组B、3n-2中，使得Bn11k=,求：(1用i,j表示k得下标变换公式；(2用k表示i、j得下标变换公式.【解答】(l)k=2(i-l+j(2)i=k3+1,j=k3+%k3(取整,取余5、在稀疏矩阵得快速转置算法5、2中,将计算PoSitionocl得访法稍加改动,使算法只占用一个辅助向量空间。【解答】算法(一)FastTransposeTSMatrxi(TSMartrixA,TSMatrix*B)/*把矩阵A转置到B所指向得矩阵中去，
18、矩阵用三元组表表示*/intool,中，q；intpositionMAXSIZE；B)Ien=A、len;B-)n=A、m;Bm=A、n；iRBlenO)(position1=1;for(t=lllen;t+positinoA、datatcol+ll+;/*positionl存放第COl-I列非零元素得个数，即利用POs81来记录第811列中非零元素得个数*/*求COl列中第一个非零元素在B、data得位置存放在POSition18中IF/for(col=2;col=A、n;col+positioncol=posiioncol+positioncol-l;for(p=l；pA、len：p+Co
19、I=A、datapcol；q=positioncol;B-)dataq、row=Adatap、col;B-dataq、COI=A、datap、row；Bdataqe=Adatap、e;Positoin(co11+；)算法(二FastTranspoSeTSMatrix(TSMartrixA,TSMatrix*B)(intcol,t,p,q；intpositionMAXSIZE;B-Ien=Alen;B)n=Am；Bm=An;if(B-lenO(for(co1=1；COlV=A、n;col+)positionco11=0；for(t=1；tv=A、len;t+)positoinA、datat.1+
20、;*计算每一列得非零元素得个数*/*从最后一列起求每一列中第一个非零元素在B、data口中得位置，存放在POSitiOnaol中 */fbr(col=An,t=Alen;col0;col-)t=t-positionco1;positioncol=t+1;fbr(p=l;pdatapcol;q=positionco1;Bdataq、w=A、datap、cobB-dataq、col=A、datap、row;B-dataqe=Adatae;&蹩例产腰1研即f) 【解答】一种存储结构笫Positioncol+;A第二种存储结构9、求下列广义表运算得结果：(1)HEAD(ab),(c,d);(a,b)(
21、2)TAIL(a,b),(c,d);(c,d)(3)TAILHEAD(a,b),(c,d);(b)(4)HEADTAILHEAD(a,b),(c,d)J;b(5)Tailiheaditail(a,b),(c,d)jj；(d)第八早第六章答案6.1分别画出具有3个结点得树与3个结点得二叉树得所有不同形态。【解答】具有3个结点得树具有3个结点得二叉树6、3已知一棵度为k得树中有n,个度为1得结点，n2个度为2得结点，,n个度为k得结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则n=no+n+m树中分支数目为B,则B=n,+2n,+3n3+.+kn因为除根结点外，每一个结点均对应一个进
22、入它得分支，所以有n=B+l即n,+n+n=+2n+3n3+kn+l由卫式可得叶子结点数为：n=n,+2n,+(k-l)n+16、5已知二叉树有50个叶子结点，则该二叉树得总结点数至少应有多少个？【解答】nLChild;/植接利用线索*/else/*在P得左子树中查找“最右下端”结点*/for(q=p-LChild;q-Rtag=Oq=q-RChiId);Pre=qreturn(pre);找结点得中序后继结点BiTNode*InSucc(BiTNode*p)/*在中序线索二叉树中查找P得中序后继结点，并用SUCC指针返回结果*/if(p-Rtag=1)succ=p-RChild/植接利用线索*
23、/q=q-LChiId);/在P得右子树中查找“最左下端”结点*/for(q=pRChildq-Ltag=O;SUCretur(succ);(3)找结点得先序后继结点BiTNode*PreSucc(BiTNode*p)/*在先序线索二叉树中查找P得先序后继结点，并用SUCC指针返回结果*/if(-Ltag=0)succ=p-)LChild;elsesucc=pRChild;return(succ);)(4)找结点得后序前驱结点BiTNode*SuccPre(BiTNode*p)/*在后序线索二叉树中查找P得后序前驱结点,并用Pre指针返回结果*/if(pLtag=1)pre=pLChild:e
24、1sepre=p)RChild;retum(pre);)6、20已知二叉树按照二叉链表方式存储,利用栈得基本操作写出先序遍历非递归形式得算法。【解答】VoidPreOrder(BiTreeroot)/*先序遍历二叉树得非递归算法*/InitStack(&S)；p=root;while(p!=NULLI!IsEmpty(三)if(p!=WLL)(Visit(p-data)；push(&S,p)；p=p-LchiId；elsePop(&S,&p)；p=p-RChiId;6、26二叉树按照二叉链表方式存储,编写算法将二叉树摆布子树进行交换。【解答】算法(一)Voidexchage(BiTreeroo
25、t)(p=rt;if(pLChild!=NULLIp)RChild!=NULL)temp=p-LChildp-LChild=p-RChild:p-RChild=temp;exchange(p-LChild);exchange(p-RChild);算法(二)Voidexchange(BTreeroot)p=rootif(pLChild!=NULL11p-RChild!=NULL)jexchange(p-LChild);exchange(pRChild);temp=p-LChild;p-)LChiId=p-RChild;p-RChild=temp;第八章第八章答案8o1【解答】5/13694710ASL=(1+2X2+3X4+4X3)10=2、98、5【解答】ASL =(1+2X2+3X3+4X3+5X2+6)“2=3、5(2)排序为：AprAug,Dec,Feb,Jan,Juy,June,Mar,May,Nov,0ct,Sep哈希表为:0123456789102241300153461367冲突计算次数（1）(1)(1)(2)(6)折半查找ASLsicc=(1+2X2+3X4+4X5)12=37128、12【解答】ASLsnce=(1X4+2X3+6)8=2ASLNsiCc-(2+l+8+7+6+5+4+3+2+1+1)/11=40/11
