第1章习题参考答案.docx

《第1章习题参考答案.docx》由会员分享，可在线阅读，更多相关《第1章习题参考答案.docx（37页珍藏版）》请在课桌文档上搜索。

1、第1章习题参考答案1. (1)加法操作，(2)乘法操作，(3)比较操作，(4)乘法操作。2. 共执行了16次元素比较操作。初始序列为(4,3,12,5,6,7,2,9,采用插入排序将序列排序为升序序列，按照算法思想：(1)初始时默认4有序，3和4比较1次，3比4小插入到4前面，则有序序列变为(3,4),进行1次比较；(2)插入12,12和4比较1次，12比4小，12插入到4后面，则有序序列变为3,4,12,进行1次比较：(3)插入5,5和12比较1次，5比12小；5和4比较1次，5比4大，5插入到4后面，则有序序列变为3,4,5,12,进行2次比较；(4)插入6,6和12比较1次，6比12小；

2、6和5比较1次，6比5大，6插入到5后面，则有序序列变为3,4,5,6,12,进行2次比较;(5)插入7,7和12比较1次，7比12小；7和6比较1次，7比6大，7插入到6后面,则有序序列变为3,4,5,6,7,12,进行2次比较;(6)插入2,2比序列前面的所有元素都小，分别和每个元素比较1次，最后插入到3前面，则有序序列变为2,3,4,5,6,7,12,进行6次比较；(7)插入9,9和12比较1次，9比12小；9和7比较1次，9比7大，9插入到7后面，则有序序列变为2,3,4,5,6,7,9,12),进行2次比较。综上，共比较16次。3. 5log(n+100)log2nVn0.001n4

3、+2n3+13n(n-2)!2n24. (1)/(n)=O(n),由于Hm鬻=Iim二0。ng(n)n2. )=O(g(),由于Iim=Iim+%”=0。ng(n)nn3. )g(n)=O(n),由于Iim华=Iim匕等=8。D7n80(n)nn4. )g(i)=O(n),由于Iim=Iim=8。Un8(n)nlogn+15. 证明：令F(ZI)=O(/(几)，G(Zl)=O(以九)。根据。的定义，存在正常数Cl和非负整数%,使得对所有的n叫,有尸(7i)cJ(n);同理，存在正常数Q和非负整数九2,使得对所有的nn2,有G(n)vgOO。令C3=qc2,H3=maxn1,n2,h(ri)=f

4、(n)g(i),则对所有的几n3,有F(n)G(n)=()(n)c1f(n)c2g(n)=c3h(n)因此。(/(几)。(。(几)=O(M九)=。(/(咖)证毕。6. (1)元素比较操作最少执行n-l次，当原列表为升序排列时达到该最小值。(2)元素比较操作最多执行电3次，当原列表为降序排列时达到该最大值。(3)元素赋值操作最少执行。次，当原列表为升序排列时达到该最小值。(4)元素赋值操作最多执行若2次，当原列表为降序排列时达到该最大值。(5)OoI2),(n)o7. (1)使用蛮力法，遍历所有元素找出最大值，时间复杂度为05)。算法：BrUteSearCh蛮力法输入：查找列表41：T输出：力中

5、的最大值步骤：1. maxmThen4. max1时当n=1时采用迭代法可得到M(n)=M(n-1)+1=M(n-2)+1+1=M(n-2)+2=M(n-3)+l+l=M(n-3)+3不难看出M(n)=M(ni)+i=M(n(n1)+n1=M(I)+n-l=n1(2)为了方便的表示，用Sm)表示加减运算次数，不包括减少时所需的减法运算，那么S5)需满足、(S(n-1)+2,当nl时SQI)=(0,当n=1时采用迭代法可得到S(n)=S(n-1)+2=S(n-2)+2+2=S(n-2)+4=S(n-3)+2+4=S(n-3)+6因此S(ri)=S(ni)+2i=S(n(n-1)+2(n1)=S(

6、I)2(n-1)=2n-29. (1)由原式可得T(n)-y=3(r(n-1)-y)T(n)-竽=3则T(n)-号是以3为公比的等比数列，首项为丁一蔡=也即()一孩=汐-1,则Ts)=T3时】+协(2)由原式可得T(TI)-T(Tl-I)=n1T(n-1)-T(n-2)=(n-1)-1=n-2T(n-2)-T(n-3)=(n-2)-1=n-3T(2)-T(I)=2-1=1上述式子累加可得T(n)-T(I)=与2即Tm)=3尸2+3。第2章习题参考答案1 .每趟执行后列表中的元素如下表：ANEXAMPLEAENXAMPLEAENAXMPLEAAENXMPLEAAENXMPELAAENXELMPA

7、AEEI.MNPX2 .(1)例如(5,19,17,21,11,8,1),算法2.1和算法2.3都需比较11次。(2)例如(2,5,4,9,3,6,8,7,1,0),算法2.1需比较23次，算法2.3需比较19次。(3)例如(8,5,3,9,11,6,4,1,10,7,2),算法2.1需比较26次,算法2.3需比较28次。3 .用递归的分治法同时返回列表A:r的最大值和最小值。算法：MaxMin/分治法求最大最小值输入：A:r输出：心X,min/A中的最大值和最小值1. Ifr=Then2. wav-Al;min-A3. returnmax,min4. EndIf5. If=2Then6. w

8、r-maAl,Ar;minr-mini4Z,i4r7. returnmax,min8. EndIf9. mid-9+r)210. (max,加1)-MaXMin(A/:mid)/处理前半部分11. (nax2,加2)-MaXMin(Amid+1,r)处理后半部分12. Ifnin2tnaxThen16. nax-nax217. EndIf28. Returnmax,min(1)以元素比较为基本，算法的计算时间记为CS),递推式如下:C(n)=2CQ)2(n2),C(2)=1,C(I)=O下面求解C()的递推式：Col)=C(2k)=2C(y)+2=2C(2fc1)+2=22C(2fc2)+2+

