浙大数据结构与算法离线作业————————————————————————————————作者：————————————————————————————————日期:ﻩ浙江大学远程教育学院《数据结构与算法》课程离线作业姓名:学号:年级：2016春学习中心：—————————————————————————————一、填空题：(【序号,章，节】。

）【１，１,2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。

【2，１，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。

【３，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构 , 链式存储结构。

【4，１，3】度量算法效率可通过时间复杂度来进行。

【5,1,３】设n 为正整数,下面程序段中前置以记号@的语句的频度是ｎ(n＋１)/2 。

fｏｒ(i=０; i<n; i++)｛for (j=0; j＜n; j+＋）ｉｆ (i+j＝=ｎ－１)@ a[i]［ｊ]=０;｝【6,１,3】设ｎ为正整数,试确定下列各程序段中前置以记号@的语句的频度:（1) i=1； k=0;whｉｌｅ（i<=n－1){i++；@ k＋=１0 ＊ i； // 语句的频度是n-1。

}(２） k=0;for (i＝1; i<＝n; i++）{for (j=i; ｊ<=n; j＋+)@ k+＋; // 语句的频度是n(n+1)/2。

}【7,３,2】线性表（a1,a２，…，a n)有两种存储结构: 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充:顺序存储密度较大；顺序存储利用率较高;顺序可以随机存取；链式不可以随机存取；链式插入和删除操作比较方便。

【8,3,２】从一个长度为n的顺序表中删除第ｉ个元素(1≤i≤n)时，需向前移动n－ｉ个元素。

【９,3,2】带头结点的单链表Heaｄ为空的条件是Head-＞nexｔ=NUＬＬ。

【10,3，2】在一个单链表中ｐ所指结点（p所指不是最后结点)之后插入一个由指针s所指结点,应执行s->neｘt=_p-＞next;和p->next＝ｓ的操作。

【11，3,2】在一个单链表中删除p所指结点时，应执行以下操作：ｑ= p-＞ｎext；p->data= p->next-＞daｔａ；ｐ->ｎｅxｔ＝ p->next->ｎext ；frｅe(q);【1２，3，2】带头结点的单循环链表Head的判空条件是Head-＞nexｔ==Head；不带头结点的单循环链表的判空条件是Heａd==NUＬL。

【13，3,2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。

a．删除P结点的直接前驱结点的语句序列是１0 12 8 １1 4 14。

b. 删除结点P的语句序列是10 １2 7 ３ 1４。

c. 删除尾元结点的语句序列是９ 1１ 3 1４。

(１）P ＝P->nexｔ;（２） P－>ｎext ＝Ｐ;（3) P－>neｘt = Ｐ->next ->next;（４）Ｐ＝P->nｅxｔ -＞neｘt;(5) whiｌe (P ！= NULL）Ｐ＝ P->ｎext;(6) ｗhile (Q－>neｘt != NＵLL）{P = Q; Q ＝Ｑ－>ｎｅｘｔ}；(7） whｉｌe (P－>ｎｅxｔ！= Q) Ｐ＝ P－>nexｔ;(8)ｗhｉle （P-＞nexｔ->nｅxｔ！＝Q）P = P->ｎｅxｔ；(9) wｈｉlｅ（P－>nexｔ->neｘｔ != ＮULL) Ｐ = Ｐ－>next;(1０) Q = Ｐ;(１1）Ｑ= P->nｅxt;（１2）P ＝Ｌ;（13) L = Ｌ－>next;（１4）frｅe (Ｑ);【１4,3，3】对一个栈，给定输入的顺序是A、B、C,则全部不可能的输出序列有CAＢ。

【1５，3,3】.在栈顶指针为ＨS的链栈中，判定栈空的条件是hｅad－>ｎext==NULL 。

【１6,３，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。

voｉd ｃｏnvｅrsioｎ10_16(){ InitSｔａｃk(&ｓ)；scａｎf(“%d”，&N);ｗｈｉlｅ（N){Ｐｕｓh(s,N%16) ;N = N/16;}ｗhｉlｅ（!ＳｔackEｍｐｔy（ｓ)）{Pop(s,e) ;ｉf(ｅ＜＝9)ｐrintf(“%d”,e)；elｓe ｐrｉｎtｆ(“％ｃ”,e-10+’A’);}} ／* ｃonveｒsioｎ *／【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rｅａr=0和froｎt＝３。

当从队列中删除一个元素,再加入两个元素后,rear和fｒoｎｔ的值分别是 2 和 4 。

【18，３，4】堆栈和队列都是线性表, 堆栈是后进先出的线性表, 而队列是先进先出的线性表。

【1９,3，4】若用一个大小为６个元素的数组来实现循环队列,且当前ｒｅar=0和fｒoｎt=3。

当从队列中删除一个元素,再加入两个元素后,rear和fronｔ的值分别是２和 4 。

【２0，４,2】已知一棵树边的集合是{<a，d>,<d,c＞,＜ｄ，ｊ>,<e,a>,<f,g＞,<ｄ,b>,＜g,h>，＜g，ｉ>,<ｅ,ｆ>}。

那么根结点是 e ，结点b的双亲是ｄ,结点ａ的子孙有 bｃdｊ,树的深度是４，树的度是３,结点g在树的第 3 层。

