数据结构(C语言版)习题解答

1、L3设n是正整数。试写出下列程序段中用记号标注的语句的频度:i=l；k=0;dok+=10*i;i+;while(iv=n-l)当n=l时，执行1；当n>=2时，执行n-l次；i=l;k=0;dok+=10*i;i-+;while(i=n);当n=2时,执行2次;当n!=2时,执行1次;i=l;j=0;while(i+j<n)if(i<j)i+;elsej+;)执行n次；x=n;y=0;/n是不小于1的常数while(x>=(y+l)*(y+l)y+；)执行(向下取整)(6) x=91;y=100;while(y>0)if(x>100)x-=10;y-;el

2、sex+;)If语句执行100次(7)for(i=0;ivn;i+)for(j=i;jvn;j+)for(k=j;kvn;k+)x+=2;过程：去，M第一早1 .3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素到La的合适位置上，保持该表的有序性。思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。StatusInsert_SqList(SqList&La,intx)/把x插入递增有力;表La中(if(La.Iength=La.listsize)returnERROR;for(i=La.Iength-1;La.elemi&

3、gt;x&&i>=0;i)La.elemi+l=La.elemi;La.elemi+l=x;La.Iength+;returnOK;/lnsert_SqList2 .5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表(ai,a2,an-1,an)逆置为(an,an-1,.,a2,a1)思路就是两个指示变量i,j同时分别从顺序表的开始和结尾处相向改变voidreverse(SqList&A)顺序表的就地逆置(ElemTypep;for(i=l,j=A.Iength;ivj;i+,j-)/A.elemi<->A.elemj;p=A.elemi

4、;A.elemi=A.elemj;A.elemj=p;/reverse2.7已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。int L. Ie ngth)voidDelete-SameElemCSqLink&L,呐层循环移动参数，中层循环寻找相同元，外层循环遍历整个表inti=0;intj=i+l;intlength=L.Iength;while(i<length)for(j=i+l;j<length;j+)if(L.EIemj=L.EIemil)for(k

5、=j;k<length-l;k+)L.Elemk=L.Elemk+1;length-j;移动元素后，由于少了一个元素，因此要减1/endifIf(L.EIemj>L.EIemi)break;/第二小问添加此句/endfor/endwhile/endfunctoion1 .8已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：L中数据元素无序排列；(2)L中数据元素非递减有序排列。(1) L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。StatusListDelete(Linklist&L

6、)/L是带头结点的线性表(ElemType*p,*q;p=L-next;q=p-next;设定p变化较慢，q变化较快while(p->next)while(q)if(p->data【一q->data)q=q->next;elseq=q->next;p->next=q;/else/whilep=p->next;q=p->next;开始后一结点的寻找returnOK;/ListDeleteL中数据元素非递减有序排列。思路：由于是有序的，遍历一次线性表就行了StatusListDelete(LinkList&L)ElemType*p,*q;p=

7、L->next;q=p->next;while(p->next)(if(p->data!=q->data)p=p->next;/和第一J可不同地方q=p->next;/ifelse(while(p->data=q->data)q=q->next;多个连续的重复值/elsep->next=q;p=q;q=p->next;删除值重复的结点，并修改相应的指针returnOK;/ListDelete2 .9设有两个非递减有序的单链表A,B。请写出算法，将3和B就地归并成一个按元素值非递增有序的单链表。将合并逆置后的结果放在c表中，

8、并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C)LinkListpa,pb,qa,qb;pa=A;Pb=B;qa=pa;/保存pa的前驱指针qb=pb;保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;while(pa&&pb)if(pa->data<pb->data)qa=pa;pa=pa->next;qa->n ext=A->n ext; A->n将当前最小结点插入A表表头e

9、xt=qa;elseqb=pb;pb=pb->next;将当前最小结点插入 A表表头qb->next=A->next;A->next=qb;while(pa)qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;while(pb)qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;pb=B;free(pb);returnOK;3 .13设以带头结点的双向循环链表表示的线性表L=(al,a2,a3,.,an)o试写一时间复杂度为0(n)的算法,将L

10、改造为L=(ai,a3,.,an,.,a4,a2)。voidReform(DuLinkedList&L)按1,3,5,心2的顺序重排双|可循环链表L中的所有结点(p=L.next;while(p->next!=L&&p->next->next!=L)(p->next=p->next->next;p=p->next;p指向最后一个奇数结点if(p-next=L)结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点p->next=L->pre->pre;else结点个数是偶数，使最后一个奇数结点next指

11、向最后一个偶数结点p->next=L->pre;p=p->next;此时p指向最后一个偶数结点while(p->pre->pre!=L)p->next=p->pre->pre;p=p->next;p-next=L;最后一个结点next指网头结点调整了next链的结构，此时pre链仍为原状调整pre链的结构for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p；头结点的pre指|句a2结点*/Reform第三章栈和队列4 .6试写一个算法，识别依次读入的一个以砂结

12、束符的字符序列是否为形如“序列序列2”模式的字符序列。其中，序列1和序列2中都不包含字符'且序列2是序列1的逆序。例如，"a+b&b+a，是属于该模式的字符序列，而“1+3&3一1”则不是。算法：intSeqReverse()判断输入的字符串中&前和&后部分是否为逆串，是则返回1,否则返回0(InitStack(s);while(e=getchar0)!=，&1)(if(e='0return0;/不允许在&'之刖出现'push(s,e);序列1输入完毕while(e=getchar()!='

13、9;)(if(StackEmpty(s)return0;pop(s,c);if(e!=c)return0;if(!StackEmpty(s)return0;序列1元素还有剩余return1;/lsReverse3.7假设一个算术表达式中可以包含三种符号:圆括号”("和")"、方括号和“”、花括号“和“”，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法(已知表达式已存入数据元素为字符的顺序表中)。算法:StatusBracketTest(char*str)判别表达式中二种括号是否匹配InitStack(s);for(p=str;*

14、p;p+)if(*p=*(，*p=T*p=*，)push(s,*p);elseP='')if(StackEmpty(s)returnERROR;pop(s,c);returnERROR;if(* p=T&&c!= V)return ERROR;if(*returnERROR;/必须与当前栈顶括号匹配/forif(!StackE mp ty(s)return ERROR; 进栈的符号还有剩余,ErrorreturnOK;/BracketTest3. 8设表达式由单字母变量、双目运算符和圆括号组成(如："(a*(b+c)-d)/e试写一个算法，将一个书写正

15、确的表达式转换为逆波兰式。思路:1 .遇到数字直接发送2.遇到'C直接入栈3遇到，)，则将栈内元素发送直至遇到则直接入栈5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈int Ran kOfO perator (char c)switch(c)casecasereturn1;0：casecasereturn1;returncase/casereturn2;')intPrecede(charc,charch)returnRankOfOperator(c)>RankOfOperator(ch);voidExpressionTOPolandStyle(charsuffixQ

16、,char*exp)Stacks;InitStack(s,100);inti=0;charc;while(*exp)if(isdigital(*suffixi+=*exp)elseswitchcasecaseexp;(*exp)'(：push(s,'(')；:while(c=pops(s)!=，('suffixi+=c;break;default：if(IsEmpty(s)push(s,*exp);elsesuffixi+=pop(s);exp;与后面的exp+相抵消，使得栈内优先级大于等于栈外的都出栈)/endswitch/endelseexp+;/endwh

17、ilewhile(!IsEmpty(s)suffixi+=pop(s);suffixi=0;3.1。假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法(在出队算法中要传回队头元素的值)要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typ edefint DataT ypestructNodeData!ypedata;Node*next;);structCycleListQueueNode*tail;voidInitCycleListQueue(CycleListQueue&L)L

18、.tail=newNode;Ltail->next=L.tail;voidEnterQueue(CycleListQueue&L,DataTypevalue)Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;voidDeparQueue(CycleListQueue&L,DataType&d)(Ltail->next!=L.tail->next->next)ifNode*p=L.tail->next->next;L

19、.tail->next->next=p->next;d=p->data;if(p=L.tail)L.tail=p->next;deletep;returnd;3.11假设将循环队列定义为：以rear和length分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法(在出队算法中要传递回队头元素的值)。此循环队列的队满条件：Q.Iength-MAXQSIZE;入队算法：StatusEnCyQueue(CyQueue&Q,intx)/带length域的循环队列入队算法(if(Q.Iength=MAXSIZE)returnOVERF

20、LOW;Q.rear=(Q.rea叶1)%MAXSIZE;Q.baseQ.rear=x;/rear指向队尾兀素Q.Iength+;returnOK;/EnCyQueue出队算法：StatusDeCyQueue(CyQueue&Q,int&x)/带length域的循环队列出队算法，用x返回队头元素的值(if(Q.length=O)returnError;/空队歹错误head=(Q.rear-Q.Iength+l)%MAXSIZE;/head指1司队头x=Q.basehead;Q.Iength;returnOK;/DeCyQueue3.12试写一个算法：判别读入的一个以为结束符的字

21、符序列是否是“回文”(所谓“回文”是指正读和反读都相同的字符序列，如“xxyzyxx”是回文，而“abcab”则不是回文)。StatusTest()判别输入的字符串是否回文序列，是则返回1,否则返回0(InitStack(S);InitQueue(Q);while(c=getchar()!=,)(Push(S,c);EnQueue(Q,c);同时使用栈和队列两种结构)while(IStackEmpty(S)(Pop(S,a);DeQueue(Q,b);if(a!=b)returnERROR;returnOK;/Test第五章多维数组5.4设有一个准对角矩阵a1222riia2133a3443a

22、442m*f 2m J3.2m, 2m.a 2m , 2ma2m, 2m按以下方式存于一维数组BL词中:alla12a21a22a33B34a43 a 1J a2m-l, 2ma2m, 2m01234564nl24m-1写出由一对下标(i, j)求k的转换公式。因为i行前有2(i-l)个元素。现考虑i行情况,当j是奇数，i行有1个元素,k=2(i-l)+l+2(i-l)；否则i行有 2 个元素，k=2(i-l)+2-l=2i-lo 故:1)腐奇数k=bni /为翩或若 i 为奇数，k=2(i-l)+j-i=i+j-2;当 i 为偶数时，k=2i-(i-j)-l=i+j-l5. 5已知稀疏矩阵A

23、4X 5如下:I 10 32 00 40051006000700 用三元组表作为存储结构，绘出相应的三元组表示意图; 用十字链表作为存储结构，绘出相应的十字链表示意图。三元组表:1jV121155212223246424457十字链表第六章数和二叉树6.5已知一棵度为k的树中有nl个度为1的结点，n2个度为2的结点，nk个度为k的结点，问该树中有多少个叶子结点？设叶子结点有x个，则树的结点总数为nl+n2+nk+x;同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：nl+2?n2+k?nk+l;knl+n2+nk+x=nl+2?n2+k?nk+l可得x=S(i-i)-

24、ni+1iz26.8已知一棵树如图6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。图6-1先根遍历：ABCEIJFGKHD后根遍历：BIJEFKGHCDA对应的二叉树：6.9将如图6-2所示的森林转化为对应的二叉树。树对应的二叉树森林对应的二叉树:图6-2图6-26.n己知某二叉树的中序序列为请DCBGEAHFIJK,后序序列为DCEGBFHKJIA。画出该二叉树。每个字母在电文中出现6.14假设某个电文由(a,b,c,d,e,f,g,h)8个字母组成,的次数分别为(7,19,2,6,32,3,21,10),试解答下列问题：(1)ifflj出出huffman树；10

25、0写出每个字母的huffman编码;a:1010b:00c:10000d:1001e:llf:10001g:01h:1011在对该电文进行最优二进制编码处理后，电文的二进制位数。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17写出按层次遍历二叉树的算法。思路：用队列存储结构，并用递归方法StatusLevelOrderTraverse(BitTreeStatus(*Visit)(TEIemTypee)/层序遍历二叉树InitQueue(Q);初始化队列if(!T)returnError;/空树，直接返回EnQueue(Q,T)；根结点入队BiTNode*p

26、;while(JQueueEmpty(Q)(DeQueue(Q,p);Visit(p->data);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);/whilereturnOk;/LevelOrderTraverse6. 19写出判断两棵给定二叉树是否相似的算法。（注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。）思路：采用递归进行比较判断boolBiTreeSimilar(BiTreeTl,BiTreeT2)if(Tl

27、=Null&&T2=Null)return1;elseif(T1二二NullT2=Null)return0;elsereturn(BiTreeSilimar(Tl->lchild,T2->lchild)&&BiTreeSimilar(Tl->rchild,T2->rchild);6.21写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。思路：在孩子兄弟链表中，若结点的firstchild为Null,则为叶子结点；采用递归方法。intCountLeaves(TreeT,int&num)/num传递的初值为0(if(T->n

28、extsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=l;/firstchild域为空，则为叶子结点returnnum;)第七章图7. 1已知有向图如图7-1所示,请给出该图的邻接矩阵示意图邻接表示意图逆邻接表(4)所有强连通分量邻接矩阵o00000100100010001001011I 0000°II 10010(2)邻接表(3)逆邻接表强连通分量V2V6V4V37.2已知图G的邻接矩阵如图7

29、-2所示。写出该图从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。1234567891010图7-2深度优先序歹lj:1734562109810深度优先生成树：广度优先序列：17931054862103广度优先生成树:9.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定的值的记录;（2 ）查找成功，且表中只有一个关键字等于给定值（3 ）查找成功，且表中有若干个关键字等于给定值 解: 对有序顺序表：的记录；的记录，要求找出所有这些记 录。11.1 +2 + . + (n 九+2)个元素序列的成功查找问题)21 n +1nLJ 2（将该项看作一项混入原有序列中，问题转变成n+13.L1+2 + 一此k项看作一项n- (k- 1) L+ n- (k 1) 1 =J 2TA将对无序顺序表:-rl +2 +