9、2=2TC(2)+2fc1+2k-2+2=2k-1C(2)+2k-2=y-2(2)蛮力法中元素比较次数为2(-1),分治法中元素比较次数为冷-2,分治法效率更高。4.利用快速排序原理，将一个数组分为三个部分：负元素、未知元素、正元素。A-ijA+1n负元素未知元素正元素算法如下：算法：NegBeforePos列表重排列输入：A1:用待重排列的列表输出：A口：川重排列后的列表步骤：1. Z-ljJ-22. WhileijDo3. IfA0Then4. z-+l5. Else6. SWaP(Ai,AUD7j-jT8. EndIf9. EndWhile10. ReturnA算法需一个长度为的数组用来

10、存放所有元素，而每次迭代都会从左向右，缩减一位未知元素空间。因此，算法的时间复杂度为0(”)，空间复杂度为0()。5.(1)蛮力法：蛮力法求解最近对问题，分别计算每一对点之间的距离，然后找出距离最小的点对，为了避免对同点对计算两次距离，只考虑i的那些点对(Pi出)。复杂度分析：算法的基本操作是计算计算两个点间的欧几里得距离。注意到，在求欧几里得距离时，避免了求平方根操作，因此，算法的基本操作为求平方，其执行次数为：n-lnn-1TT(Tl)=WW2=2W(九-，)=九(九-1)=O(M)i=j=i+i=(2)分治法：用分治法求解最近对问题，就是将集合S分成两个子集Sl和S2,每个子集中分别有方

11、个点。然后在每个子集中递归的求其最近点对，在求出每个子集的最近点对后，关键在于如何实现分治法中的合并步骤。如果S中的最近点对都在Sl中或都在52中，则问题很容易解决。如果这2个点分别在Sl和S2中，则对于SI中任一点P，”中最多只有5个点与它构成最接近点对的候选者，仍需进一步计算才能得到最终结果。时间复杂性可由如下递推式表示：T(n)=2g)+)合并子问题的解的时间f5)=0(l),因此，算法的时间笈杂度为：T(i)=O(nlogn)第3章习题参考答案1.基本思路：直接使用深度优先(DFS)算法以及广度优先算法即可得到给定图的一个连通分量。(1)使用DFS求连通分量算法*DFS/深度优先算法输