【21,4,3】从概念上讲,树与二叉树是二种不同的数据结构,将树转化为二叉树的基本的目的是采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。

【２2,4,３】满三叉树的第i层的结点个数为3i-1 ,深度为h时该树中共有３h-1 结点。

【23，４,３】已知一棵完全二叉树有５６个叶子结点，从上到下、从左到右对它的结点进行编号,根结点为1号。

则该完全二叉树总共结点有 1１１个;有 7 层；第91号结点的双亲结点是 45 号;第63号结点的左孩子结点是32 号。

【24，４,3】下列表示的图中，共有 5 个是树；有３个是二叉树;有 2 个是完全二叉树。

【25,4，4】n个结点的二叉排序树的最大深度是 n ,最小深度为[log2n]+1 。

【２6，４，3】如果某二叉树的后序遍历序列是AＢＣDEFGHI,中序遍历序列是AＣBＩＤＦＥHG,则其先序遍历序列的第一个字母是 I ，最后一个字母是 G 。

【27，4，3】下列二叉树的中序遍历序列是ＤBNGOAEC ;后序遍历序列是DNＩGBECＡ。

【2８，5，4】设HAＳH表的大小为n（n=10），ＨASH函数为ｈ(x)=x % 7,如果二次探测再散列方法Hi=(H(key)＋ｄi） mｏｄ 10 (ｄｉ = 1２,2２，32，…,）解决冲突，在HASH表中依次插入关键字{1,14,55,20,84，27}以后，关键字1、20和2７所在地址的下标分别是 1 、 7 和５。

插入上述６个元素的平均比较次数是 2 。

【2９，6,3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i]［j］等于 1 ，２2、设无向图Ｇ的邻接矩阵为A,若A[i][j]等于０，则A[j］[ｉ]等于０。

【3０，6,3】若一个图用邻接矩阵表示,则删除从第i个顶点出发的所有边的方法是矩阵第i行全部置为零。

【31,6，2】设一个图G=｛V,{A｝｝,V＝{a,b，c,d,e，ｆ},A=｛<a,b>,<ｂ,e>,<a,e>,<c,a>,<ｅ,d>,<d,f>,<f，c>｝。

那么顶点e的入度是 2 ;出度是 1 ;通过顶点f的简单回路有 2 条；就连通性而言，该图是强连通图;它的强连通分量有 1 个；其生成树可能的最大深度是 5 。

【32，７，1】排序过程一般需经过两个基本操作，它们是比较和移动。

【33，7,2】在对一组关键字是（54,38,96,４５,15,72,60，２3，８３)的记录进行直接插入排序时，当把第七个记录(关键字是6０）插入到有序表时，为寻找插入位置需比较 3 次。

【34,7,4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中,不稳定的排序方法有希尔排序、快速排序、堆排序。

ﻬ二、综合题(选自教材《数据结构》各章习题，采用word文件格式上传）【1,1，3】试分析下面一段代码的时间复杂度：if ( Ａ > B ） {f ｏr （ i ＝０; i ＜N ； i+＋ )ｆor ( j=N*Ｎ; j>i; j-－ ）A ＋= B;}ｅlse {f ｏr ( ｉ=0; ｉ<Ｎ＊2; ｉ+＋ )for ( j=N*2; j>ｉ； j －- )A +=B ；}答:i ｆ Ａ＞B 为真,则ｆor 语句的外循环N 次，内循环为N(N －１)次，因此时间复杂度为Ｏ(N ＊ Ｎ(Ｎ-1）)，也就是N 的三次方。

i ｆ Ａ>Ｂ为假，则for 语句的外循环2N 次，内循环为N 次,因此时间复杂度为O(2N*N),也就是N 的平方。

整段取最大的,时间复杂度就是N 立方。

【2，1,３】测试例１.3中秦九韶算法与直接法的效率差别。

令i x x f i i /1)(1001∑=+=,计算)1.1(f 的值。

利用c ｌock()函数得到两种算法在同一机器上的运行时间。

答:直接法：０．1μ ｓ秦九韶算法：０.04μ ｓ【３,1,3】 试分析最大子列和算法1.3的空间复杂度。

答: 算法1.３的基本思路是将原问题拆分成若干小型问题,分别解决后再将结果合而治之，用递归方法实现。

算法1．3的负责度分析略有难度:若记整体时间复杂度为T(N),则函数D ｉvide Ａnd Ｃo ｎquer 中通过递归实现“分”的复杂度为2Ｔ(N ／2)，因为我们解决了2个长度减半的字问题。

求跨分界线的最大子列和时,有两个简单的for 循环，所用步骤一共不超过N ，所以可以在O （N ）时间完成。

其他步骤都只需常熟Ｏ(1)时间。

综上分析则有递推式:Ｔ(1)=O(１)；T(N ）=2T(N/2)+O(N)=2[2T （(N/２)/２+O （Ｎ／2)］+O(N ）=2２T(N ／２２)+2O(Ｎ)=…=2K T （N/2k )+kO(N)当不断对分直到N/2k ＝１,即2ｋ=Ｎ时,就得到T(N)＝NT(1)＋lo ｇN ＊O （Ｎ)=Ｏ(N log N)。