浙江大学远程教育-数据结构与算法-离线作业及答案.docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《浙江大学远程教育-数据结构与算法-离线作业及答案.docx》由会员分享,可在线阅读,更多相关《浙江大学远程教育-数据结构与算法-离线作业及答案.docx(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、浙江大学远程教育学院数据结构与算法课程离线作业姓名:学 号:年级:学习中心:一、填空题:(【序号,章,节】。)【1,1,2】线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。【2,1,2】为了最快地存取数据元素,物理结构宜采用 顺序存储 结构。【3,1,2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构_, 链式存储结构_。【4,1,3】度量算法效率可通过 时间复杂度_来进行。【5,1,3】设n 为正整数,下面程序段中前置以记号的语句的频度是 n(n+1)/2 。 for (i=0; in; i+) for (j=0; j
2、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; jnext=NULL _。【10,3,2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点,应执行s-next=_ p-next _;和p-next=_ s _的操作。【11,3,2】在一个单链表中删除p所指结点时,应执行以下操作: q= p-next
3、; p-data= p-next-data; p-next= P-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-
4、next;(2) P-next = P;(3) P-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) Q = P;(11) Q = P-next;(12) P = L;
5、(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; while(!StackEmpty(s) _Pop(s,e) ; if(e=9)printf(“%d”,e);
6、 else printf(“%c”,e-10+A); /* conversion */【17,3,4】若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front=3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是 和 。【18,3,4】堆栈和队列都是线性表, 堆栈是_后进先出_的线性表, 而队列是_先进先出_的线性表。【19,3,4】若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front=3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是 2 和 4 。【20,4,2】已知一棵树边的集合是,。那么根结点是
7、e ,结点b的双亲是 d ,结点a的子孙有 bcdj ,树的深度是 4 ,树的度是 3 ,结点g在树的第 3 层。【21,4,3】从概念上讲,树与二叉树是二种不同的数据结构,将树转化为二叉树的基本的目的是树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。【22,4,3】满三叉树的第i层的结点个数为 3i-1 ,深度为h时该树中共有 3-1h 结点。【23,4,3】已知一棵完全二叉树有56个叶子结点,从上到下、从左到右对它的结点进行编号,根结点为1号。则该完全二叉树总共结点有_111_个;有_7_层;第91号结点的双亲结点是_45_号;第63号结点的左孩子结点是_32_号。【24,
8、4,3】下列表示的图中,共有_5_个是树;有_3_个是二叉树;有_2_个是完全二叉树。【25,4,4】n个结点的二叉排序树的最大深度是 n ,最小深度为 log2n+1 。【26,4,3】如果某二叉树的后序遍历序列是ABCDEFGHI,中序遍历序列是ACBIDFEHG,则其先序遍历序列的第一个字母是 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 (d
9、i = 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的边集合,则对应元素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=,。那么顶点e的入度是 2 ;出度是 1 ;通
10、过顶点f的简单回路有 2 条;就连通性而言,该图是 强连通 图;它的强连通分量有 1 个;其生成树可能的最大深度是 5。【32,7,1】排序过程一般需经过两个基本操作,它们是 比较 和 移动 。【33,7,2】在对一组关键字是(54,38,96,45,15,72,60,23,83)的记录进行直接插入排序时,当把第七个记录(关键字是60)插入到有序表时,为寻找插入位置需比较 3 次。【34,7,4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中,不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。二、综合题(选自教材数据结构各章习题,采用word文件格式上传)【
11、1,1,3】试分析下面一段代码的时间复杂度:if ( A B ) for ( i=0; ii; j- ) A += B;else for ( i=0; ii; j- ) A += B;If AB为真,则for语句的外循环N次,内循环为N(N-1)次,因此时间复杂度为O(N*N(N-1),也就是N的三次方。If AB为假,则for语句的外循环2N次,内循环为N次,因此时间复杂度为O(2N*N),也就是N的平方。【2,1,3】测试例1.3中秦九韶算法与直接法的效率差别。令,计算的值。利用clock()函数得到两种算法在同一机器上的运行时间。f(1.1)=137797.40625【3,1,3】 试分
12、析最大子列和算法1.3的空间复杂度。【4,1,3】试给出判断是否为质数的的算法。Int sushu(in N)int i;Int flag=1;If(N=1)return false;If(N=2) return ture;for(i=2;i=sqrt(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.hint main()int a,b,n,i,s=0;scanf(%d %d,&a,&n);b=a;for(i=1;i=n;i+)s+=
13、a;a=a*10+b;printf(%dn,s);【6,2,3】请编写递归函数,输出123.n的全排列(n小于10),并观察n逐步增大时程序的运行时间。#include #define swap(a,b)int t=a;a=b;b=t;void permutation (int*a,int b,int e)int i;if (b=e)for (i=0;ie;+i)printf(%d,ai)printf(n);elsefor(i=b;ie;+i)swap(ab,ai);permutation(a,b+1,e);swap(ab,ai);int main(void)int a4=1,2,3,4;pe
14、rmutation(a,0,4);return 0;【7,3,2】 给定一个顺序存储的线性表L = (, , , ),请设计一个算法删除所有值大于min而且小于max的元素。#include #include #include typedef int ElemType;typedef struct LNode ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ LNode; /* 结点结构类型 */LNode *L; /* 函数声明 */LNode *creat_L();void delete_L(LNode *L,int i);
15、/返回值格式变为空/* 建立线性链表*/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-data=x; s-next=NULL; p-next=s; p=s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浙江大学 远程教育 数据结构 算法 离线 作业 答案
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内