12、入：G=输出：g图G的一个连通分量步骤：1. g-02. visit遍历初始顶点3. Initialize(S)将栈S初始化为空4. PUSh(S/)/初始顶点入栈5. WhileS非空Do6. X-Pop(5,)7. g-gu%8. For每一个与X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. PUSh(S,卬)将顶点入栈12. EndIf13. EndFor14. EndWhile15. RetUrng(2)使用BFS求连通分量算法:BFS/广度优先算法输入：G=输出：g图G的一个连通分量步骤:1. g-02. ViSitW)遍历初始顶点3. InitiaIi

13、Ze(Q)初始化队列4. EnqUeUe(Q,u)初始顶点入队5. WhileQ非空Do6. xDequeUe(Q)7. g-g=%8. For每一个与己X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. Enqueue(,W)12. EndIf13. EndFor14. EndWhile15. RetUrng2 .参考如下极端情况，其中一个顶点出度为-1,其余顶点出度均为0,最多有(-1)!种拓扑排序结果。3 .第一步：遍历所有顶点，找出入度为0的顶点F并将该顶点入队，将与F连接的顶点E、B、C、G入度减1,同时让F出队，F即为拓扑排序的第1个元素。此时拓扑序列为F

14、0第二步：遍历所有顶点，找出入度为0的顶点E并将该顶点入队，将与E连接的顶点A入度减1,同时让E出队，E即为拓扑排序的第2个元素。此时拓扑序列为F,E。第三步：遍历所有顶点，找出入度为0的顶点A并将该顶点入队，将与A连接的顶点B入度减1,同时让A出队，A即为拓扑排序的第3个元素。此时拓扑序列为F,E,A。第四步：遍历所有顶点，找出入度为0的顶点B并将该顶点入队，将与B连接的顶点C入度减1,同时让B出队，B即为拓扑排序的第4个元素。此时拓扑序列为F,E,A,B0第五步：遍历所有顶点，找出入度为O的顶点C并将其入队，将与C连接的顶点D入度减1,同时让C出队，C即为拓扑排序的第5个元素。此时拓扑序列

15、为F,E,A,B,C。第六步：遍历所有顶点，找出入度为O的顶点D并将该顶点入队，将与D连接的顶点G入度减1,同时让D出队，D即为拓扑排序的第6个元素。此时拓扑序列为F,E,A,B,C,Do第七步：遍历顶点发现只剩下顶点G,则G为拓扑排序的最后一个元素。因此，该有向图的最终拓扑排序序列为F,E,A,B,C,D,Go第4章习题参考答案(1) (1)基于贪心法的哈夫曼树构造过程如下:合并出现频率最小的字符B和D,并计算合并后的频率;合并出现频率最小的字符E和C并计算合并后的频率;合并出现频率值最小的两个节点，并计算合并后的频率;(2) ABACABAD的编码为OlO1。(3) 010解码为BADEA

16、DA。注意：上述答案不唯一，根据构造的哈夫曼树结构不同而不同。2.每次先取剩余硬币中面值最大的硬币，如果不满足条件，再选择次面值最大的硬币。假设有4种硬币，面值分别为50元、10元、5元和1元。如需找零99元，首先选择一个面值不超过99元的最大硬币，即50元，由于慨M=1,因而选择一个面值为50元的硬币，然后从99元中减去50元，剩下49元。再选择一个面值不超过49元的最大硬币，即10元,由于葛=4,因而选择4个面值为10元的硬币，然后从49元中减去40元，剩下9元。如此一直做下去，最终的硬币选择方案为1个50元的硬币、4个10元的硬币、1个5元的硬币和4个1元的硬币。算法：C算nge/求解找

17、零问题的贪心算法输入：找零金额n,非升序的硬币面值山，d2,.,dm）输出：每种面额硬币数量。1:力步骤：1. Fori=1TomDo2. Ci-0初始化每种面额硬币找钱数3. EndFor4. Fori=1TomDo5. CE-用6. nnmoddi取余7. EndFor8. Ifn=0Then9. ReturnC10. Else11. RetUmNOSoliltion/无解3.每次选择元素个数最少的两个列表进行合并排序，从而合并元素时元素比较总次数最少。该算法的步骤如下：（1）找到包含元素最少的两个列表,可采用堆排序算法根据列表中元素个数进行排序，时间复杂度为0（nIogn）。（2）找到元

