浙大远程数据结构与算法离线复习资料完整版.docx

浙江高校远程教化学院数据构造及算法课程离线作业一、填空题：（【序号，章，节】。）【1，1，2】线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。【2，1，2】为了最快地存取数据元素，物理构造宜采纳 序存储 构造。3，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; 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)有两种存储构造： 依次存储构造和链式存储构造，请就这两种存储构造完成下列填充： _依次存储构造_ 存储密度较大；_依次存储构造_存储利用率较高；_依次存储构造_可以随机存取；_链式存储构造_不行以随机存取；_链式存储构造_插入和删除操作比拟便利。【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->next->next _ ; free(q);【12，3，2】带头结点的单循环链表Head的判空条件是_ Head->next=null _； 不带头结点的单循环链表的判空条件是_ 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->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->next;(14) free (Q);【14，3，3】对一个栈，给定输入的依次是A、B、C，则全部不行能的输出序列有 C A B 。【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 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。当从队列中删除一个元素，再参加两个元素后，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，4，3】满三叉树的第i层的结点个数为 3i-1 ，深度为h时该树中共有 3h-1 结点。【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进展编号，根结点为1号。则该完全二叉树总共结点有_111_个；有_7_层；第91号结点的双亲结点是_45_号；第63号结点的左孩子结点是_号。【24，4，3】下列表示的图中，共有_5_个是树；有_3_个是二叉树；有_2_个是完全二叉树。【25，4，4】n个结点的二叉排序树的最大深度是 n ，最小深度为 log2+1 _ 【26，4，3】假如某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先序遍历序列的第一个字母是 I ，最终一个字母是 G【27，4，3】下列二叉树的中序遍历序列是_ DBNGOAEC _ _;后序遍历序列是_ DNOGBECA _。【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所在地址的下标分别是 、 _ 和 。插入上述6个元素的平均比拟次数是 。答案：1、7、5、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=<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>。那么顶点e的入度是 2 ；出度是 1 ；通过顶点f的简洁回路有 2 条；就连通性而言，该图是 强连通图 图；它的强连通重量有 1 个；其生成树可能的最大深度是 5。【32，7，1】排序过程一般需经过两个根本操作，它们是 比拟 和 挪动 。【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进展干脆插入排序时，当把第七个记录（关键字是60）插入到有序表时，为找寻插入位置需比拟 3 次 分别及54、72、96比拟【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有选择排序、快速排序、堆排序、希尔排序二、综合题（选自教材数据构造各章习题，采纳word文件格式上传）【1，1，3】试分析下面一段代码的时间困难度：if ( A > B ) for ( i=0; i<N; i+ ) 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中的时间困难度为：O(n*n²)即O(n³)else中的时间困难度为：O(n*n)即O(n²)【2，1，3】测试例1.3中秦九韶算法及干脆法的效率差异。令，计算的值。利用clock()函数得到两种算法在同一机器上的运行时间。答：从运行结果可以看出秦九昭算法效率上有很大优势；#include <stdio.h>#include <time.h>#include <math.h>clock_t start,stop;double duration;#define MAXN 10#define MAXK 1e7double f1(int n ,double a,double x);double f2(int n ,double a,double x);/秦九昭算法double f1(int n ,double a,double x)int i =0 ;double p = a0;for(i=n;i>0;i-)p = ai-1 + x * p;return p;/干脆算法double f2(int n ,double a,double x)int i =0 ;double p = a0;for(i=n;i>0;i-)p += ai*pow(x,i);return p;int main()int i ;double aMAXN ;for(i=0;i<MAXN;i+)ai=(double)i;start = clock();for(i=0;i<MAXK;i+)f2(MAXN-1,a,1.1);stop = clock();duration = (double)(stop-start)/CLK_TCK/MAXK ;printf("干脆算法：");printf("ticks = %fn",(double)(stop-start);printf("duration = %6.2en",duration);for(i=0;i<MAXN;i+)ai=(double)i;start = clock();for(i=0;i<MAXK;i+)f1(MAXN-1,a,1.1);stop = clock();printf("秦九昭算法：");printf("ticks = %fn",(double)(stop-start);printf("duration = %6.2en",duration);return 0;【3，1，3】 试分析最大子列和算法1.3的空间困难度。答：在1.4中存在4种解决最大子列的算法，详细空间困难度如下：1、 穷举法：算法并没有开拓另外的存储空间进展存储，利用的是累加所以空间困难度为O(2);2、 局部穷举：同上3、 分而治之：利用递归解决问题，故空间困难度为O(N);4、 在线处理：为O(2);【4，1，3】试给出推断是否为质数的的算法。答案：#include <stdio.h>#include <math.h>int is_prime(int n)int i = 0; if(n!= 2 && n % 2 = 0) return 0; for(i=3;i<=sqrt(double)n);i+=2) if(n % i = 0) return 0; return 1;void main()int num = 0 ,result =0 ;printf("Input the num:"); scanf("%d", &num);result = is_prime(num); if(result) printf("%d is a primen", num); else printf("%d is not a primen", num);Input the num: 55 is a prime.【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逐步增大时程序的运行时间。答案：#include <stdio.h>#include <time.h>void pailie(int* data, int n, int curr)int i = 0 ; if (curr=n-1) for (i = 0; i < n; +i ) printf("%d", datai); printf("n"); else for (i = curr; i < n; +i) int t; t = datacurr, datacurr = datai, datai = t; pailie(data, n, curr+1); t = datacurr, datacurr = datai, datai = t;int main()clock_t end;clock_t start = clock(); int n = 0;int i = 0; int as10 = 0,0,0,0,0,0,0,0,0,0;/n小于等于10 scanf("%d", &n); for (i = 0; i < n; +i) asi = i+1; pailie(as, n, 0);end = clock();printf("The time was: %dn", (end - start) / CLK_TCK); return 0;N为7N为9分析来看时间上虽然有比拟大的增长，但主要用于打印；但在时间困难度上是随着n的变大呈直线上升趋势；【7，3，2】 给定一个依次存储的线性表L = (, , ¼, )，请设计一个算法删除全部值大于min而且小于max的元素。SeqList Delete(SeqList &L, int min, int max) int i;=0,j=0 for (i=0; i<L.Length; i+) if(L.elemi>min && L.elemi<max)for(j=i;j<L.length;j+)L.elemj=L.elemj+1;-L.length; return L ;【8，3，2】给定一个依次存储的线性表L = (, , ¼, )，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。void main() int n, i, j, k; int A1024=;int dp1024=; scanf("%d", &n); for (i=1; i<=n; i+) scanf("%d", Ai); dp1 = 1; / 有n个阶段 for (i=2; i<=n; i+) dpi = 1; / 每个阶段只有1个状态 / 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度 for (j=i-1; j>=0; j-) if (Ai>Aj) dpi = max(dpi, dpj+1); int maximum = dp1; for (i=2; i<=n; i+) maximum = max(maximum, dpi); printf("%d maximum is : n", maximum);【9，3，3】 假如有1、2、3、4、5按依次入栈，不同的堆栈操作（pop, push）依次可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？答案：依据正常状况，1,2,3,4,5的全排列组合共有5! = 120,即120种，但由于 像：12435、12534之类的无法按依次出入栈，故依据依次入栈的状况共有56种：以1开场排列组合为14种以2开场排列组合为14种以3开场的排列组合为9种以4开场的排列组合为4种以5开场的排列组合为1种【10，3，2】请编写程序将中缀表达式转换为后缀表达式。答案：运用栈的循序存储构造实现、栈的依次存储构造，用一维数组实现 #include <stdio.h> #include <stdlib.h>#define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0 #define MAXSIZE 10 typedef int Status; typedef char ElemType; typedef struct ElemType dataMAXSIZE; int top;/栈顶指针 Stack; /1. 初始化 Status InitStack(Stack *S) int i; for(i=0;i<MAXSIZE;i+) S->datai=NULL; S->top=-1; return OK; /2. 创立一个长度为n的堆栈 Status CreateStack(Stack *S,int n) int i =0; if(n>MAXSIZE | n<1) printf("输入长度有误！n"); return ERROR; for(i=0;i<n;i+) S->datai=rand()%100+1; S->top=n-1; return OK; Status push(Stack *S,ElemType e) if(MAXSIZE-1=S->top) printf("栈已满n"); return ERROR; /栈顶指向的元素有值 +(S->top); S->dataS->top=e; return OK; /4. 出栈 Status pop(Stack *S,ElemType *e) /将栈顶元素出栈，传给e if(-1=S->top) printf("栈为空！n"); return ERROR; *e=S->dataS->top; -(S->top); return OK; /5. 中缀表达式转后缀表达式 void MidToFinal(char *mid,char *final) /中缀表达式为middle，要转换成后缀表达式传给last /新建一个栈，来存储符号 char e; Stack S; if(OK!=InitStack(&S) printf("初始化栈失败！n"); /当带转换的字符串*mid未终止时，循环处理 while(*mid) /假如是数字，则干脆输出 if(*mid>='0' && *mid<='9') *(final+)=*(mid+); continue; else if(*mid='+' | *mid='-' | *mid='*' | *mid='/' | *mid='(' | *mid=')') /输入的是合法运算符号,比拟之前是否有更高优先级的符号 if(S=-1 | '('=*mid) /当符号栈为空或遇到左括号时，符号入栈 push(&S,*(mid+); continue; if(')'=*mid) /遇到右括号时，栈顶元素依次出栈；直到遇到第一个左括号时完毕 pop(&S,&e); *(final+)=e; while(pop(&S,&e) && e!='(') *(final+)=e; / printf("%cn",e); mid+; continue; /后续的处理都要取出临时的栈顶元素，及当前输入的符号*mid相比拟；当临时栈顶元素优先级大于等于输入符号的优先级时，出栈；否则符号入栈（已经弹出一个，记得把弹出的元素也入栈） pop(&S,&e); if('+'=*mid | '-'=*mid) if(e='(') push(&S,'('); push(&S,*(mid+); continue; else *(final+)=e; push(&S,*(mid+); continue; else if('*'=*mid | '/'=*mid) if('*'=e | '/'=e) *(final+)=e; push(&S,*(mid+); continue; else push(&S,e); push(&S,*(mid+); continue; else printf("输入的字符不合法！%cn",*mid); return; /当待转换的字符已经完毕时，符号栈至少还有一个元素（中缀表达式的特点：数字结尾；后缀表达式以符号结尾）；将栈中的元素依次出栈 while(S!=-1) pop(&S,&e); *(final+)=e; /字符串的完毕符！ *final='0' int main() char data="3+(5*6-7/1*7)*9" char final="" MidToFinal(data,final); printf("%sn",final); return 0; 【11，4，3】设二叉树的存储构造如下：12345678910Lchild00237580101dataJHFDBACEGIRchild0009400000其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。（1） 画出二叉树的逻辑构造。（2） 写出该树的前序、中序和后序遍历的序列。答：前序遍历：ECBHFDJIGA中序遍历：ABCEDFHGIJ后序遍历：ECHFJIGDBA【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的随意5个。解：30种。任写5个序列如下：（5，4，7，6，2，3，1）；（5，7，4，6，2，3，1）；（5，4，7，2，3，1，6）；（5，7，6，4，2，3，1）；（5，7，6，4，2，1，3）【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请答复：（1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）；（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；答：（1）（2）【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，求该哈夫曼树的带权途径长度。答：【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。答：公式5.6如下h(key)=key mod 11;身份证号码信息如下：362429198307050010，设身份证为数字类型，对11求余后为4【16，5，4】设有一组关键字29，01，13，15，56，20，87，27，69，9，10，74，散列函数为：H(key) = key % 17，采纳平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。答：散列地址012345678910111213141516说明插入2929无冲突插入0101无冲突插入1313无冲突插入1515无冲突插入5656无冲突插入2020无冲突插入8787无冲突插入2727无冲突插入6969d2=-1插入99无冲突插入1010d1=1插入7474无冲突【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开场的一个一维数组。处理冲突采纳线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。答：tableSize为7/0.7，即10，散列函数为h(key)=(key*3) mod 10;下面为散列表插入过程散列地址0123456789说明插入77无冲突插入88无冲突插入3030无冲突插入1111无冲突插入1818d1=1插入99无冲突插入1414无冲突【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 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) 画出该图的图形； (2) 给出从V0动身的深度优先遍历序和广度优先遍历序。答：深度优先：广度优先：【19，6，3】已知有向图如右图所示，请给出该图的（1） 每个顶点的入度和出度； （2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 各个强连通重量答案：（1）：节点号入度出度130222312413521623（2）：1 0 1 0 0 1 1 2 1 0 1 1 0 1 3 0 1 0 1 0 1 4 0 1 1 0 1 1 5 1 0 0 1 0 1 6 1 1 1 1 1 0 (3)：（4）：（5）：1：无强连通重量【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短间隔 及对应的途径，写出计算过程中各步状态。答：初始（第0步）第一步（选C）第二步(选F)第三步(选E)第四步(选G)第五步(选D)第六步(选B)终点DPDPDPDPDPDPDPB15015A15A15A15A15A15AC202A2A2