数据结构课后习题答案(耿国华版.docx

第1章绪论2、(1)×(2)×(3)3、(1)A(2)C(3)C'f*骷下"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)(n÷2)6编写算法，求一元多项式p。(X)=a。+a,x+azX2+aXn得值P(X)并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数.注意：本题中得输入为a,(i=01,n)、X与n,输出为P。(x)。算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式传递。讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(int,in;floatx,alp;printf(hn=,3;scanff%fj(fen);PrintfrX=")seanf(tt%fx);for(i=0;i<n;i+)scanf(%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;i<=n;i+)s=s+a i* p;P=P*x;)re turn(p);算法得时间复杂度：T(n)=O(n)t行次数：n次*/第2章线性表习题1、填空：(1)在顺序表中插入或者删除一个元素，需要平均挪移二生元素，具体挪移得元素个数与捷或者删除得位置有关。线性表有顺序与链式两种存储结构,在顺序表中,线性表得长度在数组定义时就已经确定，就是静态保存,在链式表中，整个链表由“头指针”来表示，单链表得长度就是动态保存。(3)在顺序表中，逻辑上相邻得元素，其物理位置二一相邻.在单链表中，逻辑上相邻得元素，其物理位置不一定相邻。(4)在带头结点得非空单链表中，头结点得存储位置由头指针指示，首元素结点得存储位置由头结点指示，除首元素结点外，其它任一元素结点得存储位置由其直接前趋得neXt域指示.2、选择题(I)A(2)已知L就是无表头结点得单链表，且P结点既不就是首元素结点，也不就是尾元素结点。按要求从下列语句中选择合适得语句序列.a、 在P结点后插入S结点得语句序列就是：E、A。b、 在P结点前插入S结点得语句序列就是：H、L、I、E、A。c、在表首插入S结点得语句序列就是；F、M。d、在表尾插入S结点得语句序列就是：L、J、A、G。供选择得语句有：AP>next=S;BP->next=P>next->next;CP->next=S>next;DS>neXt=P->next;ES->nexl=L;FS->neXt=NULL;GQ=P;Hwhile(P->next!=Q)P=P->next;Iwhile(P>next!=NULL)P=P>next;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;j<=(*num-1)/2;+)tmp=Lj1.j毛*num-j-l;1.*num-j1=tmp;J(2)用单链表作为存储结构voidinvert(LinkListL)Node*p,*q,*r;if(L>next=NULL)return;*链表为空*/p=L->next;q=p->next;p>next=NULL;/*摘下第一个结点，生成初始逆置表*/whik(q!=NULL)/*从第二个结点起挨次头插入当前逆置表*/r=q->next;q->neXt=L->next;1.->next=q;q=r;将线性表A=(al,a2,am),B=(bl,b2,bn)合并成线性表C,C=(al,bl,am,bm,bm+l,、bn)当m<=n时，或者C=(al,bl,an,bn,an+l,am)当m>n时，线性表A、B、C以单链表作为存储结构，且C表利用A表与B表中得结点空间构成.注意：单链表得长度值m与n均未显式存储.【解答】算法如下：1.inkListmerge(LinkListA,LinkListBLinkListC)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->nextqb=qb>next;p->next=pa;/咬替选择表A与表B中得结点连接到新链表中；*/P=P也p>next=pb;P=Pb;pa=qa;pb=qb;if(p!=NULDp>next=p；*A得长度大于B得长度*/if(pb!=NULL)p->next=pb;*B得长度大于A得长度*/C=A;Return(C)；实习题约瑟夫环问题约瑟夫问题得一种描述为:编号1,2,n得n个人按顺时针方向围坐一圈,每一个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时住手报数.报m得人出列，将她得密码作为新得m值，从她在顺时针方向上得下一个人开始重新从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);/*初始化单向循环链表*/if(L=NULL)Pintfr链表申请不到空间！")；return；1.>net=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)；p>passWord=C;p->nUm=j；next=r=p;p)next=L->next；print请输入第一个报数上限值m(m>0):") sc a n R'%d''.&m);n)；printf,出列得顺序为：nq=L;P=L>next;while(n!=l)/针算出列得顺序*/(j=LWhile<m)/*计算当前出列得人选P*/(q=P；*q为当前结点P得前驱结点*/p=p->next;j+;)printf(d>num);m=p>password;/获得新密码*/n-,q>next=p>next;*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、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满：如果S>top=Stack_Size-1表示栈满。(2)链栈(top为栈顶指针，指向当前栈顶元素前面得头结点)判断栈空：如果Iop->next=NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈得元素，此时栈满。4照四则运算加、减、乘、除与基运算得优先惯例，画出对下列表达式求值时操作数栈与运算符栈得变化过程：A-B*CD+ETF【解答】写一个算法，判断挨次读入得一个以为结束符得字母序列，就是否形如，序列1&序列2,得字符序列.序列1与序列2中都不含，且序列2就是序列1得逆序列.例如，,a+b<feb÷a,就是属于该模式得字符序列，而'1+&3-1，则不就是。【解答】算法如下：intIsHuiWenOStack*S;Charch,temp;InitStack(&S);PrintH”请输入字符序列：0Ch=getchar();While(ch!=&)Push(<feS,ch);ch=getchar();do1得逆序列*/ch=getchar(),Pop(&S,&temp);if(ch!=temp)序列1得逆序列*/retum(FALSE);while(ch!=if(ch=&&return(TRUE);是序列1得逆序列3*序列1入栈*/删断序列2就是否就是序列printf(nNO");&&!IsHmpty(&S)IsEmpty(&S)Printf(“YES”);/*序列2不就是/*序列2就e1sereturn(FALSE);printfnNo,);*IsHuiWen(*/8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为。或者1来区分头尾指针相同时得队列状态得空与满，请编写与此相应得入队与出队算法。L答】入队算法：intEntcrQueue(SeqQueue*Q,QueueE1emcntTypex)(产将元素X入队*/if(Q>fint=Q->front&&tag=l)队满*/return(FALSE)；if(Q->front=Q->fint&&tag=0)*x入队前队空，X入队后重新设置标志*/tag=bQ)dememtQoiear=x;Q>rea=(Q->rear+1)%MXSIZE；产设置队尾指针*/Retum(TRUE)；出队算法：intDclctcQueue(ScqQueue*Q,QueueEIementType*x)*删除队头元素用X返回其值*/ilQ->frOnt=Q->rear&&tag=O)/*队空*/return(FALSE)；*X=Q>dementQ)front；Q->fr0nt=(Qfront+1)%MAXSIZE；/*重新设置队头指针*/if(Q一>fint=Q->rear)tag=O;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE)；第4章串第四章答案1设S=IAMSTUEENTHGDq=WORKER，。给出下列操作得结果：【答】StrLength(s>14;SubString(sub151，7)subl-IAMA'；SubString(sub2,s,7,1)sub2=,；'StrIndex(s,4,'A')=6；StReplace(s,'STUDENT,q);s=,IAMAWORKER,;SoCat(StrCat(Sub1,tStCat(sub2,q)subl-IAMAGOODWORKER'o2编写算法,实现串得基本操作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(T>Ien-VxIen)(caseQ/*串T得长度等于串V得长度*/for(i=0;i<=V、1en;H-+)替*/S>chpos+i=Vchi;case0:*串T得长度大于串V得长度*/得所有字符for(i=pos+t、ien；i<Slen；i-)子串T后/*将S中S-)chit、len+v>len=S->ch(j;前移T、Ien-V、Ien个位置*/T*/for(i=;Oi<=Vlen；i+)Schpos+i=V>chi;S->len=S->lenT、1en+Vlen；/*用V替case小于串V得长度*/<0:/*串T得长度if(S->Ien-TxIen+V、len)<=MAXLEN*插入后串长小于MAXLEN*/*将S中子串T后得所有字符后移V、lenT、Ien个位置*/for(i=S->len-Tlen+V、Ien;i)=pos+T>len;i)S->chi=S->chi-T>Ien+V>len；ir(i=;OiV=V、len；i+)*用V替T*/S->chpos+i=Vchi;S->len=S-)len-T>len+V>len;Jelse产替后串长MAXLEZ,但串V可以全部替*/if(pos+V、len<=MAXLEN)fc(=iMAXLEN-1；i>=pos+T>len;-i)Schi=s-)chiT、len+V、lenfor(i=0；i<=V>len;i+)*用V替T*/S>chpos+i=V、chi;S>Ien=MAXLEN;else*串V得部份字符要舍弃*/for(i=0：i<MAXLENpos;i+)Schi+pos=V>chi；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得最后一个元素得地址；(1282(3按行存储时，元素A36得地址；(1126(4按列存储时,元素A36得地址；(11924、设有三对角矩阵A-，将其三条对角线上得元素逐行得存于数组B"、3n-2中，使得Bn×11k=,求：(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所指向得矩阵中去，矩阵用三元组表表示*/intool,中，q；intpositionMAXSIZE；B)Ien=A、len;B-)n=A、m;B>m=A、n；iRB>len>O)(position1=1;for(t=ll<=A>len;t+positinoA、datat>col+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+CoI=A、datapcol；q=positioncol;B-)dataq、row=Adatap、col;B->dataq、COI=A、datap、row；B>dataq>e=A>datap、e;Positoin(co11+；)算法(二FastTranspoSeTSMatrix(TSMartrixA,TSMatrix*B)(intcol,t,p,q；intpositionMAXSIZE;B->Ien=Alen;B)n=Am；B>m=An;if(B->len>O(for(co1=1；COlV=A、n;col+)positionco11=0；for(t=1；tv=A、len;t+)positoinA、datat.1+;*计算每一列得非零元素得个数*/*从最后一列起求每一列中第一个非零元素在B、data口中得位置，存放在POSitiOnaol中 */fbr(col=A>n,t=A>len;col>0;col-)t=t-positionco1;positioncol=t+1;fbr(p=l;p<A、Ien;p+)col=A>datap>col;q=positionco1;B>dataq、w=A、datap、cobB->dataq、col=A、datap、row;B->dataq>e=A>data>e;&蹩例产腰1研即f) 【解答】一种存储结构笫Positioncol+;A第二种存储结构9、求下列广义表运算得结果：(1)HEAD(ab),(c,d);(a,b)(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因为除根结点外，每一个结点均对应一个进入它得分支，所以有n=B+l即n,+n+n=+2n+3n3+kn+l由卫式可得叶子结点数为：n=n,+2n,÷+(k-l)n+16、5已知二叉树有50个叶子结点，则该二叉树得总结点数至少应有多少个？【解答】n<3表示叶子结点数，d表示度为2得结点数，则n。=n+1所以lb。1=49,当二叉树中没有度为1得结点时，总结点数n=ng+n,=996、6试分别找出满足以下条件得所有二叉树：(1)前序序列与中序序列相同；(2)中序序列与后序序列相同；(3)前序序列与后序序列相同。【解答】前序与中序相同：空树或者缺左子树得单支树；(2)中序与后序相同：空树或者缺右子树得单支树；(3)前序与后序相同：空树或者惟独根结点得二叉树.6、9假设通讯得电文仅由8个字母组成，字母在电文中浮现得频率分别为:0、07,0、19,0、02,0、06,0、32,0、03,0、21,0、10请为这8个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：哈夫曼编码为：1:11111I:11001:11110I：101:1110I:011:1101I.:00【解答】AA(6、16分别写出算法，实现在中序线索二叉树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=Oq=q->RChiId);Pre=qreturn(pre);找结点得中序后继结点BiTNode*InSucc(BiTNode*p)/*在中序线索二叉树中查找P得中序后继结点，并用SUCC指针返回结果*/if(p->Rtag=1)succ=p->RChild/植接利用线索*/q=q->LChiId);/在P得右子树中查找“最左下端”结点*/for(q=p>RChildq->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(p>Ltag=1)pre=pLChild:e1sepre=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(BiTreeroot)(p=rt;if(p>LChild!=NULLIp)RChild!=NULL)temp=p->LChildp->LChild=p->RChild:p->RChild=temp;exchange(p->LChild);exchange(p->RChild);算法(二)Voidexchange(BTreeroot)p=rootif(p>LChild!=NULL11p->RChild!=NULL)jexchange(p->LChild);exchange(p>RChild);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