浙大远程教育数据结构与算法离线作业参考答案

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

2、; j<n; j+) if (i+j=n-1) aij=0; 【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号的语句的频度: (1) i=1; k=0; while (i<=n-1) i+; k+=10 * i; / 语句的频度是n-1。 (2) k=0; for (i=1; i<=n; i+) for (j=i; j<=n; j+) k+; / 语句的频度是n(n+1)/2。 【7，3，2】线性表(a1，a2，an)有两种存储结构： 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充： 顺序存储密度较大；顺序存储利用率较高；顺序可以随机存取；链式不

3、可以随机存取；链式插入和删除操作比较方便。【8，3，2】从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动 n-i 个元素。【9，3，2】带头结点的单链表Head为空的条件是Head->next=NULL。【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=_p->next;和p->next=s的操作。【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next; p->data= p->next->data; p->next= p->

4、next->next ; free(q);【12，3，2】带头结点的单循环链表Head的判空条件是Head->next=Head； 不带头结点的单循环链表的判空条件是Head=NULL。【13，3，2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。a. 删除P结点的直接前驱结点的语句序列是10 12 8 11 4 14。b. 删除结点P的语句序列是10 12 7 3 14。c. 删除尾元结点的语句序列是9 11 3 14。(1) P = P->next;(2) P->next = P;(3) P->

5、;next = P->next ->next;(4) P = P->next ->next;(5) while (P != NULL) P = P->next;(6) while (Q->next != NULL)P = Q; Q = Q->next;(7) while (P->next != Q) P = P->next;(8) while (P->next->next != Q) P = P->next;(9) while (P->next->next != NULL) P = P->next;(10

6、) Q = P;(11) Q = P->next;(12) P = L;(13) L = L->next;(14) free (Q);【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有 CAB 。【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是head->next=NULL 。【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。void conversion10_16() InitStack(&s); scanf(“%d”,&N); while(N)Push(s,N%16) ; N = N/16;

