第1章习题参考答案.docx

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

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. 51og(n+100)1og2nVn1时当n=1时

3、采用迭代法可得到M(n)=M(n-1)+1=M(n-2)+1+1=M(n-2)+2=M(n-3)+1+1=M(n-3)+3不难看出M(n)=M(ni)+i=M(n(n1)+n1=M(I)+n-1=n1(2)为了方便的表示，用Sm)表示加减运算次数，不包括减少时所需的减法运算，那么S5)需满足、(S(n-1)+2,当n1时SQI)=(0,当n=1时采用迭代法可得到S(n)=S(n-1)+2+2n3+13n(n-2)!2n24. (1)/(n)=O(n),由于Hm鬻=Iim二0。ng(n)n(2) =O(g(),由于Iim=Iim+%”=0。ng(n)nn(3) g(n)=O(n),由于Iim华=

4、Iim匕等=8。D7n80(n)nn证毕。6. (1)元素比较操作最少执行n-1次，当原列表为升序排列时达到该最小值。(2)元素比较操作最多执行电3次，当原列表为降序排列时达到该最大值。(3)元素赋值操作最少执行。次，当原列表为升序排列时达到该最小值。(4)元素赋值操作最多执行若2次，当原列表为降序排列时达到该最大值。(5)OoI2),(n)o7. (1)使用蛮力法，遍历所有元素找出最大值，时间复杂度为05)。算法：BrUteSearCh蛮力法输入：查找列表41：T输出：力中的最大值步骤：1. maxmThen4. max-Ai5. EndIf6. EndForM(n)=10,7. ReIUm

5、max=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(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(T1-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章习题参

6、考答案1 .每趟执行后列表中的元素如下表：ANEXAMP1EAENXAMP1EAENAXMP1EAAENXMP1EAAENXMPE1AAENXE1MPAAEEI.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

7、/A中的最大值和最小值1. Ifr=Then2. wav-A1;min-A3. returnmax,min4. EndIf5. If=2Then6. wr-maA1,Ar;minr-mini4Z,i4r7. returnmax,min8. EndIf9. mid-9+r)210. (max,加1)-MaXMin(A/:mid)/处理前半部分11. (nax2,加2)-MaXMin(Amid+1,r)处理后半部分12. Ifnin2tnaxThen15. nax-nax216. EndIf28. Returnmax,min(1)以元素比较为基本，算法的计算时间记为CS),递推式如下:C(n)=2

8、CQ)2(n2),C(2)=1,C(I)=O下面求解C()的递推式：Co1)=C(2k)=2C(y)+2=2C(2fc1)+2=22C(2fc2)+2+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-1jJ-22. Whi1eijDo3. IfA0Then

9、4. z-+15. E1se6. SWaP(Ai,AUD7j-jT8. EndIf9. EndWhi1e10. ReturnA算法需一个长度为的数组用来存放所有元素，而每次迭代都会从左向右，缩减一位未知元素空间。因此，算法的时间复杂度为0(”)，空间复杂度为0()。5.(1)蛮力法：蛮力法求解最近对问题，分别计算每一对点之间的距离，然后找出距离最小的点对，为了避免对同点对计算两次距离，只考虑i的那些点对(Pi出)。复杂度分析：算法的基本操作是计算计算两个点间的欧几里得距离。注意到，在求欧几里得距离时，避免了求平方根操作，因此，算法的基本操作为求平方，其执行次数为：n-1nn-1TT(T1)=W

10、W2=2W(九-，)=九(九-1)=O(M)i=j=i+i=(2)分治法：用分治法求解最近对问题，就是将集合S分成两个子集S1和S2,每个子集中分别有方个点。然后在每个子集中递归的求其最近点对，在求出每个子集的最近点对后，关键在于如何实现分治法中的合并步骤。如果S中的最近点对都在S1中或都在52中，则问题很容易解决。如果这2个点分别在S1和S2中，则对于SI中任一点P，”中最多只有5个点与它构成最接近点对的候选者，仍需进一步计算才能得到最终结果。时间复杂性可由如下递推式表示：T(n)=2g)+)合并子问题的解的时间f5)=0(1),因此，算法的时间笈杂度为：T(i)=O(n1ogn)第3章习题

11、参考答案1.基本思路：直接使用深度优先(DFS)算法以及广度优先算法即可得到给定图的一个连通分量。(1)使用DFS求连通分量算法*DFS/深度优先算法输入：G=输出：g图G的一个连通分量步骤：1. g-02. visit遍历初始顶点3. Initia1ize(S)将栈S初始化为空4. PUSh(S/)/初始顶点入栈5. Whi1eS非空Do6. X-Pop(5,)7. g-gu%8. For每一个与X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. PUSh(S,卬)将顶点入栈12. EndIf13. EndFor14. EndWhi1e15. RetUrng(2)使

12、用BFS求连通分量算法:BFS/广度优先算法输入：G=输出：g图G的一个连通分量步骤:1. g-02. ViSitW)遍历初始顶点3. InitiaIiZe(Q)初始化队列4. EnqUeUe(Q,u)初始顶点入队5. Whi1eQ非空Do6. xDequeUe(Q)7. g-g=%8. For每一个与己X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. Enqueue(,W)12. EndIf13. EndFor14. EndWhi1e15. RetUrng2 .参考如下极端情况，其中一个顶点出度为-1,其余顶点出度均为0,最多有(-1)!种拓扑排序结果。3 .第一步：遍历所有顶点，找出入度为0的顶点F并将该顶点入队，将与F连接的顶点E、B、C、G入度减1,同时让F出队，F即为拓扑排序的第1个元素。此时拓扑序列为F0第二步：遍历所有顶点，找出入度为0的顶点E并将该顶点入队，将与E连接的顶点A入度减1,同时让E出队，E即为拓扑排序的第2个元素。此时拓扑序列为F,E。第三步：遍历所有顶点，找