浙大数据结构与算法离线作业.docx

1、浙大数据结构与算法离线作业大学远程教育学院数据结构与算法课程离线作业：学 号：年级：2016春学习中心：一、填空题：（【序号，章，节】。）【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+

2、) for (j=0; jn; 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-ne

3、xt; 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-next;(2) P

4、-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;(13) L = L

5、-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); else print

6、f(“%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。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。【20，4，2】已知一棵树边的集合是,。那么根结点是 e ，结点b的双亲是

7、d ，结点a的子有 bcdj ，树的深度是 4 ，树的度是 3 ，结点g在树的第 3 层。【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。【22，4，3】满三叉树的第i层的结点个数为 3i-1 ，深度为h时该树中共有 3h-1 结点。【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。则该完全二叉树总共结点有 111 个；有 7 层；第91号结点的双亲结点是 45 号；第63号结点的左孩子结点是 32 号。【24，4，3】下列表示的图中，共有

8、 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 (di = 12,22,32,)解决

9、冲突，在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 ；通过顶点f的简单回路有 2 条；就连

10、通性而言，该图是 强连通 图；它的强连通分量有 1 个；其生成树可能的最大深度是 5。【32，7，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序 、 快速排序 、 堆排序 。二、综合题（选自教材数据结构各章习题，采用word文件格式上传）【1，1，3】试分析下面一段代码的时

11、间复杂度：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中九韶算法与直接法的效率差别。令，计算的值。利用clock()函数得到两种算法在同一机器上的运行时间。答： 直接法：0.1 s 九韶算法：0.04 s【

12、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/2)+O(N) =22T(N/2)/2+O(N/2)+O(N)=22T(N/2

13、2)+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(N);i+) if (N%i=0) flag=0； break; return fl

14、ag;【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+aaa(n个a)的结果。答：#includestdio.hint 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逐步增大时程序的运行时间。答：#include #define N 8 int n = 0;void swap(int *a, int *b) int m; m=*a; *a=*b; *b=m;

15、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,&listi); 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%

16、10; num=num/10; i+; perm(list,0, i-1); printf(total:%dn,n); 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; /* 函数声明 */

17、LNode *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,&x); /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1，结束循环 */ s=(LNode *)malloc(sizeof(LNode);

18、/* 分配新结点 */ s-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_link */* 删除大于x小于y的值*/void delete_L(LNode *L,int a,int b) LNod

19、e *p,*q; p=L; q=p; p=p-next; if(p=NULL) printf(ERROR:链表为空); while(p!=NULL) if(p-data a) & (p-data next=p-next; free(p); p=q-next; else q=p; p=p-next; /* delete_L */void main() 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); /*

20、 main */【8，3，2】给定一个顺序存储的线性表L = (, , , )，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。答：#include #include using namespace std;#define MAXN 1003int AMAXN;int dpMAXN;/ 动态规划思想O(n2)int main() int n, i, j, k; cin n; for (i=1; i Ai; dp1 = 1; / 有n个阶段 for (i=2; i=0; j-) if (AiAj) dpi = m

21、ax(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 23145 23154 23415 23451 23541 24315 24351 2

22、4531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321【10，3，2】请编写程序将中缀表达式转换为后缀表达式。答:#include #include #include using namespace std;int prior(char op)if(op=+|op=-) return 1;if(op=*|op=/) return 2;return 0;string middletolast(string middle)stack op;string ans; f

23、or(int i=0;i=0&cprior(op.top() op.push(c); else while(!op.empty()&prior(c)mdata; res=middletolast(mdata);for(int i=0;ires.size();i+) if(i=0) coutresi; else cout resi;coutendl;return 0;【11，4，3】设二叉树的存储结构如下：12345678910Lchild00237580101dataJHFDBACEGIRchild0009400000其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针

24、域，data为数据域。（1）画出二叉树的逻辑结构。答：（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，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）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；答：（2）若这些字符在文本中出现的频率分别为：3,35,13,15,20,5,9