《习题及解答.docx》由会员分享，可在线阅读，更多相关《习题及解答.docx（10页珍藏版）》请在课桌文档上搜索。
1、第1章1.请说明数据结构、数据类型以及抽象数据类型之间的区别。略2 .解释什么是数据的逻辑结构和物理结构。略3 .分析下面各算法(程序段)的最大语句频度并计算该算法的时间复杂度。1) for(i=0;in;i+)for(j=Ojn;j+)Aij=O;O(M)2) for(i=0;in;i+)for(j=0;ji;j+)Aij=O;O(M)3) s=0;for(i=0;in;i+)for(j=O;jn;j+)for(k=0;kn;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=
2、1.length;for(i=0;inext;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+lmaxsize(!1.1.ength)return0;for(i=1.Iength-I;1.elemix&i=0;i一)Elemi+l=elemi;elcmi+l=x;1.length+;return1;)第3章1、己知堆栈采用链式存
3、储结构，初始时为空，试画出u,%w,X四个元素依次进栈以后堆栈的状态，然后画出此时的栈顶元素出栈后堆栈的状态。2、用图表示出使用栈将表达式“9*(8-3)/5+4#”转换成后缀表达式并计算结果的过程。3、假定用一个单循环链表来表示队列(也称为循环队列)，该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：(1)向循环链队列插入一个元素值为X的结点；(2)从循环链队列中删除一个结点。本题是对一个循环链队列做插入和删除运算,假设不需要保留被删结点的值和不需要回收结点，算法描述如下：(1)插入(即入队)算法：insert(1.ink1.ist*rear,eIemtypex)设循环链队列的
4、队尾指针为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)队中只有一个结
5、点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(ilen&tag)if(-veci!=y-vec
6、i)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的一
7、棵哈复曼树，并求其加权路径长度WP1.o2、已知一棵度为In的树中有nl个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少个叶子结点？3、二叉树采用链接存储结构，试设计一个按层次顺序(同一层次自左至右)遍历二叉树的算法。第7章1、图G=(V,E),其中V=l,2,3,4,5,6,E=,(2)卷。啦卷仓图7-2二叉排序树的构造过程2、设有一组关键字(19,01,23,14,55,20,84,27,68,11,10,77),采用哈希函数：H(key)=key%13,若用开放定址法的线性探测法解决冲突，试在013的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的AS1.解
8、：依题意，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(8
9、4)=(6+l)%146(冲突)=7(仍冲突)H(10)=(10+1)%14=11(仍冲突)H(84)=(7+1)%14=8H(10)=(11+1)%14=12H(27)=27%13=1(冲突)H(77)=77%13=12(冲突)H(27)=(l+I)%14=2(仍冲突)H(77)=(12+1)%14=13哈希表如下:哈希地址012345678910111213关键字11455276819208423111077比较次数121431131132共有12个关键字，等概率查找，则成功查找时AS1.=(1+2+1+4+3+1+1+3+1+1+3+2)/12=23/121.93、已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每一趟的排序结果。(0)46(1)34(2)26(3)14(4)1474531426388665273427381426468665537427143438467465538626273438465365J7486262734384653657486第10章1、己知一组记录为(46,74,53,14,26,38,86,65,27.34),给出采用快速排序法进行排序时每一趟的排序结果。
