




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 环境卫生科医院清洁消毒工作计划
- 2025年婚内协议书手写模板电子版
- 福建省建瓯市第二中学初中体育《跨越式跳高》体育课教学实录
- 2025年有机颜料:偶氮颜料项目发展计划
- 教学设计-浙教信息技术六下第13课 《扩音系统的优化》
- 劳动合同试用期合同(2025年版)
- 三年级下册数学教案-5.1.认识年、月、日-苏教版
- 七 用方程解决问题(新教案)2024-2025学年五年级下册数学【探究乐园】高效课堂(北师大版)教用
- 2025年泰安驾校考试货运从业资格证考试
- 书籍出版合同(2025年版)
- 百融云创风险决策引擎V5产品操作手册
- GB 15979-2024一次性使用卫生用品卫生要求
- 2024年合肥市轨道交通集团有限公司招聘笔试冲刺题(带答案解析)
- CJJT8-2011 城市测量规范
- 故事绘本后羿射日
- 产前筛查标准技术操作规程
- 2024年广州市高三一模高考物理试卷试题答案(精校打印)
- 国测省测四年级劳动质量检测试卷
- SAT真题 2023年6月 亚太卷
- 中外室内设计史全套教学课件
- 02章 电催化过程
评论
0/150
提交评论