7、while(!StackEmpty(s) Pop(s,e) ; if(e<=9)printf(“%d”,e); else printf(“%c”,e-10+A); /* conversion */【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。【18，3，4】堆栈和队列都是线性表, 堆栈是后进先出的线性表, 而队列是先进先出的线性表。【19，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再

8、加入两个元素后，rear和front的值分别是 2 和 4 。【20，4，2】已知一棵树边的集合是<a,d>,<d,c>,<d,j>,<e,a>,<f,g>,<d,b>,<g,h>,<g,i>,<e,f>。那么根结点是 e ，结点b的双亲是 d ，结点a的子孙有 bcdj ，树的深度是 4 ，树的度是 3 ，结点g在树的第 3 层。【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。【22，

9、4，3】满三叉树的第i层的结点个数为 3i-1 ，深度为h时该树中共有 3h-1 结点。【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。则该完全二叉树总共结点有 111 个；有 7 层；第91号结点的双亲结点是 45 号；第63号结点的左孩子结点是 32 号。【24，4，3】下列表示的图中，共有 5 个是树；有 3 个是二叉树；有 2 个是完全二叉树。【25，4，4】n个结点的二叉排序树的最大深度是 n ，最小深度为 log2n+1 。【26，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先

10、序遍历序列的第一个字母是 I ，最后一个字母是 G 。【27，4，3】下列二叉树的中序遍历序列是DBNGOAEC ;后序遍历序列是DNIGBECA 。 【28，5，4】设HASH表的大小为 n (n=10), HASH函数为 h(x)=x % 7, 如果二次探测再散列方法Hi=(H(key)+di) mod 10 (di = 12,22,32,)解决冲突，在HASH表中依次插入关键字1,14,55,20,84,27以后，关键字1、20和27所在地址的下标分别是 1 、 7 和 5 。插入上述6个元素的平均比较次数是 2 。【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集

11、合，则对应元素Aij等于 1 ，22、设无向图G的邻接矩阵为A，若Aij等于0，则Aji等于 0 。【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是 矩阵第i行全部置为零 。【31，6，2】设一个图G=V,A,V=a,b,c,d,e,f,A=<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>。那么顶点e的入度是 2 ；出度是 1 ；通过顶点f的简单回路有 2 条；就连通性而言，该图是 强连通 图；它的强连通分量有 1 个；其生成树可能的最大深度是 5

12、。【32，7，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。二、综合题（选自教材数据结构各章习题，采用word文件格式上传）【1，1，3】试分析下面一段代码的时间复杂度：if ( A > B ) for ( i=0; i<N; i+

13、 ) for ( j=N*N; j>i; j- ) A += B;else for ( i=0; i<N*2; i+ ) for ( j=N*2; j>i; j- ) A += B;答： if A>B为真，则for语句的外循环N次，内循环为N（N-1）次，因此时间复杂度为O(N* N（N-1）)，也就是N的三次方。 if A>B为假，则for语句的外循环2N次，内循环为N次，因此时间复杂度为O（2N*N），也就是N的平方。整段取最大的，时间复杂度就是N立方。【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令，计算的值。利用clock()函数得到两种算法在

14、同一机器上的运行时间。答： 直接法：0.1 s 秦九韶算法：0.04 s【3，1，3】 试分析最大子列和算法1.3的空间复杂度。答：算法1.3的基本思路是将原问题拆分成若干小型问题，分别解决后再将结果合而治之，用递归方法实现。算法1.3的负责度分析略有难度：若记整体时间复杂度为T(N)，则函数DivideAndConquer中通过递归实现“分”的复杂度为2T(N/2)，因为我们解决了2个长度减半的字问题。求跨分界线的最大子列和时，有两个简单的for循环，所用步骤一共不超过N，所以可以在O(N)时间完成。其他步骤都只需常熟O(1)时间。综上分析则有递推式：T(1)=O(1)；T(N)=2T(N/

15、2)+O(N) =22T(N/2)/2+O(N/2)+O(N)=22T(N/22)+2O(N) =2KT(N/2k)+kO(N)当不断对分直到N/2k=1,即2k=N时，就得到T(N)=NT(1)+logN*O(N)=O(N log N)。此算法比算法1.2又快了一些，当N=104时，效果会非常明显。但是这仍然不是最快的算法。【4，1，3】试给出判断是否为质数的的算法。答:int sushu(int N) int i; int flag=1; if (N=1) return false; /1既不是合数也不是质数 if (N=2) return true for (i=2;i<=sqrt

16、(N);i+) if (N%i=0) flag=0； break; return flag;【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+aaa(n个a)的结果。答：#include"stdio.h"int main() int a,b,n,i,s=0; scanf("%d %d",&a,&n); b=a; for(i=1;i<=n;i+) s+=a; a=a*10+b; printf("%dn",s);【6，2，3】请编写递归函数，输出123.n的全排列（n小于10）,并观察n逐步增大时程

17、序的运行时间。答：#include <stdio.h> #define N 8 int n = 0;void swap(int *a, int *b) int m; m=*a; *a=*b; *b=m;void perm(int list, int k, int m) int i; if(k > m) for(i = 0; i <= m; i+) printf("%d", listi); printf("n"); n+; else for(i = k; i <= m; i+) swap(&listk,&lis

18、ti); perm(list,k + 1, m); swap(&listk,&listi); int main() int listN; int num,i=0; printf("Pleaseinput a num:"); scanf("%d",&num); while(num != 0) listi=num%10; num=num/10; i+; perm(list,0, i-1); printf("total:%dn",n); return 0;【7，3，2】 给定一个顺序存储的线性表L = (, , &#

19、188;, )，请设计一个算法删除所有值大于min而且小于max的元素。答：#include <stdio.h> #include <stdlib.h> #include <math.h> typedef int ElemType; typedef struct LNode ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ LNode; /* 结点结构类型 */ LNode *L; /* 函数声明 */ LNode *creat_L();void delete_L(LNode *L,int i)

