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

1、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

2、ext=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。【13，3，2】已知 L 是带表头结点的非空单链表, 且 P 结点既然不首元

3、结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。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) while (P != NULL) P = P-next;(6) while (Q-next != NULL)P = Q; Q = Q-next;(7) while (P-next !

4、= 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;3(13) L = L-next;(14) free (Q);【14，3，3】对一个栈，给定输入的顺序是 A、B、C，则全部不可能的输出序列有 CAB 。【15，3，3】.在栈顶指针为 HS 的链栈中，判定栈空的条件是 head-next=NULL 。【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。

5、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】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是 采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。【22，4，3】满三叉树的第 i 层的结点个数为 3 i-1 ，深度为 h 时该树中

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

7、个字母是 G 。【27，4，3】下列二叉树的中序遍历序列是 DBNGOAEC ;后序遍历序列是 DNIGBECA 。5【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 的边集

8、合，则对应元素 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 条；就连通性而言，该图是 强连通 图；它的强连通分量有 1 个；其生成树可能的最大深度是 5 。【32，7，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。【33，7，2】在对一组关键字是（54,38,96,45,

9、15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是 60）插入到有序表时，为寻找插入位置需比较 3 次。【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。6二、综合题（选自教材数据结构各章习题，采用 word 文件格式上传）【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 次，内循环

10、为 N（N-1）次，因此时间复杂度为 O(N* N（N-1）)，也就是 N 的三次方。 if AB 为假，则 for 语句的外循环 2N 次，内循环为 N 次，因此时间复杂度为 O（2N*N） ，也就是 N的平方。整段取最大的，时间复杂度就是 N 立方。【2，1，3】测试例 1.3 中秦九韶算法与直接法的效率差别。令 ，计算 的ixxfi/1)(0)1.(f值。利用 clock()函数得到两种算法在同一机器上的运行时间。答： 直接法：0.1 s 秦九韶算法：0.04 s【3，1，3】 试分析最大子列和算法 1.3 的空间复杂度。答：算法 1.3 的基本思路是将原问题拆分成若干小型问题，分别解决

11、后再将结果合而治之，用递归方法7实现。算法 1.3 的负责度分析略有难度：若记整体时间复杂度为 T(N)，则函数 DivideAndConquer 中通过递归实现“分”的复杂度为 2T(N/2)，因为我们解决了 2 个长度减半的字问题。求跨分界线的最大子列和时，有两个简单的 for 循环，所用步骤一共不超过 N，所以可以在 O(N)时间完成。其他步骤都只需常熟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=

12、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 false; /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 = m; i+)printf(“%d“, listi);printf(“n“);10n+;elsefor(i = k; i = m; i+)swap(perm(list,k + 1, m);swap(int main()int listN;int num,i=0;printf(“Pleaseinput a num:“);scanf(“%d“,while(num != 0)