18、素最少的两个列表后采用算法2.2进行合并，时间复杂度为OSlogTi）。由于每次需通过堆排序查找包含元素最少的两个列表，共执行（n-l）次堆排序，因此该算法的时间复杂度为。（九2Iogn）。第5章习题参考答案1 .动态规划的基本思想：问题的最优解如果可由子问题的最优解推导得到，则可先求解子问题的最优解，再构造原问题的最优解。动态规划要把之前步骤已计算出的结果记录下来，当需要求解原问题的时候，就可使用各子问题（规模更小）的解来构造当前解。动态规划是一个多阶段决策，不是一次性解出多个，而是将多个决策变成多次决策；各个子问题之间并不独立，大规模问题的解可由小规模问题的解进行递推得到（前后有联系）。使

19、用动态规划算法求解问题的基本步骤：（1）分析最优解的性质，刻画其最优子结构特征。（2）递归地定义最优值。（3）根据状态转移顺序，以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，以填表的方式构造最优解。动态规划算法适用的条件或场景：1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。（2）无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用。2 .共同点：二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小（

20、小到很容易解决的程序）的子问题，找出子问题与原问题之间的关系（递推式）然后将子问题的解合并，形成原问题的解。不同点：分治法中，分解后得到的子问题相互独立，通常使用递归算法求解。动态规划法中，分解后的子问题相互间有联系（并不独立）、有重叠部分，需要记忆，通常使用迭代方式来求解。3 .（1）各子问题的最优值如下表：物品容量0123456000000001000252525252002025254545301520354045604015203540556050152035405565第一行的值为0,因为物品标号为0（考虑前。个物品的最优值）的情况下（即没有物品）最大价值都是0。第一列的值为0,因为

21、在当前背包容量为。的情况下最大价值都是0。当i=2、户3时，由于广优，物品2可装入背包、也可不装入背包，此时考虑物品2是否装入背包,比较装入或不装物品2时的最大价值:物品2不装入背包时的价值为仇2,3）=25；物品2装入背包时的价值为仇2,3）二仇2-1,4-2）=20;取两者中的最大值max25,20）=25,即此时背包最大价值为25。以此类推，继续迭代直至填满表格。（2）有1个最优子集。最优值为最大价值65,最优解为0,0,1,0,1。（3） 一般来说，可以通过判断表中最后一列的最大值个数来判断（背包问题的最优值只会在最后一列中产生）。4.分析：无论怎样的组合，最后有i枚硬币的面额加起来等

22、于总金额八设最后一枚硬币为的面额为山，这枚硬币之外的前面硬币的面额加起来为/-山。我们不关心前面i-l枚硬币的组合，也不知道山和心可以确定的是，前面的硬币组合成了九-4,且硬币的数量一定减少。因此，可用数组fi来表示用i种不同的硬币去找钱j时所需的最少硬币数。可将问题进行分解：针对第一1项，最后一枚硬币的面额为由处,dm时，所需最少硬币数分别为川田-必+1,fi）-+1/i/-dm+Io因此，/i=mini-l/,fij-di+l）Climtljn）,其中-1/表示不使用第i枚硬币找零时，对金额）进行找钱所需的最少硬币数。算法如下：算法：MinimIInlehange最少硬币找钱输入：Coin

23、s1:汨,nHCoins代表硬币面额数组，n为需找钱金额输出：力加1川步骤：LForZ=ITowDo2. W0-03. EndFor4. For/=1TomDo5. For7-1TonDo6. IfjCoins1Then7. 川皿一+88. Else9. 川T+川-C。加10. EndIf11. Ifj)加入到训练集D中，此时，根据Dirichlet先验分布特性，重新估计参数,1P(Cr8)=最片若CrCp/)=提分+&，若Cr=G其中，=C+D,分为分类器的原有参数，%=P(Cr8)=笔*。C12(2)增量更新已有类别概率通过分析学习参数的变化可知，(x弓)加入到训练集后，只有与之相关的项的估计变化较大，而与之无关的项变化较小。为此，使用Du(xcj)估计xZT-xj的类条件概率时，忽略与无关的项的影响，求解方法如下:p(4Me)P网Ebxir Pq0)tej,其中，Tid