2023年数据结构与算法离线作业答案.pdf

《2023年数据结构与算法离线作业答案.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构与算法离线作业答案.pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、浙江大学远程教育学院 数据结构与算法课程离线作业姓名：陈翠 学 号：7年级：2023秋 学习中心：金华学习中心一、填空题：(【序号，章，节】。)1,1,2线性结构中元素之间存在一对一关系，树形结构中元素之间存在_ 一对多关系，图形结构中元素之间存在 多对多 关系。2,1 ,2 为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。3,1,2 存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构，_链式存储结构o4,1,3】度量算法效率可通过_ 时间复杂度 来进行。5,1,31设 n 为正整数，下面程序段中前置以记号的语句的频度是n(n+l)/2_ of o r (i=0；i n

2、;i+)for(j=0;j n;j+)i f(i+j=n-l)a i E j =0;6,1,3设n 为正整数，试拟定下列各程序段中前置以记号的语句的频度：(1)i=1;k=0;wh i le(i=n-l)i+；k+=l 0*i;语句的频度是 n-1 o)(2)k=0;for(i=l；i=n;i+)f o r (j=i；jnext=N ULL10,3,2】在一个单链表中p 所指结点(p所指不是最后结点)之后插入一个由指针s 所指结点，应执行s-n e x t=_ p-ne x t-：和p-n e x t=s 的操作o11,3,2】在一个单链表中删除p 所指结点时，应执行以下操作：q=p-next

3、;p-d ata=p-next-data;p-n e x t=p nex t-n e x tfr e e(q);1 2,3,2】带头结点的单循环链表H ead的判空条件是_ H e a d-next=Hea d；不带头结点的单循环链表的判空条件是一 Head=NUL L-。13,3,2 已知L 是带表头结点的非空单链表，且P 结点既然不首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P 结点的直接前驱结点的语句序列是_10 12 8 11 4 14。b.册U 除结点P 的语句序列是_ 1 0 12 7 3 14。c.删除尾元结点的语句序列是 9 11 3 14 o(1

4、)P=P-nex t;(2)P-ne x t 二 P；(3)P-next=P-n e xt-next；(4)P=P next nex t;(5)whi 1 e(P!=NULL)P=P-nex t;(6)while(Q-nex t!=NU L L)P=Q;Q=Q-n e x t;whi 1 e(P-n e x t!=Q)P=P-nex t;(8)wh i 1 e(P n e x t n e x t!=Q)P=Pn e x t;(9)while(P-next-nex t!=NULL)P=P-n ext；(1 0)Q=P；(1 1)Q=P-next;(1 2)P=L;(1 3)L=L-next;(1

5、4)f r e e (Q);14,3,3 对一个栈，给定输入的顺序是A、B、C,则所有不也许的输出序列有 不也许得到的输出序列有CAB o15,3,31.在栈顶指针为H S 的链栈中，鉴定栈空的条件是_head next=N ULL_。16,3,31下列程序把十进制数转换为十六进制数，请填写合适的语句成分。voi d conve r sionl 0 _16()In i tS tack(&s);scanf(%d”,&N);wh i 1 e(N)P u sh(s,N%16);N=N/16；)w h ile(!S t ackEmpty(s)Pop(s,e)；i f(e =9)pr i n t f (

6、d”，e);e l s e p r i n t f (c”,e 1 0 +A )；/*c o n v e r s i o n */1 7,3,4 若用一个大小为6个元素的数组来实现循环队列,且当前r e a r=0和f r o n t=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_2和 4 _o 1 8,3,4 堆栈和队列都是线性表，堆栈是 后进先出_ _ _ _ _ _的线性表，而队列是先进先出 的线性表。19,3,4 若用一个大小为6个元素的数组来实现循环队列,且当前r e a r=0和f r o n t=3。当从队列中删除一个元素，再加入两个元素后，r e

7、 a r和f r o n t的值分别是2_和_4 o2 0,4,2 已知一棵树边的集合是 ,Vd,c ,o那么根结点是_e,结点b的双亲是 d,结点a的子孙有_ b c d j,树的深度是 4,树的度是_3 _,结点g在树的第3 层 21,4,3从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是一树可采用二叉树的存储结构并运用二叉树的已有算法解决树的有关问题o 22,4,3 满三叉树的第i层的结点个数为3 i-1，深度为h时该树中共有 3-lh结点。2 3,4,3】已知一棵完全二叉树有5 6 个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1 号。则该完全二叉

8、树总共结点有 1 1 1 个;有 7 层;第 9 1 号结点的双亲结点是4 5 号；第 6 3 号结点的左孩子结点是 32号。24,4,3】下列表达的图中，共有 5 个是树；有 3 个是二叉树；有_ 2 个是完全二叉树。25,4,4 n 个结点的二叉排序树的最大深度是_ n ，最小深度为1。g 2n+126,4,3 假如某二叉树的后序遍历序列是ABCDEFGHI,中序遍历序列是ACBIDF EH G,则其先序遍历序列的第一个字母是一 I _，最后一个字母是_G_。27,4,3 下列二叉树的中序遍历序列是_DBNGOAEC_;后序遍历序列是 D NI GBECA o28,5,4 设H A S H

9、 表的大小为n(n=10),H A SH 函数为h(x)=x%7,假如二次探测再散列方法Hi=(H(key)+di)mod 10(di=l2,2 2,32,.,)解决冲突,在 HASH表中依次插入关键字 1,14,55,20,84,2 7 以后，关键字1、2 0 和 27所在地址的下标分别是_1_、_ 7 _ 和 5。插入上述6 个元素的平均比较次数是22 9,6,3 设无权图G 的邻接矩阵为A,若(vi,vj)属于图G 的边集合，则相应元素 Ai jl等 于 1 ,2 2、设无向图G 的邻接矩阵为A,若A i j等于0,则 Aj i等于 0。3 0,6 ,3 若一个图用邻接矩阵表达，则删除从

10、第i 个顶点出发的所有边的方法是矩阵第i 行所有置为零013 1,6,2 设一个图G=V,A,V=a,b,c,d,e,f,A=,e,d,那么顶点e的入度是 2；出度是 1；通过顶点f的简朴回路有 2 条:就连通性而言.该图是强连通 图；它的强连通分量有_个:其生成树也许的最大深度是5。32,7,1 排序过程一般需通过两个基本操作，它们是 比较 和移动 3 3 ,7,2在对一组关键字是(54,38,9 6,45,15,72,60,23,8 3)的记录进行直接插入排序时，当把第七个记录(关键字是60)插入到有序表时，为寻找插入位置需比较三次。34,7,4 插入排序、希尔排序、选择排序、快速排序、堆

11、排序、归并排序、和基数排序方法中，不稳定的排序方法有_ 希尔排序_、_ 快速排序_、_ 堆排序二、综合题(选自教材 数据结构各章习题，采用w o rd文献格式上传)1 ,1,31试分析下面一段代码的时间复杂度：i f (A B)(f o r(i=0；i i;j-)A+=B;/A=A+B)e Is e fo r(i=0；i i;j-)A+=B;/A=A+B)A n sw er:i f AB为真，则f o r语句的外循环N次，内循环为N(N-l)次，因此时间复杂度为0(N*N(N-l),也就是N的三次方。i f A B为假，则f。r语句的外循环2 N次，内循环为N次，因此时间复杂度为0(2N*N)

12、，也就是N的平方。2,1,3 测试例1.3 中秦九韶算法与直接法的效率差别。令/(x)=l+Z tx/3+算/(L1)的值。运用clock()函数得到两种算法在同一机器上的运营时间。A n s w e r：f(1.1)=13 7 7 9 7.406253,1,31试分析最大子列和算法1.3 的空间复杂度。4,1,31试给出判断N 是否为质数的0(灰)的算法。An s w er：i nt sushu(int N)AMnt i;intflag=1；if(N=1)r e turn false;/1 既不是合数也不是质数if(N=2)ret u r n tru e;for(i=2；i=s q rt(N

13、);i+)(i f(N%i=0)A A f la g=0brea k;4 return flag;5 ,2,2 请编写程序，输入整数n和a,输 出S=a+a a+aa a+aa.a(n个a)的结果。Answe r：#inc 1 ude s tdio.hin t ma i n()Jint a,b,n,i,s=0;s canf(%d%d,&a,&n)；A b=a;A f o r(i=1;i=n;i+)4 s+=a;a=a*10+b;A p r int f(%dn,s);A6,2,3】请编写递归函数，输出123.n的全排列(n小于1 0),并观测n逐步增大时程序的运营时间。A nswer:#in c

14、 lud e#d e fi n e swa p(a,b)intt=a;Wa=b;A b=)AVO i d p e r mutation(i nt*a,int b,int e)gint i*if(b=e)(for(i=0;i e;+i)p rintf(%d,ai);Aprintf(n)；A e ls e(4o r(i=b；i e;+i)3 swap(ab,a i)；permuta t i on(a,b+1,e)。s w a p(a b,a i)；0 卜 Ain t main(v oi d)int a4=1,2,3,4;A perm u tation(a,0,4);/*system(paus e)

15、;*/丛 return 0;)7,3,2 1 给定一个顺序存储的线性表L=(%,a2l%),请设计一个算法删除所有值大于mi n 并且小于max的元素。#i n clu d e A#inc 1 ude#i n clud e Atyp e d e f in t E lemT y pe;typ e d e f s tract LNo d ElemTy p e da t a;/*数据子域*/A s t r uct L No d e*next;/*指针子域小)LNo d e;I*结点结构类型*/LNode*L;AA/*函数声明*/ALN O de*cr e at_L()；svoid d e lete_

16、L(LNode*L,int i);返回值格式变为空/*建立线性链表*/LNod e*c r e at_L()A LNode*h,*p,*s；ElemTy p e x；h=(LNode*)malloc(s i zeof(LNode);/*分派头结点*/h-n e x t=NULL;P =h;A p ri n t f(输入一串数字(以一1 结束):n d a ta=)：s c an f(%d ，&x)；/*输入第一个数据元素*/while(x!=-1)/*输入-1,结 束 循 环*/(s=(LNode*)malloc(sizeof(LNode);/*分派新结点 办s-dat a=x;s-next=

17、NULL;*p-next=s；p=s;printf(data=);scanf(%d,&x);r输入下一个数据*/A r e t u r n(h)；A/*c r e at_ L*/AA/*输出单链表中的数据元素*/A V 0 i dout_L(LN ode*L)ALN o de*p；A p=L-next；A prin t f(n 数据是：)*w h ile(p!=N ULL)A pr i ntf(%5 d ,p-d a t a);A p=p n ext；A /*outI in k*M*删除大于x 小于y 的值*/vo i d delete_L(LNo d e*L,int a,int b)-*LN

18、od e*p,*q；A p=L；A q=p；p=p n e x t；A i f(p=NULL)print f(ERROR:链表为空)；wh i le(p!=N U L L)A A if(p d ata a)&(p-data n e x t=p-ne x t；A free(p);p=q-next；)else q=p；p=p-next;卜 /*delete，*/4 v o i d ma i n()Ai nt a,b;A L=c r eat_L();o utL(L);pri ntf(nn请输入你要删除的元素的范围min和max:n);劣 sc a n f(%d%d,&a,&b);del e te_L

19、(L,a,b);outL(L);P rin t f(n)；呼/*main 78,3,2 给定一个顺序存储的线性表L=(a,a2 r*),请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)o#i nclu d e#i ncl u d e usin g n a mespace st d；#def i n e MAXN 1003in t A MAXN;in t dpMAXN；/动态规划思想O(n-2)in t m a in()i n t n,i,j,k；c in n;f o r (i=1 ;i A i;d p 1 =1;

20、/有n个阶段f or(i=2;i =0;j-)i f (A i A j )d p i=m a x(d p i,d p j +l);in t max i mum=d p 1;f o r (i =2;i=n;i +)maximum=m a x(maximum,d p i )；cout max i m u m;9,3,3假如有1、2、3、4、5按顺序入栈，不同的堆栈操作(pop,pus h)顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？Answer：共有3 4种不同的输出序列12345 1 2354 1 24 3 5 12 5 4 3 1 3 2 45 1 32 5 4 143

21、25 1 5 4 32 21 3 45 2143 5 2 1 543 23145 2315 4 2 34 1 5 23451 2 3541 2 43 1 52 4 35 1 24531 254313214 5 32154 3 24 15 324 5 1 3 2 541 3421 5 3425 1 3452 135 421 43215 43251 4352 1 4532 1 543211 0,3,2 请编 写程序将中缀表达式转换为后缀表达式。#i nc 1 ude#include a#i n cl u de u sing n a mes P ace s t d;i n t p r i o r(c

22、har o p)ai f(op=z+|op=,J)r eturn 1;if(op=*|o p=7)r e t u rn 2;r e turn 0;4str i n g midd 1 et o last(s trin g m i ddle)stack op；s t r i n g a ns;for(i nt i=0;i=0,&c ans.appen d(lzc)；els ei f(c=C)a o p.p ush(C);e Iseif(c=)/)whil e(op.top()1 =，()a ans.app end(l,o p.to p();o p .p op();a a o p.pop();)e

23、I s e&i f(op.emp t y()&op.push(c)；el s ei f(p r i o r(c )pri o r(op.to p()op.push(c )；4 e ls e a whi 1 e(!op.e mpty()&prior(c)mda t a;r es=midd 1 eto 1 ast(m d a ta);a f o r (int i=0;ire s.s ize();i+)而 if(i=0)c outresi；j5 e 1 seco ut res i2 4cou t retu r n 0;)11,4,31设二叉树的存储结构如下：的指针值为6,L child,Rchild

24、分别为结点的左、右孩子指针域,data为数据域。（1）画出二叉树的逻辑结构。（2）写出该树的前序、中序和后序遍历的序列。Answe r(1)ABCD F G IE H(2)前序:ABD F E CGH I中序:D BE FAG HC I后序:DEFBHG I CA1 2,4,4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。答：可以生成如上二叉排序树的关键字的初始排列有3()种任写4个序列如下：(5,7,6,4,2,1,3)(5,7,6,4,2,3,1)(5,4,2,3,7,6,1)(5,4,2,1,7,6,3)1 3,4,5给定关键字序列(1 1、7、16、4、2 2

25、、13、5),请回答:(1)画出依次插入到一棵空的二叉排序树后的最终二叉树(6分)；(2)画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果(4分)；ANS WE R1 17 1 64 22 13 514,4,6 假设一个文本使用的字符集为 a,b,c,d,e,f,g,字符的哈夫曼编码依次为 0110,10,1 1 0,111,00,0 11 1,0 1 0 o(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；(2)若这些字符在文本中出现的频率分别为:3,3 5,1 3,1 5,20,5,9,求该哈夫曼树的带权途径长度。A N S W E R：7 44 23223 19

26、12 20/15 8 9 10/8 7/3 5编码:A(0 1 0)B(000 0 0)C(00 0 0 1 )D(0 0 1 )E(1 0)F(1 1 )G(000 1 )H(011)带权途径长度值为：(3+5)*5+7*4+(8+9+10)*3+(1 2+2 0)*2=2 1315,5,3】用公式5.6 计算一下你的身份证号码的散列值是多少。An s we r：924 3 0 016,5,4 设有一组关键字29,01,13,15,56,20,8 7,27,69,9,10,74,散列函数为：H(k e y)=key%1 7,采用平方探测方法解决冲突。试 在。至 U 1 8 的散列地址空间中对

27、该关键字序列构造散列表。ANSWER:一方面将各个数除以1 7 取余数：(627,1,2,7,7,6)可见20,85与4 6 冲突，5 8 与71冲突。将 7+1 再对13取余，直到无冲突，类似的6+1对 1 3 取余，最后可得H(71)=6;H(28)=2;H(46)=7；H(14)=1 ；H(2)=3;H (20)=8；H(85)=9；H(58)=10；哈希表存储结构:0 1 2 3 4 5 6 7 8 9 1 8 1 4 28。2。71 46 2 0 85 58平均查找长度=(1x 4+2 x 2+3 x 1 +4x 1)/8=1 5/817,5,4】将关键字序列(7,8,3 0,1 1

28、,1 8,9,1 4)散列存储到散列列表中，散 歹I表的存储空间是一个下标从0开始的一个一维数组。解决冲突采用线性探测法，散列函数为：H(key)=(k e yx3)mod T a b le S i z e,规定装入因子为 0.7。A n sw e r:线性探测法构建列表的过程关键字783 01118914散列地址14034720123456789插入77插入88插入3 03 0插入1 11 1插入185d 1=1插入99插入1 41 4 1 8,6,3 已知一个无向图的顶点集为Vo,Vi,.,V7,其邻接矩阵如下所示:v5 0Vor0 10 110 00Vi1 01 010)0V20 10

29、0 0100V31 00 0001 0v4b 10 000 J1 00 1 0 0 00 0v6 0 0 0 1 1 0 0 1v7 0 00000 0 1(1)画出该图的图形；(2)给出从Vo出发的深度优先遍历序和广度优先遍历序。1 9,6,3 已知有向图如右图所示，请给出该图的15(1)每个顶点的入度和出度;(2)邻接矩阵；(3)邻接表；(4)逆邻接表；(5)各个强连通分量。答：(1)各顶点的入/出度如下：顶点1:3/0;顶点2:2/2；顶点31/2;顶点4 1/2；顶点5:2/1；顶点6:2/3。(2)邻接矩阵如下:12345610()00001001003010001400101151

30、00()006110010(3)邻接表如下:1 _2 A 1 三 43 I-1 6 I24 I I 3 I 1 I 5 I I fi5 I-16 I-1 1 I-2 I IS(4)逆邻接表如下：1 I I 2 I1 I 5 1-；,I 62 I 1 3 I-l 63 I-44 I-25 I I 4 I I 66 I ，h I I 4(5)故意向3个强连通分量错误！错误！磐!/20,6,3 试运用 D ijk st r乱错误！错误！X o ac （O，3）,a算法求下图在从顶点A到其它顶点的最短距离及相应的3途径,写出计算过程中各步状态。A nsw e r:1 c:22A c：2 f：63 c:

31、2 f:6 e:104 c：2 f：6 e:10 d:115 c:2f:6e:1 0 d:11 g：14 6 c：2 f:6e:10d:1 1 g:14b:152 1,6,3 1 给出如下图所示的具有7 个结点的网G。请：（1）画出该网的邻接矩阵；（2）采 用 P r im 算法，从 4 号结点开始，给出该网的最小生成树（画 出 Pr i m 算法的执行过程及最小生成树的生成示意图）。22,7,4给 定 数 组 4 8,2 5,6,90,17,84,6 2,48,2 7,9 6,4 9,7 2,17）,请分别用简朴选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果,

32、分析各自比较和互换的次数，以及排序结果是否稳定。A nswer简朴选择排序过程如下:环节48256901 78462482796497217164825901 784624827964972172617482590846 248279649721736171748259084624827964972461 7172548908462482796497256171 72527489 08462489 64972661 717252 74890846248964972761 71725274848908462964 97286171725274848499 08462967296171725274

33、848496290849672106171 7252748484962729084961 161 717252748484962728490961 261 71 7252 74848496272849 096冒泡排序过程如下:环节4 82 569 01 78 4624 8279 64 97 21 71254 869 0178 4486 22 74 97 21 7 9 622 56481 7 8 44 8622 74 97 21 79 09 6362 51 74 8 4 86 2274 97 21 78 49 09 6461 72 54 84 82 74 9 6 21 7728 49 09 65

34、61 7 2 52 74 84 84 9 1 76 27 2849 096661 71 7 2 52 74 84 8 4 96 27 28 49 09 6 2 3,7,4 给定数组 4 8,2 5,6,9 0,1 7,8 4,6 2,4 8,2 7 ,9 6,4 9 ,7 2,1 7 ,请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和互换的次数，以及排序结果是否稳定。A nswer：快速排序环节4 82 569 01 78 46 2 4 82 79 64 97 21 714 861 72 71 7 4 8 9 08 46 29 64 97 226

35、1 71 7 2 52 74 8484 98 4627 29 09 6361 71 72 52 74 84 84 96 2728 49 09 6 2 4,7,4 给定数组 4 8,2 5,6,9 0,1 7,8 4,6 2 ,4 8,2 7,9 6 ,4 9,72,1 7 ,请用3 种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果,分析各自比较和互换的次数，以及排序结果是否稳定。A ns we r增量序列 5,3,1 第一步：4 8 ,8 4,4 9 、2 5,6 2,7 2 、6,4 8,1 7 ,9 0,2 7 、1 7,9 6 4 8 ,4 9,8 4 ,2 5,6 2,7 2,6,1 7,4 8,2 7,9 0 ,1 7,9 6第二步：4 8,2 5,6,2 7,9 6 、4 9,6 2,1 7,9 0 、8 4,7 2,4 8,1 7)排序:6,2 5,2 7,4 8,9 6,1 7,4 9,6 2,9 0,1 7,4 8,7 2,8 4第三步:6,1 7,1 7,2 5,2 7,4 8,4 8,4 9,6 2,7 2,8 4,9 0,9 6