2.4　习题

2.1　请计算满足下面两个条件的实数x的区间：①12.2　证明:对于任意整数n≥1，log(n+1)=log n+1
(提示：将n划分为2k≤n≤2k+1－1)。
2.3　对于斐波那契数列，请证明：
1） Fn是偶数当且仅当n能被3整除。
2） F2n－Fn+1Fn－1=(－1)n+1。
2.4　给定一棵完美二叉树，记其节点数为n，高度为h，叶节点数为l，内部节点数为t。
1） 给定上述4个量中的任意一个，请推导出其他3个量。
2） 请计算完美二叉树任意一层的节点个数。
①如果任意指定深度为p的一层节点，请计算该层节点个数np(0≤p≤h)。
②如果任意指定高度为q的一层节点，请计算该层节点个数nq(0≤q≤h)。
2.5　对于一棵非空的二叉树T，记其中叶节点的个数为n0，有一个子节点的节点个数为n1，有两个子节点的节点个数为n2。
●如果T为一棵2-tree，请证明n0=n2+1。
●如果T为一棵任意二叉树，n0和n2是否满足上述关系？请证明你的结论。
2.6　（函数渐近增长率的基本性质） 　请证明函数渐近增长率的如下性质：
1） O、Ω、Θ、o、ω这5种关系均满足传递性。
2） O、Ω、Θ这3种关系均满足自反性。
3） Θ是一个等价关系。
4） f(n)=Θ(g(n)) iff f(n)=O(g(n))且f(n)=Ω(g(n))。
5） O、 o和Ω、ω之间有一种对偶关系，即f=O(g) iff g=Ω(f)，f=o(g) iff g=ω(f)。
6） o(g(n))∩ω(g(n))= ?Θ(g(n))∩o(g(n))= ?Θ(g(n))∩ω(g(n))= А?
2.7　请将下面的函数按照渐近增长率从低到高的顺序进行排序。如果有多个函数其渐近增长率相同，请予以指出。
1） 将下面的函数排序：n,2n,n log n,n3,n2,log n,n－n3+7n5,n2+log n2） 将下面的函数同1）中的函数置于一起进行排序(假设0<ε<1)：en,n,2n－1,loglog n,(log n)2,n!,n1+ε2.8　对于斐波那契数列，请判断下面两个结论的正误，并证明你的结论：
1） 对于n≥1,F(n)≤10032n。
2） 对于n≥1,F(n)≥0.0132n。
2.9　对于大小为n的输入，假设在最坏情况下，算法1需要执行的步数为f(n)=n2+4n，算法2需要执行的步数为g(n)=29n+3。当n为多少时，算法1比算法2快(在最坏情况下)？
2.10　请证明log(n!)=Θ(n log n)。(注：你可以通过Stirling公式得到一个证明；如果不能使用Stirling公式，你能否得到另一个证明？)
2.11　已知k log k=Θ(n)，请证明：k=Θ(n/log n)。
2.12　函数log n!是否多项式有界？函数loglog n!呢？请给出证明。
2.13　请比较f(n)、g(n)的渐近增长率：f(n)=nlog n,g(n)=(log n)n2.14　精确求解递归式T(n)=∑n－1i=1T(i)+k，其中k为常数，T(1)=1。
2.15　计算T(n)的渐近增长率，可以假设T(1)=1,n>1，c是正的常量。
1） T(n)=2T(n/3)+1。
2） T(n)=T(n/2)+c log n。
3） T(n)=T(n/2)+cn。
4） T(n)=2T(n/2)+cn。
5） T(n)=2T(n/2)+cn log n。
6） T(n)=2T(n/2)+cn2。
7）T(n)=49T(n/25)+n3/2log n。
8） T(n)=T(n－1)+2。
9） T(n)=T(n－1)+nc，常量c≥1。
10） T(n)=T(n－1)+cn，常量c>1。
11） T(n)=T(n/2)+T(n/4)+T(n/8)+n。
2.16　假设T(1)=0，且对所有n≥2，T(n)=T(n/2)+T(n/2)+n－1，请证明：T(n)=nlog n－2log n+12.17　给定算法的时间复杂度的递归式T(n)=n・T(n)+n，但是它并不满足Master定理所需要的形式。请计算算法的时间复杂度。
2.18　给定递归表达式T(n)=aTnb+f(n)。选择合适的a、 b和f(n)使得Master定理的3种情况均不能应用于求解该递归表达式。
2.19　假设你可以选择如下3个算法来解决当前的问题：
●算法A将问题划分为5个规模为一半的子问题，递归地解每个子问题，合并这些子问题需要线性的时间复杂度。
●算法B将一个规模为n的问题划分为两个规模为n－1的子问题，递归地解这两个子问题，合并这些子问题需要常数的时间复杂度。
●算法C将规模为n的问题划分为9个规模为n3的子问题，递归地解每个问题，合并这些子问题的时间复杂度是O(n2)。
每个算法的时间复杂度是多少(以 O 来表示)，你会选择哪一个算法？
2.20　请分别给出下面4个算法MYSTERY、PERSKY、PRESTIFEROUS和CONUNDRUM的结果(用含有n的表达式表示)，以及在最坏情况下的运行时间(用O表示)。1　Algorithm:MYSTERY(n)
2　r∶=0;
3　for i∶=1 to n-1 do
4　for j∶=i+1 to n do
5　for k∶=1 to j do
6　r∶=r+1;7　return r;1　Algorithm:PERSKY(n)
2　r∶=0;
3　for i∶=1 to n do
4　for j∶=1 to i do
5　for k∶=j to i+j do
6　r=r+1;7　return r;1　Algorithm:PRESTIFEROUS(n)
2　r∶=0;
3　for i∶=1 to n do
4　for j∶=1 to i do
5　for k∶=j to i+j do
6　for l∶=1 to i+j－k do
7　r∶=r+1;8　return r;1　Algorithm:CONUNDRUM(n)
2　r∶=0;
3　for i∶=1 to n do
4　for j∶=i+1 to n do
5　for k∶=i+j－1 to n do
6　r∶=r+1;7　return r;第二部分　朴素遍历朴素遍历是最简单最基本的算法设计策略，利用计算机的优势――善于做简单重复的事情，速度很快，且基本不犯错，我们经常可以通过枚举所有需要考虑的情况来求解算法问题。虽然朴素遍历的策略往往不能得到最高效的算法设计，但它经常是后续改进必要的基础。
针对不同的数据结构，遍历的方法会有很大的不同。我们首先考虑线性表的遍历。线性表是最常用的一种存储算法输入数据的数据结构，其遍历实现简单，易于分析。通过线性表的遍历我们可以初步解决选择、查找、排序等经典的算法问题，为后续更高效地解决这些问题打下基础。
图是一种计算机科学中广泛使用的数学概念与数据结构，很多算法问题适合采用图来建模，因而图遍历成为解决这类问题的支撑技术。图本质上表示的是一组元素之间的二元关系，而图遍历则是循着元素间的关系，逐一处理所有的元素。根据遍历方式的不同，图遍历分为深度优先遍历与广度优先遍历，我们分别进行讨论。对于这两种遍历方式，首先给出遍历的算法框架；其次详细分析遍历过程中每个点和边的状态变化，这主要围绕图中每个点、每条边的染色和遍历过程中形成的遍历树来讨论；最后结合典型问题的求解来展示图遍历算法的运用。