20、; /返回值格式变为空/* 建立线性链表*/LNode *creat_L() LNode *h,*p,*s; ElemType x; h=(LNode *)malloc(sizeof(LNode); /* 分配头结点 */ h->next=NULL; p=h; printf("输入一串数字（以-1结束）:ndata= "); scanf("%d",&x); /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1，结束循环 */ s=(LNode *)malloc(sizeof(LNode); /* 分配新结点 */ s-

21、>data=x; s->next=NULL p->next=s; p=s; printf("data= "); scanf("%d",&x); /* 输入下一个数据*/ return(h); /* creat_L */* 输出单链表中的数据元素*/void out_L(LNode *L) LNode *p; p=L->next; printf("n数据是:"); while(p!=NULL) printf("%5d",p->data); p=p->next; /* out

22、_link */* 删除大于x小于y的值*/void delete_L(LNode *L,int a,int b) LNode *p,*q; p=L; q=p; p=p->next; if(p=NULL) printf("ERROR:链表为空"); while(p!=NULL) if(p->data >a) && (p->data <b) q->next=p->next; free(p); p=q->next; else q=p; p=p->next; /* delete_L */void main()

23、int a,b L=creat_L( ); out_L(L); printf("nn请输入你要删除的元素的范围min和max:n"); scanf("%d%d",&a,&b); delete_L(L,a,b); out_L(L); printf("n"); /* main */【8，3，2】给定一个顺序存储的线性表L = (, , ¼, )，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。答：#include <iost

24、ream>#include <algorithm>using namespace std;#define MAXN 1003int AMAXN;int dpMAXN;/ 动态规划思想O(n2)int main() int n, i, j, k; cin >> n; for (i=1; i<=n; i+) cin >> Ai; dp1 = 1; / 有n个阶段 for (i=2; i<=n; i+) dpi = 1; / 每个阶段只有1个状态 / 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度 for (j=i-1; j>

25、=0; j-) if (Ai>Aj) dpi = max(dpi, dpj+1); int maximum = dp1; for (i=2; i<=n; i+) maximum = max(maximum, dpi); cout << maximum; 【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？答： 共有34种不同的输出序列 12345 12354 12435 12543 13245 13254 14325 15432 21345 21435 21543 2

26、3145 23154 23415 23451 23541 24315 24351 24531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321【10，3，2】请编写程序将中缀表达式转换为后缀表达式。答:#include <iostream>#include <stack>#include <string>using namespace std;int prior(char op)if(op='+'|op='

27、-') return 1;if(op='*'|op='/') return 2;return 0;string middletolast(string middle)stack<char> op;string ans; for(int i=0;i<middle.size();i+) char c=middlei; if(c>='0'&&c<='9') ans.append(1,c); else if(c='(') op.push('('); el

28、se if(c=')') while(op.top()!='(') ans.append(1,op.top(); op.pop(); op.pop(); else if(op.empty() op.push(c); else if(prior(c)>prior(op.top() op.push(c); else while(!op.empty()&&prior(c)<=prior(op.top() ans.append(1,op.top(); op.pop(); op.push(c); while(!op.empty() ans.ap

29、pend(1,op.top(); op.pop(); return ans;int main()string mdata,res;cin>>mdata; res=middletolast(mdata);for(int i=0;i<res.size();i+) if(i=0) cout<<resi; else cout<<' '<<resi;cout<<endl;return 0;【11，4，3】设二叉树的存储结构如下：12345678910Lchild00237580101dataJHFDBACEGIRchild

30、0009400000其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。（1） 画出二叉树的逻辑结构。答：ABCEDFGIHJ（2） 写出该树的前序、中序和后序遍历的序列。答：前序序列： ABCEDFHGI 中序序列： ECBHFDJIGA 后序序列： ECHFJIGDBA【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。答：可以生成如上二叉排序树的关键字的初始排列有30种 任写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，

31、1，7，6，3）【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答：（1） 画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）；答： 11 7 13 4 16 22 5 （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）； 11 5 16 4 7 13 22 【14，4，6】 假设一个文本使用的字符集为a,b,c,d,e,f,g, 字符的哈夫曼编码依次为0110，10，110，111，00，0111，010。（1） 请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；答：01010001111egbcd（2） 若这些字符在文本中出现的频

32、率分别为：3,35,13,15,20,5,9，求该哈夫曼树的带权路径长度。答：WPL=4*(3+5)+3*(9+13+15)+2*(20+35)=253【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。答：924300【16，5，4】设有一组关键字29，01，13，15，56，20，87，27，69，9，10，74，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。答：首先将各个数除以17取余数：（6,2,7,1,2,7,7,6）可见20,85与46冲突，58与71冲突。将7+1再对13取余，直到无冲

33、突，类似的6+1对13取余，最后可得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 10 14 28 2 71 46 20 85 58 平均查找长度=（1×4+2×2+3×1+4×1）/8=15/8【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod Ta

34、bleSize，要求装入因子为0.7。答：（1）由装载因子0.7，数据总数7个存储空间长度为10P=10所以，构造的散列表为：01234567893071411818.9.H（7）=（7×3）MOD10=1（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2【18，6，3】已知一个无向图的顶点集为V0，V1，V7，其邻接矩阵如下所示：V0 0 1 0 1 1 0 0 0V1 1 0 1 0 1 0 0 0V2 0 1 0 0 0 1 0 0V3 1 0 0 0 0 0 1 0V4 1 1 0 0

35、 0 0 1 0V5 0 0 1 0 0 0 0 0V6 0 0 0 1 1 0 0 1V7 0 0 0 0 0 0 0 1(1) 画出该图的图形； 答：23104756(2) 给出从V0出发的深度优先遍历序和广度优先遍历序。答：深度优先序列 V0,V1,V2,V5,V4,V6,V3,V7广度优先序列 V0 V1 V3 V4 V2 V6 V5 V7【19，6，3】已知有向图如右图所示，请给出该图的（1） 每个顶点的入度和出度； （2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 各个强连通分量。答： （1）各顶点的入度和出度如下：3/0 2/2 1/2 1/2 2/1 2/3（2）邻接

36、矩阵如下：123456100000021001003010001400101151000006110010（3）邻接表如下： 6 5425 21631112345623424366 64（4）逆邻接表如下：123456（5）有三个强连通分量: 【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。答：1 c:2 2 c:2 f:6 3 c:2 f:6 e:10 4 c:2 f:6 e:10 d:115 c:2 f:6 e:10 d:11 g:14 6 c:2 f:6 e:10 d:11 g:14 b:15【21，6，3】给出如下图所

37、示的具有7个结点的网G。请：（1） 画出该网的邻接矩阵；（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法的执行过程及最小生成树的生成示意图）。0123645164432315725答：void prim(MGraph g,int v0,int &sum)   int lowcostMAXSIZE,vsetMAXSIZE;   int v,preMAXSIZE;             &

38、#160;   /pre存入前驱结点数组   int i,j,k,min;   v=v0;                                /初始起点   for(i=1;i<=g.n;i+

39、)      lowcosti=g.edgesv0i;       /lowcost的数组      prei=v0;      vseti=0;      vsetv0=1;   sum=0;   for(i=1;i      min=INF; &

40、#160;    for(j=1;j<=g.n;j+)          if(vsetj=0&&lowcostj             min=lowcostj;             k=j; 

41、60;                      vsetk=1;        /将此结点并入到所够造的生成树中      v=k;      if(min!=INF)      

42、;    printf("边的起点为：   %d   终点为：    %d   权值为    %dn",prev,v,min);          sum+=min;               el

43、se          break;            for(j=1;j<=g.n;j+)/并入新结点后修改剩下的结点到生成树的权值          if(vsetj=0&&g.edgesvj        &

44、#160;    lowcostj=g.edgesvj;             prej=v;   /并记其下全趋结点                   【22，7，4】给定数组48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 7

45、2, 17，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。答：简单选择排序：6，25，48， 90, 17, 84, 62, 48, 27, 96, 49, 72, 176，17， 48， 90,25, 84, 62, 48, 27, 96, 49, 72, 176，17， 17， 90,25, 84, 62, 48, 27, 96, 49, 72, 486，17， 17， 25,90 84, 62, 48, 27, 96, 49, 72, 486，17， 17， 25, 27, 84, 62, 48, 90 96, 49, 72, 486，17， 17， 25, 27, 48 62 84