10.4-5 给定一个n结点的二叉树，写出一个$O(n)$时间的非递归过程，将该树的每一个结点的关键字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间，且中过程中不得修改该树，即使是暂时的修改也不允许。
要完成$O(1))$的空间内遍历该树，需要每个结点需要能访问其父节点进行回溯。
1234567struct Tree{ Tree *parent; Tree *left; Tree *right; int key;};
中序遍历：
访问左孩子
访问右孩子
从左孩子返回，访问根节点，进入右孩子访问
从右孩子返回，整棵树访问完成，回溯...
Win10中shift+鼠标右键调出cmd窗口最近Win10系统更新，更新后发现之前按shift+鼠标右键时，菜单栏里面的cmd选项不见了，取而代之的是 Powershell窗口。用习惯了了cmd还是有点不习惯powershell。
下面是我Win10更新后shift+鼠标右键的选项栏的效果：
这里不做cmd和powershell的比较。简单来说powershell像是cmd的一个超集，不仅仅支持cmd的命令，还额外支持.net命令，也支持部分常用的Linux命令。powershell的字体颜色比cmd丰富点。但是相应的powershell所占用的资源更多，有时候我在pow...
9-2 (带权中位数)对分别具体以正权重$w_1,w_2,\dotsb,w_n$,且满足$\sum_{i=1}^{n}{w_i=1}$的$n$个互异的元素$x_1,x_2,\dotsb,x_n$来说，带权中位数$x_k$(较小中位数)是满足如下条件的元素：
\sum_{x_i < x_k}w_i x_k}w_i \leq \frac{1}{2}例如，如果元素是$0.1 ,0.35 ,0.05 ,0.1 ,0.15 ,0.05 ,0.2$，并且每个元素的权重等于本身(即对所有$i=1,2,\dotsb,7都有w_i=x_i$)，那么中位数是0.1，而带全中位数是0....
9.3-8 设X[1..n]和Y[1..n]为两个数组，每个都包含n个有序的元素，请设计一个$O(lgn)$时间的算法找出数组X和Y中所有2n个元素的中位数。下面假设中位数(低中位数，数组长度偶数时较小的那个)在数组$X$中。如果要求中间两个数的均值，只需要在该基础之上修改一点就好。
a、$X[k]=m$为中位数，对于数组$X$,有$k$个元素小于等于$X[k]$，同时有$n-k$个元素大于等于$X[k]$。当两个数组合并有序时，对于中位数来说，共有$n$个元素小于等于$X[k]$，n个元素大于等于$X[k]$。那么对于数组$Y$来说，有$n-k$个元素小于等于$X[k]$，$...
6-2（对d叉堆的分析）d叉堆与二叉堆很类似，但（一个可能的例外是）其中的每个非叶节点有d个孩子，而不是仅仅2个。a. 如何在一个数组中表示一个d叉堆？
假设数组从$A[1]$开始,它作为根，那么$A[1]$有d个孩子分别是$A[2]…A[d+1]$，共d个。那么对于$A[2]…A[d+1]$共d个结点，一共有$d^2$个结点，从$A[d+2]….A[d^2+d+1]$。依次类推。那么对于一个编号为$i$的结点的第$j$个孩子$(1 \leq j \leq d)$，
D-ARY-Parent(i)return $\lfloor (i-2)/d+1 \rfloor$
D-ARY-...
4-1（递归式例子）对下列每个递归式，给出T(n)的渐进上界和渐进下界。假定 $n\leq2$时T(n)时常数。给出尽量紧确的界，并验证其正确性。不会主方法的先看一下这篇博客：https://blog.csdn.net/qq_40512922/article/details/96932368
a. $T(n)=2T(n/2)+n^4$
证明：有$a=2,b=2,n^{log_ba}=n$，$f(n)=f(n^4)=\Omega(n^{\epsilon+1})$，其中$\epsilon=3$。下面证明正则条件：$\exists c<1,af(n/b)\leq cf(n)$
...
思考题2-4（逆序对） 假设A[1..n]是一个有$n$个不同数的数组，若iA[j]，则对偶(i,j)称为A的一个逆序对(inversion)。a.列出数组$$的5个逆序对。 逆序对有$(1,5),(2,5),(3,4),(3,5),(4,5)$
b.有集合$\{1,2,\dots,n\}$中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？ 当数组为 $\{1,2,\dots,n\}$为逆序时，即$\{n,n-1,\dots,1\}$时逆序对最多。对于 $\forall i,j \in [1,n],(i,j)$均为逆序对。此时共有逆序对$(_n^2)=n(n...
算法导论 第二章插入排序实现 插入排序算法是时间复杂度为 $O(n)$，输入规模$n$较小时，插入排序往往能有较好的效果。
最优情况：数据整体有序，无需须交换元素，时间复杂度$O(n)$
最坏情况：数据整体逆序，每个元素要 $1~n-1$次，时间复杂度为 $O(n^2)$。
插入排序中的常数因子较小使得在$n$在较小的时候，在很多情况能够运行更快。作为归并排序，快速排序等算法在小规模时处理的问题时的子程序。
书中的伪代码123456789INSERTION-SORT(A)1 for j = 2 to A.length2 key = A[j]...
算法导论-思考题1-11-1（运行时间的比较）假设求解问题的算法需要 $f(n)$微秒(microseconds)，对下表中每个函数$f(n)$和时间$t$可以确定在时间$t$内求解问题的最大规模$n$。中文版给的$f(n)$单位是毫秒，但看了原版，发现单位是微秒(microseconds)，故下面采用微秒来计算。
函数\时间
1秒钟
1分钟
1小时
1天
1月
1年
1世纪
$lgn$
$2^{10^6}$
$2^{6\times 10^7}$
$2^{3.6 \times 10^9}$
$2^{8.64 \times 10^{10}}$
$2^{2.592 \time...
算法导论9.1-1找第二小的元素1、证明：在最坏情况下，找到n个元素中第二小的元素需要 $n+ \lceil lgn \rceil -2$次比较。（提示：可以同时找到最小元素）做以下断言：无论采用何种比较算法，在寻找最小元素的过程中，第二小的元素一定与最小元素做过比较。显然，因为第二小的元素直到遇到最小元素前，一定会胜出进入下一轮。如果最小元素没有与第二小元素相比较，则无法得出该元素是最小的关系。
因此，要想是我们找到最小元素的比较次数最少，就需要在寻找最小元素的过程中与最小元素发生比较的次数尽量的少。
由于每次我们只能取两个元素进行比较，从而考虑每一轮将我们比较元素两两比较，...
