《2016浙大数据结构与算法离线作业》由会员分享，可在线阅读，更多相关《2016浙大数据结构与算法离线作业（32页珍藏版）》请在金锄头文库上搜索。
1、1浙江大学远程教育学院数据结构与算法数据结构与算法课程离线作业课程离线作业姓名：姓名：学学 号：号：年级：年级：2016 春春学习中心：学习中心：一、填空题：（一、填空题：（【序号，章，节】 。 。 。 。 。 。 ）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多 关系，图形结构中元素之间存在 多对多 关系。【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构 ， 链式存储结构。【4，1，3】度量算法效率可通过 时间复杂度 来进行。【5，1，3】设 n 为正整数，下面
2、程序段中前置以记号的语句的频度是 n(n+1)/2 。for (i=0; inext=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-next-next ;free(q);【12，3，2】带头结点的单循环链表 Head 的判空条件是 Head-next=Head； 不带头结点的单循环链表的判空条件是 Head=NULL
3、。【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-next = P-next -next;(4) P = P-next -next;(5) whilewhile (P != NULLNULL) P = P-next;(6) whilewhile
4、(Q-next != NULLNULL)P = Q; Q = Q-next;(7) whilewhile (P-next != Q) P = P-next;(8) whilewhile (P-next-next != Q) P = P-next;(9) whilewhile (P-next-next != NULLNULL) P = P-next;(10) Q = P;(11) Q = P-next;(12) P = L;3(13) L = L-next;(14) freefree (Q);【14，3，3】对一个栈，给定输入的顺序是 A、B、C，则全部不可能的输出序列有 CAB 。【15，3，
5、3】.在栈顶指针为 HS 的链栈中，判定栈空的条件是 head-next=NULL 。【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。void conversion10_16() InitStack(scanf(“%d”,while(N)Push(s,N%16) ;N = N/16;while(!StackEmpty(s)Pop(s,e) ;if(e,。那么根结点是 e ，结点 b 的双亲是 d ，结点 a 的子孙有 bcdj ，树的深度是 4 ，树的度是 3 ，结点 g 在树的第 3 层。【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的
6、基本的目的是 采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。【22，4，3】满三叉树的第 i 层的结点个数为 3i-1 ，深度为 h 时该树中共有 3h-1 结点。【23，4，3】已知一棵完全二叉树有 56 个叶子结点，从上到下、从左到右对它的结点进行编号，根结4点为 1 号。则该完全二叉树总共结点有 111 个；有 7 层；第 91 号结点的双亲结点是 45 号；第 63 号结点的左孩子结点是 32 号。【24，4，3】下列表示的图中，共有 5 个是树；有 3 个是二叉树；有 2 个是完全二叉树。【25，4，4】n 个结点的二叉排序树的最大深度是 n ，最小深度为 log2n
7、+1 。【26，4，3】如果某二叉树的后序遍历序列是 ABCDEFGHI，中序遍历序列是 ACBIDFEHG，则其先序遍历序列的第一个字母是 I ，最后一个字母是 G 。【27，4，3】下列二叉树的中序遍历序列是 DBNGOAEC ;后序遍历序列是 DNIGBECA 。5【28，5，4】设 HASH 表的大小为 n n (n=10), HASH 函数为 h(x)=xh(x)=x % % 7,7, 如果二次探测再散列方法 Hi=(H(key)+di) mod 10 (di = 12,22,32,)解决冲突，在 HASH 表中依次插入关键字1,14,55,20,84,27以后，关键字 1、20 和
8、 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 ；通过顶点 f 的简单回路有 2 条；就连通性而言，该图是 强连通 图；它的强连通分
9、量有 1 个；其生成树可能的最大深度是 5 。【32，7，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是 60）插入到有序表时，为寻找插入位置需比较 3 次。【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。6二、综合题（选自教材二、综合题（选自教材数据结构数据结构各章习题，采用各章习题，采用 wordword 文件格式上传）文件格式上传）【1
10、，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 的平方。整段取最大的，时间复杂度就是 N 立方。【2，1，3】测试例 1.3 中秦九韶算法与直接法的效率差别。令，计算的ixxfii/1)(1001
11、) 1 . 1 (f值。利用 clock()函数得到两种算法在同一机器上的运行时间。答： 直接法：0.1 s 秦九韶算法：0.04 s【3，1，3】 试分析最大子列和算法 1.3 的空间复杂度。答：算法 1.3 的基本思路是将原问题拆分成若干小型问题，分别解决后再将结果合而治之，用递归方法实现。算法 1.3 的负责度分析略有难度：若记整体时间复杂度为 T(N)，则函数 DivideAndConquer 中通过递7归实现“分”的复杂度为 2T(N/2)，因为我们解决了 2 个长度减半的字问题。求跨分界线的最大子列和时，有两个简单的 for 循环，所用步骤一共不超过 N，所以可以在 O(N)时间完
12、成。其他步骤都只需常熟O(1)时间。综上分析则有递推式：T(1)=O(1)；T(N)=2T(N/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】试给出判断是否为质数的的算法。N)( NO答:int sushu(int N) int i;int flag=1;if (N=1) return fal
13、se; /1 既不是合数也不是质数if (N=2) return truefor (i=2;i #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 #include #include typedef int ElemType; typedef struct LNode ElemType data; /* 数据子域 */struct LNode *next; /* 指针子域 */LNode; /
14、* 结点结构类型 */LNode *L; /* 函数声明 */ 12LNode *creat_L();void delete_L(LNode *L,int i); /返回值格式变为空/* 建立线性链表*/LNode *creat_L() LNode *h,*p,*s; ElemType x;h=(LNode *)malloc(sizeof(LNode); /* 分配头结点 */h-next=NULL;p=h;printf(“输入一串数字（以-1 结束）:ndata= “);scanf(“%d“, /* 输入第一个数据元素 */while( x!=-1) /* 输入-1，结束循环 */s=(LNode *)malloc(sizeof(LNode); /* 分配新结点 */s-data=x; s-next=NULLp-next=s; p=s;printf(“data= “);scanf(“%d“, /* 输入下一个数据*/return(h);13 /*
