习题及解答.docx
第1章1.请说明数据结构、数据类型以及抽象数据类型之间的区别。略2 .解释什么是数据的逻辑结构和物理结构。略3 .分析下面各算法(程序段)的最大语句频度并计算该算法的时间复杂度。1) for(i=0;i<n;i+)for(j=Oj<n;j+)Aij=O;O(M)2) for(i=0;i<n;i+)for(j=0;j<i;j+)Aij=O;O(M)3) s=0;for(i=0;i<n;i+)for(j=O;j<n;j+)for(k=0;k<n;k+)s=s+Bijk;sum=s;0(n3)4) i=l;while(i<=n)i=i*2;0(log2n)第2章an)1.inti,n;ElemTypetemp;n=1.length;for(i=0;i<n/2;i+)(temp=1.elemn-l-i;1.elemn-l-i=1.elemi;1.elemi=temp;)2. 1试写一算法，实现顺序表的就地逆置.，即利用原表的存储空间将线性表(al,a2,.逆置为(an,an-l,.,al)typedefstruct(ElemType*elem;/存储空间基intlength;表长,元素个数intlistsize;表容量,空间大小Sq1.ist;voidReverse_Sq(Sq1.ist&1.)(利用原表空间就地逆置顺序表2.2设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。Pr=OPprhPvoidinvert(1.ink1.ist*head)逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head->next;while(p!=NU1.1.)/当表不为空时，逐个结点逆置s=q；q=p;p=p->next;q->next=s;)p->next=q;)2.3设顺序表Va中的数据元数递增有序。试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。intInsert(Seq1.ist&1.,x)inti;if(1.length+l>maxsize(!1.1.ength)return0;for(i=1.Iength-I;1.elemi>x&&i>=0;i一)Elemi+l=elemi;elcmi+l=x;1.length+;return1;)第3章1、己知堆栈采用链式存储结构，初始时为空，试画出u,%w,X四个元素依次进栈以后堆栈的状态，然后画出此时的栈顶元素出栈后堆栈的状态。2、用图表示出使用栈将表达式“9*(8-3)/5+4#”转换成后缀表达式并计算结果的过程。3、假定用一个单循环链表来表示队列(也称为循环队列)，该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：(1)向循环链队列插入一个元素值为X的结点；(2)从循环链队列中删除一个结点。本题是对一个循环链队列做插入和删除运算,假设不需要保留被删结点的值和不需要回收结点，算法描述如下：(1)插入(即入队)算法：insert(1.ink1.ist*rear,eIemtypex)设循环链队列的队尾指针为rear,x为待插入的元素1.ink1.ist*p;p=(1.ink1.ist*)malloc(sizeof(1.ink1.ist);if(rear=NU1.1.)如为空队，建立循环链队列的第一个结点rear=p;rear->next=p;链接成循环链表)else否则在队尾插入P结点p->next=rear->next;rear->next=p;rear=p;)(2)删除(即出队)算法：delete(1.ink1.ist*rear)设循环链队列的队尾指针为rearif(rear=NU1.1.)空队printf(,underflow11zz);if(rear->next=rear)队中只有一个结点rear=NU1.1.;elserear->next=rear->next->next;/rear->next指向的结点为循环链队列的队头结点)第4章1、若X和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。解：两个串相等表示对应的字符必须都相同，所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等，由此得到如下函数：intsame(x,y)(orderstring*x,*y;(inti=0,tag=l;if(->len!=y->len)return(0);else(while(i<->len&&tag)if(->veci!=y->veci)tag=O;i+；)return(tag);)2、若X和y是两个单链表存储的串，编写一个函数找出X中第一个不在y中出现的字符。typedefcharDataType;typedefstructNodeDataTypedata;structNode*next;1.ink1.ist;linklist*search(linklist*x,linklist*y)linklist*p,*q;P=X；q=y;While(P&&q)if(p->data!=q->data)q=q->next;elsep=p->next;q=y;)returnp;)第6章1、设给定权集w=(2,3,4,7,8,9),试构造关于W的一棵哈复曼树，并求其加权路径长度WP1.o2、已知一棵度为In的树中有nl个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少个叶子结点？3、二叉树采用链接存储结构，试设计一个按层次顺序(同一层次自左至右)遍历二叉树的算法。第7章1、图G=(V,E),其中V=l,2,3,4,5,6,E=<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6»,请画出图G,并写出其邻接矩阵和邻接表表示。解：图G如图6-4中的（八）所示，图G的邻接矩阵和邻接表表示分别如图(b)和(C)所示。对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下.对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。©-0111000001010010000000001_00000001110.2、己知一个无向图的邻接表如图所示，要求：(1)画出该无向图；(2)根据邻接表，分别写出用DFS(深度优先搜索)和BFS(广度优先搜索)算法从顶点VO开始遍历该图后所得到的遍历序列。解：(1)该无向图如图6-6所示。图6-6无向图VOVlV2V3V4V5V62561A3042A03I61A12I4A1306八I25I0AIU6-5图的邻接表存储(2)根据该无向图的邻接表表示，从顶点VO开始的深度优先遍历序列为：Y0、V2、V3、VI、V4、V6、V5o广度优先遍历序列为VO、V2、V5、V6、VKV3、V4。从图的逻辑结构上来讲,从图中某个顶点开始的深度(或广度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中，并没有对每个顶点的所有邻接点规定它们之间的先后顺序，这样在搜索算法中选取第一个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序，这时深度优先和广度优先遍历序列就是唯一的。3、对于如图6-8所示的带权无向图，用图示说明：(1)利用Prim算法从顶点a开始构造最小生成树的过程；(2)利用Kruskal算法构造最小生成树的过程；O234©84D94×-y197。5068解：(1)利用Prim算法从顶点a开始构造最小生成树的过程如图6-9所示。初始状态连通e连通g23®l。©234©连通d连通f连通b连通C用Prim算法构造最小生成树的过程(2)利用Kruskal算法构造最小生成树的过程如图6-10所示。Q)G)初始状态增加第1条边增加第2条边21。1增加第3条边23。'增加第4条边234©1QG)1。增加第5条边G23O4(i1O6Q1Q增加第6条边Kruskal算法构造最小生成树的过程第9章1、记录的关键字序列为：63,90,70,55,67,42,98,83,10,45,58,则画出构造一棵二叉排序树的过程。解：构造二叉排序树的过程如图7-2所示。O©©©©®©®®®>©©©©©(2)®®©®®©®卷。啦卷仓图7-2二叉排序树的构造过程2、设有一组关键字(19,01,23,14,55,20,84,27,68,11,10,77),采用哈希函数：H(key)=key%13,若用开放定址法的线性探测法解决冲突，试在013的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的AS1.解：依题意，m=13,线性探测法的下一个地址计算公式为：di=H(key)di+=(di+l)%m；i=l,2,其计算函数如下：H(19)=19%13=6H(27)=(2+1)%14=3(仍冲突)H(01)=01%13=1H(27)=(3+1)%14=4H(23)=23%13=10H(68)=68%13=3(冲突)H(14)=14%13=1(冲突)H(68)=(3+l)%14=4(仍冲突)H(14)=(1+1)%14=2H(68)=(4+1)%14=5H(55)=55%13=3H(11)=11%13=11H(20)=20%13=7H(10)=10%13=10(冲突)H(84)=84%13=H(84)=(6+l)%146(冲突)=7(仍冲突)H(10)=(10+1)%
