《作业参考答案》PPT课件.ppt

《《作业参考答案》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《作业参考答案》PPT课件.ppt（33页珍藏版）》请在装配图网上搜索。

1、作业参考答案,二、读下列程序后,说明该程序有些什么主要的功能 1. 若线性表L是无序的,问下列程序的功能是什么? Void sortlist ( struct List ,答案：把线性表L中的元素由小到大排序,第二章作业,2. 若x为给定的值,读下列程序后,说明该序的主要功 能是什么? calculate (stuct sNode *HL, elemtype ,答案：统计链表HL中值等于X的结点个数,3.下列程序的主要功能是什么? m( struct sNode *HL) if( HL= = null) return null; struct sNode *pmax = HL, p = HLl

2、ink; while (P!=null) if ( pdatapmaxdata) pmax = p; p =plink; return pmax; ,答案：查找链表HL中最大元素所在的位置,三、算法设计 1. 编写一个程序将单链表中值重复的结点删去,使所得的该表中各结点值均不相同的算法 算法：令p指针指向所建单链表的第一个结点，令q指向p的后继结点，q沿着链表向右（向后）扫描，若找到与p所指结点值相同的结点，则将其删除，继续处理，直到q为空；然后令p移到下一个结点（即直接后继结点），q依然指向p的后继结点，重复同样的处理 linklist *deletesamenode(linklist *h

3、) linklist *p,*q,*s; p=h-next; s=p; while(p!=NULL) q=p-next; while(q!=NULL) if(q-data!=p-data) s=q; / s为q的直接前趋指针，即s紧跟着q向右移动。 q=q-next; else s-next=q-next; /此时q所指向的结点为待删除结点 free(q); q=s-next; /q指向后继结点，继续寻找与p所指结点值相同的结点。 /内while循环结束 p=p-next; /外层while循环结束 return(h); ,2、求顺序表(或单链表)的逆序算法,void invert(SqLis

4、t 逆置（头插法插入） head-next=p； 头结点的指针域指向新插入的结点 p=r； 恢复待处理结点 return（head）； invert,作 业,1. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A. 栈 B. 队列 C. 树 D. 图,2. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是 A. 1 B. 2 C. 3 D. 4,

5、3.顺序队列的入队操作应为 ( ) A.sq.rear=sq.rear+1 sq.datasq.rear=x B. sq.datasq.rear=x sq.rear=sq.rear+1 C. sq.rear=(sq.rear+1)% maxsize; sq.datasq.rear=x D. sq.datasqrear=x sq.rear=(sq.rear+1)% maxsize,5.循环队列的人队操作应为 ( ) A.sq.rear=sq.rear+1 sq.datasq.rear=x B. sq.datasq.rear=x sq.rear=sq.rear+1 C. sq.rear=(sq.r

6、ear+1)% maxsize sq.datasq.rear=x D. sq.datasq.rear=x sq.rear=(sq.rear+1)% maxsize,6.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ） A. Top-next=s B. s-next=Top-next;Top-next=s C. s-next=Top;Top=s D. s-next=Top;Top=Top-next,7.循环队列的优点是什么？如何判断“队空”、“队满”？ 循环队列解决了常规用的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，仍用队头指针等于队尾指针表示队

7、空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（取模）等于队头指针时，表示队列满。也有使用全部单元，通过设标记来解决“空”和“满”的。第三种办法是一个队头（或队尾）指针加上队列中元素个数来区分队列的“空”和“满”的。,第四章作业,1.有关二叉树下列说法正确的是（ ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 2. 已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是( ) A. 39 B. 52 C. 111 D. 119 3. 已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。 A. 311 B. 3

8、12 C. 313 D. 314 E. 其它 4. 一棵树高为K的完全二叉树至少有（ ）个结点 A. 2k 1 B. 2k-1 1 C. 2k-1 D. 2k 5.设无向图的顶点个数为n，则该图最多有（ ）条边。 An-1 Bn(n-1)/2 Cn(n+1)/2 D0 EN2,6.要连通具有n个顶点的有向图，至少需要（）条边。 An-l Bn Cn+l D2n 7.一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A0 B1 Cn-1 Dn 8.用邻接表存储图所用的空间大小 。 与图的顶点数和边数都有关 只与图的边数有关 只与图的顶点数有关 与边数的平方有关,9.已

9、知二叉树的 后序序列 DMFBHELGCA 中序序列 DBMFAHECGL 请构造该二叉树。,第五章作业,一、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是 稳定 的，否则称为不稳定 的。 2.按照排序过程涉及的存储设备的不同，排序可分为内部 排序和_外部 排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：插入排序、交换排序、选择排序、归并排序等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以关键字比较和移动为标准操作。评价排序的另一个主要标准是执行算法所需要的辅助空间。 5.常用的插入排序方法有_

10、直接插入排序、折半插入排序、二路 插入排序和 希尔 插入排序。,6.以下为直接插入排序的算法。请分析算法，并在_上填充适当的语句。 void straightsort(list r); for(i= 1 ;i=n;i+) r0=ri;j=i-1; while(r0.keyrj.key)rj+1=_rj_ ;j-; rj+1= r0_; 7.对快速排序来讲，其最好情况下的时间复杂度是_O（nlog2n），其最坏情况下的时间复杂度是_O（n2）。 8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是_插入排序算法，最费时间的是快速排序算法。,二

11、、单项选择 1 以下说法错误的是 （ ） 直接插入排序的空间复杂度为O(1)。 快速排序附加存储开销为O(log2n)。 堆排序的空间复杂度为O(n)。 二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 2 以下不稳定的排序方法是 （ ） 直接插入排序 冒泡排序 直接选择排序 二路归并排序 3 以下稳定的排序方法是 （ ） 快速排序 冒泡排序 直接选择排序 堆排序 4 以下时间复杂性不是O(n2)的排序方法是 （ ） 直接插入排序 二路归并排序 冒泡排序 直接选择排序 5 以下时间复杂性不是O(nlog2n)的排序方法是 （ ） 堆排序 直接插入排序 二路归并排序 快速排序 6 在

12、文件局部有序或文件长度较小的情况下，最佳的排序方法是 （ ） 直接插入排序 冒泡排序 直接选择排序 归并排序,第六章作业,1 若对长度均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？ （1）查找不成功，即表中没有和关键字K相等的记录； （2）查找成功，且表中只有一个和关键字K相等的记录； （3）查找成功，且表中有多个和关键字K相等的记录，要求计算有多少个和关键字K相等的记录。,解答:（1）平均查找长度不相同。在有序的顺序表中查找时，在n+1(1n+1)个位置均可能失败；查找无序的顺序表时，查找失败都是在第n+1个位置，其平均

13、查找长度是n+1。 （2）平均查找长度相同。在n个位置上均可能成功。 （3）平均查找长度不相同。前者在某个位置上(1=i=n)查找成功时，和关键字K相等的记录是连续的，而后者要查找完顺序表的全部记录。,2.假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中要做多少次探测？ 解答:n个关键字都是同义词，因此，用线性探测法将第一个关键字存入时不会发生冲突，对其余关键字存入时都会发生冲突，所以探测的次数应为1+2+3+.+ n=n(n+1)/2次。 3.设有一组关键字9，01，23，14，55，20，84，27，采用哈希函数：H（key）=key % 7 ，表长为

14、10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) % 10(di=12，22，32，)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。,平均查找长度：ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8 以关键字27为例：H(27)=27%7=6(冲突) H1=(6+1)%10=7(冲突) H2=(6+22)%10=0(冲突) H3=(6+33)%10=5 所以比较了4次。,4.假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题：(1) 若查找元素54，需依次与哪些元素比较?(2)

15、若查找元素90，需依次与哪些元素比较?(3) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解:,第七章作业,1.给定一个有序数组A1.n ，以及一个元素x ，设计一个寻找 x的分治算法并分析其时间复杂度。要求返回 x在数组中的位置。,算法思想： 1、先将问题划分为大小近似相同的两个子问题 2、对子问题递归调用该算法进行处理，递归出口为子问题只含一个元素，这时将其与 x 直接比较，若等于 x 则返回该元素在数组中的位置 3、由于给定数组是有序的，因而可以根据 x 的大小判断 x 位于那个子问题内，而将另 一个不含 x 的子问题丢弃 Searchx(A, p, r, x) if pr

16、 then return 0 else q (p+r)/2 if x=Aq then return q else if x Aq then return Searchx(A, p, q-1, x) else Searchx(A, q+1, r, x),2.给定n 个整数的数组A1.n ，以及一个整数x ，设计一个分治算法，求出 x在数组A 中的出现的次数，并分析所设计算法的时间复杂度。 算法思想： 1、先将问题划分为大小近似相等的两个子问题 2、对子问题递归调用该算法进行处理，递归出口为子问题只含一个元素，若该元素等 于 x ，则返回 x 的出现次数 1，若该元素不等于 x ，则返回 0 3、

17、原问题结果为这两个子问题所得结果之和,Countx(A, p, r, x) if p=r then if Ap=x then return 1 else return 0 else q(p+r)/2 return (Countx(A, p, q, x)+Countx(A, q+1, r, x),第八章作 业,1.对维数序列为5，10，3，12，5，50，6的矩阵链，利用动态规划填表格的方式找出其矩阵链乘积的最优加括号方式。,解:,2.阐述分治法和动态规划算法的联系与区别。 联系: 问题都是被划分成一个或是多个子问题, 然后把子问题的解组合起来. 区别: 分治方法： 1. 子问题是相互独立的.

18、2. 子问题被重复计算. 动态规划 (DP) 1. 子问题是不独立的. 2. 子问题仅被执行一次. 动态规划通过以下方法提高效率: 以自底向上的方法解决子问题. 把第一次已得到解答的子问题的解保存起来. 当再次遇到该子问题时，检索这个解.,3.数字三角形问题,问题描述 给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请应用动态规划分析求从三角形的顶至底的最小路径得分的算法，并证明具备最优子结构性质。,2 6 2 1 8 4 1 5 6 8 图1 数字三角形,提示：可用二元组D(X,y)描述问题，D(X,y)表示从顶层到达第X

19、层第y个位置的最小路径得分。,用二元组D(X,y)描述问题，D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。 最优子结构性质：容易看出，D(X,y)的最优路径Path(X,y)一定包含子问题D(X-1,y)或D(X-1,y-1)的最优路径。 否则，取D(X-1,y)和D(X-l,y-1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分，这与Path(X,y)的最优性是矛盾的。 递归关系： D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y) D(1,1)a(1,1) 其中，a(X,y)为第X层第y个位置的数值。,原问题的最小路径得分可以通过比较D(N,i)获得，其中i1，2，N。 在上述递归关系中，求D(X,y)的时候，先计算D(X-1,y)和D(X-1,y-1)，下一步求D(X，y+1)时需要D(X-1，y+1)和D(X-1，y)，但其中D(X-1，y)在前面已经计算过了。于是，子问题重叠性质成立。 因此，采用该问题具备了用动态规划求解的基本要素，可以用动态规划进行求解。,