算法导论第五章答案

6 Problem 5-2. Join operation on red-black trees Handout 22: Problem Set 5 The join operation takes two dynamic� sets �� and �� and an element � such that for any ��������� and ������� , we have key ������� key ����� key ����� . It returns a set ���������������� . In this problem, we investigate how to implement the join operation on red-black trees. (a Given a red-black tree � , we store its black-height as the field bh ��. Argue that this field can be maintained by RB-I NSERT and RB-D ELETE (as given in the textbook, on pages 280 and 288 respectively without requiring extra storage in the nodes of the tree and without increasing the asymptotic running times. Show that while descending through � , we can determine the black-height of each node we visit in ������� time per node visited. Solution: Starting at the root, we can proceed to a leaf, couting the number of black nodes on the path. This does not require any extra storage in the nodes of the tree and will take ����������� time. Since RB-I NSERT and RB-D ELETE also run in����������� time, the asymptotic running time is not increased. While descending through � , we decrement bh �� by � 1 everytime we encounter a blacknode. The black-height of a node, � , is then bh �� minus the number of black nodes encountered (excluding node � itself. This decrement can be done in ������� time per node visited. We wish to implement the operation RB-J OIN ������������� , which may destroy �� and �� and returns a red-black tree ���������������� . Let � be the total number of nodes in �� and �� . (b Assume that bh ������ bh ���� . Describe an ����������� -time algorithm that finds a black � node ����� in � with the largest key from among those nodes whose black-height is bh � . Solution: Since �� is a binary search tree, the largest element at any level is on the rightmost path. So, we decend down the rightmost path, calculating bh at each node (as described ���� in the previous part, until we reach the black node whose black-height is bh � , which is what we want. Thus the running time is at most the height of the tree, i.e. ����������� . (Calculating the black-height takes ������� per node, as shown in the previous part. ���� (c Let ��� be the subtree rooted at � . Describe how �������������� can replace ��� in ������� time without destroying the binary-search-tree property. Solution:Handout 22: Problem Set 5 Insert � into where � was in �� . Form �������������� by letting ��� be the left subtree� of � , and ��� be the right subtree of � . Given that this join operation is such that � key ������� key����� key ����� where ������� and ������� , the binary search tree property is maintained and this operation takes ������� time. Consider the following red-black properties: 7 � every node is either red or black � every leaf is black nodes (d What color should we make � so that the above red-black properties are maintained? Solution: We should make � red. Since ��� already has black-height = bh ������� , � must be red to �������������� = bh �������maintain the same black-height, bh ��� Consider the following red-black properties: �for each node, all paths from the node to descendant leaves contain the same number of black � the root is black � if a node is red, then both its children are black (e Describe how the above two properties can be enforced in ����������� time. Solution:Use RB-I NSERT-F IXUP on the new tree, to perform the recoloring and rotations nec-essary to enforce these two properties. We know that RB-I NSERT-F IXUP runs in����������� time, thus we conclude that the enforcement can be done in����������� time. (f Argue that the running time of RB-J OIN is����������� . Solution: RB-J OIN is implemented by using all the previous parts: The black-height can be calculated and maintained in ������� time. The required black node, � , can be found in ����������� time. Then, the join is done in�����������time, and finally, after assigning � the right color, the red-black tree properties can be enforced in ����������� time. So the total runing time is �����������。

算法导论课程作业答案Introduction to AlgorithmsMassachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout10Diagnostic Test SolutionsProblem1Consider the following pseudocode:R OUTINE(n)1if n=12then return13else return n+R OUTINE(n?1)(a)Give a one-sentence description of what R OUTINE(n)does.(Remember,don’t guess.) Solution:The routine gives the sum from1to n.(b)Give a precondition for the routine to work correctly.Solution:The value n must be greater than0;otherwise,the routine loops forever.(c)Give a one-sentence description of a faster implementation of the same routine. Solution:Return the value n(n+1)/2.Problem2Give a short(1–2-sentence)description of each of the following data structures:(a)FIFO queueSolution:A dynamic set where the element removed is always the one that has been in the set for the longest time.(b)Priority queueSolution:A dynamic set where each element has anassociated priority value.The element removed is the element with the highest(or lowest)priority.(c)Hash tableSolution:A dynamic set where the location of an element is computed using a function of the ele ment’s key.Problem3UsingΘ-notation,describe the worst-case running time of the best algorithm that you know for each of the following:(a)Finding an element in a sorted array.Solution:Θ(log n)(b)Finding an element in a sorted linked-list.Solution:Θ(n)(c)Inserting an element in a sorted array,once the position is found.Solution:Θ(n)(d)Inserting an element in a sorted linked-list,once the position is found.Solution:Θ(1)Problem4Describe an algorithm that locates the?rst occurrence of the largest element in a?nite list of integers,where the integers are not necessarily distinct.What is the worst-case running time of your algorithm?Solution:Idea is as follows:go through list,keeping track of the largest element found so far and its index.Update whenever necessary.Running time isΘ(n).Problem5How does the height h of a balanced binary search tree relate to the number of nodes n in the tree? Solution:h=O(lg n) Problem 6Does an undirected graph with 5vertices,each of degree 3,exist?If so,draw such a graph.If not,explain why no such graph exists.Solution:No such graph exists by the Handshaking Lemma.Every edge adds 2to the sum of the degrees.Consequently,the sum of the degrees must be even.Problem 7It is known that if a solution to Problem A exists,then a solution to Problem B exists also.(a)Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable.If his proof turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no (or don’t know).Solution:No(b)Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable.If the proof turns out to be valid,can we conclude that problem A is unsolvable as well?Answer yes or no (or don’t know).Solution:YesProblem 8Consider the following statement:If 5points are placed anywhere on or inside a unit square,then there must exist two that are no more than √2/2units apart.Here are two attempts to prove this statement.Proof (a):Place 4of the points on the vertices of the square;that way they are maximally sepa-rated from one another.The 5th point must then lie within √2/2units of one of the other points,since the furthest from the corners it can be is the center,which is exactly √2/2units fromeach of the four corners.Proof (b):Partition the square into 4squares,each with a side of 1/2unit.If any two points areon or inside one of these smaller squares,the distance between these two points will be at most √2/2units.Since there are 5points and only 4squares,at least two points must fall on or inside one of the smaller squares,giving a set of points that are no more than √2/2apart.Which of the proofs are correct:(a),(b),both,or neither (or don’t know)?Solution:(b)onlyProblem9Give an inductive proof of the following statement:For every natural number n>3,we have n!>2n.Solution:Base case:True for n=4.Inductive step:Assume n!>2n.Then,multiplying both sides by(n+1),we get(n+1)n!> (n+1)2n>2?2n=2n+1.Problem10We want to line up6out of10children.Which of the following expresses the number of possible line-ups?(Circle the right answer.)(a)10!/6!(b)10!/4!(c) 106(d) 104 ·6!(e)None of the above(f)Don’t knowSolution:(b),(d)are both correctProblem11A deck of52cards is shuf?ed thoroughly.What is the probability that the4aces are all next to each other?(Circle theright answer.)(a)4!49!/52!(b)1/52!(c)4!/52!(d)4!48!/52!(e)None of the above(f)Don’t knowSolution:(a)Problem12The weather forecaster says that the probability of rain on Saturday is25%and that the probability of rain on Sunday is25%.Consider the following statement:The probability of rain during the weekend is50%.Which of the following best describes the validity of this statement?(a)If the two events(rain on Sat/rain on Sun)are independent,then we can add up the twoprobabilities,and the statement is true.Without independence,we can’t tell.(b)True,whether the two events are independent or not.(c)If the events are independent,the statement is false,because the the probability of no rainduring the weekend is9/16.If they are not independent,we can’t tell.(d)False,no matter what.(e)None of the above.(f)Don’t know.Solution:(c)Problem13A player throws darts at a target.On each trial,independentlyof the other trials,he hits the bull’s-eye with probability1/4.How many times should he throw so that his probability is75%of hitting the bull’s-eye at least once?(a)3(b)4(c)5(d)75%can’t be achieved.(e)Don’t know.Solution:(c),assuming that we want the probability to be≥0.75,not necessarily exactly0.75.Problem14Let X be an indicator random variable.Which of the following statements are true?(Circle all that apply.)(a)Pr{X=0}=Pr{X=1}=1/2(b)Pr{X=1}=E[X](c)E[X]=E[X2](d)E[X]=(E[X])2Solution:(b)and(c)only。

page: 1The Home of jetmambo - 第 5 章树和二叉树第 5 章树和二叉树(1970-01-01) -第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m （m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

算法导论答案算法导论是计算机科学领域中一门重要的课程，其目的是介绍和探讨算法的基本原理和设计方法。

本文将从几个不同角度来讨论算法导论的主题，包括算法的定义、算法分析、算法设计等，并提供一些常见的算法应用示例。

一、算法的定义与特点算法是一个用于完成特定任务的有限一系列指令或规则的集合。

算法的设计应具备以下几个特点：确定性、有穷性、可行性和输入/输出。

1. 确定性：对于给定的输入，算法的每个步骤都必须是明确且唯一的。

不同的输入应得到不同的输出。

2. 有穷性：算法必须经过有限的步骤后能终止。

这是因为计算机程序需要在有限时间内完成，而无限循环的算法则无法给出结果。

3. 可行性：算法的每个步骤都应该是可行执行的，即能够在可接受的时间内完成。

4. 输入/输出：算法应该具有输入和输出，即根据给定的输入，通过算法能够得到相应的输出。

二、算法的分析与效率评估算法的分析与效率评估是算法导论的重要内容。

在设计和选择算法时，需要考虑到其执行时间和内存需求等方面。

1. 时间复杂度：用于衡量算法所需执行的时间。

常见的时间复杂度表示方法有大O记法，例如O(n)、O(nlogn)等。

时间复杂度越低，算法执行效率越高。

2. 空间复杂度：用于衡量算法所需的内存空间。

空间复杂度的衡量单位通常是字节或比特。

与时间复杂度一样，空间复杂度越低，算法的内存需求越小。

三、算法的设计方法算法设计是算法导论的核心内容之一，主要包括贪心算法、分治算法、动态规划算法等。

1. 贪心算法：贪心算法是一种基于每一步局部最优解的策略来解决问题的算法。

它常应用于问题的最优解为局部最优解的情况，但不一定能得到全局最优解。

2. 分治算法：分治算法是一种将问题划分为多个相互独立的子问题，再合并子问题的解来得到整体解的算法。

适合解决规模较大且问题可被划分的情况。

3. 动态规划算法：动态规划算法是一种将复杂问题拆分为更小、更简单的子问题来解决的算法。

它利用了子问题的重叠性质，将子问题的解保存起来，避免了重复计算。

Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort 重写为按非递减顺序排序2.1.3 计算两个n 位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数32/10001001003n n n --+用符号Θ表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n 个元素已经是最大的元素了.最好时间和最坏时间均为2()n Θ2.3 Designing algorithms2.3.3 计算递归方程的解22()2(/2)2,1k if n T n T n n if n for k =⎧=⎨+ = >⎩ （1） 当1k =时，2n =，显然有()lg T n n n =（2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===⋅，则当1k i =+，即12i n +=时，111111()(2)2(2)222(1)22lg(2)lg i i i i i i i i T n T T i i n n ++++++==+=⋅+=+== ()lg T n n n ∴ =2.3.4 给出insertion sort 的递归版本的递归式(1)1()(1)()1if n T n T n n if n Θ =⎧=⎨-+Θ >⎩2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找：Search(A,n,x)QuickSort(A,n);i←1; j←n ;while A[i]+A[j]≠x and i<jif A[i]+A[j]<xi←i+1elsej←j -1if A[i]+A[j]=xreturn trueelsereturn false时间复杂度为)(n Θ。

算法导论Exercises22.5（转载）Exercises 22.5 - 导论.英⽂第3版最近看书的同时, 感觉⼀些练习缺少参考, 所以按部分总结了⾃⼰的解答, 也能够强化学习过程.如有不⾜或疑问, 欢迎指正.Exercises 22.5-1How can the number of strongly connected components of a graph change if a newedge is added?可以将每个强连通组件当作⼀个顶点, 组成强连通图, 图内顶点数量即强连通组件数量.如果新增加的边在顶点内部(即指向⾃⼰), 或者重复已有顶点间的边, 则数量没变化.如果新增加的边使图形成环, 这样环内顶点组成⼀个新的强连通组件, 所以数量减少N, N = (环内顶点数量 - 1). Exercises 22.5-2Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on thegraph of Figure 22.6. Specifically, show the finishing times computed in line 1 andthe forest produced in line 3. Assume that the loop of lines 5–7 of DFS considersvertices in alphabetical order and that the adjacency lists are in alphabetical order.按照字母排序的循环和邻接表, 可得出第⼀次DFS访问顶点顺序, 如下(q (s (v (w, w) v) s) (t (x (z, z) x) (y, y) t) q) (r (u, u) r)finishing time: f(r) 20, f(u) 19, r(q) 16, f(t) 15, f(y) 14,f(x) 12, f(z) 11, f(s) 7, f(v) 6, f(w) 5.根据 finishing time 降序排列, 并倒转上图中的边, 第⼆次DFS访问顶点顺序, 如下(r, r) * (u, u) * (q (y (t, t) y) q) * (x (z, z) x) * (s (w (v, v) w) s)每个不相关括号(⽤*间隔)内的顶点, 代表 line 3 ⽣成的树(即强连通组件)ANSWER：DFS（G）森林：（其中红⾊为树边）强连通分量结果：Exercises 22.5-3Professor Bacon claims that the algorithm for strongly connected componentswould be simpler if it used the original (instead of the transpose) graph in thesecond depth-first search and scanned the vertices in order of increasing finishingtimes. Does this simpler algorithm always produce correct results?设想对上图应⽤指定的升序式算法, 图中有A, B, C 三个顶点, A->B, B->A, B->C 三条边.如果⾸次 DFS 从 B 开始, 先向 A 遍历, 则访问顶点顺序为 (B (A, A) (C, C) B)升序排列 finishing time 是 A, C, B. 这样第⼆次进⾏ DFS 则应从 A 开始, 该算法结果显⽰ A, B, C 是⼀个强连通组件, ⽽实际情况不是如此.该算法不能保证通⽤性, 只有在选择特殊顶点作为起始点, 以及规定邻接表顺序的情况下,结果才有可能是正确的.Exercises 22.5-4Prove that for any directed graph G, we have (( GT)SCC)T = (G)SCC. That is, thetranspose of the component graph of GT is the same as the component graph of G.在图 G 中, 同⼀组件中的顶点可以互相连通. ⽽图 GT 中, 组件中的边虽然反转,但其顶点仍可以互相连通, 这⽅⾯是不受影响的, 组件之间的边全部反转, 同样不会形成新的组件. 所以 ((GT)SCC)T = (G)SCC, 即 GT 和 G 的强连通组件相同.Exercises 22.5-5Give an O (V + E)-time algorithm to compute the component graph of a directedgraph G = (V, E). Make sure that there is at most one edge between two verticesin the component graph your algorithm produces.(1) first DFS (G)if v finishorderList.push_front(v) // orderList 是 finishing time 降序队列时间 O(V + E)(2) for each v in Vfor each x in v.adjx.adj.push_back(v)即求 GT 时间 O(V + E)(3) second DFS (GT)for v in order of orderListmap v to scc // scc 是强连通组件for each x in v.adjif x.color = COLOR_BLACK // 代表这条边(v, x)是强连通组件间的边if x non-exist in scc.adj // 在DFS(GT)期间总搜索时间 O(E)scc.adj.push_back(x)即求 scc 和 scc.adj 时间 O(V + E), 所以算法时间复杂度 O(V + E).即：（1）利⽤STRONGLY-CONNECTED-COMPONENTS(G)将结点分类，给每个分量中的结点赋予⼀个相同的标号，时间为O(V+E)。