1
高度为 $h$ 的 AVL 树, 其最少的结点数是多少?
[Hint]
高度为 $h$ 的 AVL 树, 其最少的结点数若记 $S(h)$, 则 $S(h)$ 有三部分组成: 1（根结点）, 左子树的最少结点数, 右子树的最少结点数.
由于 AVL 树的平衡条件是: 任意结点的左子树与右子树的高度之差的绝对值至多为 1. 因此如果左子树的最少结点数是 $S(h-1)$, 则右子树的最少结点数是 $S(h-2)$.
于是, 我们得到关于 $S(h)$ 的递推表达式:
\[
S(h)=S(h-1)+S(h-2)+1.
\]
这与 Fibonacci 的递推表达式非常类似, 仅相差一个常数 1.
试求出 $S(h)$ 的具体表达式.
P. 132 Ex 4.18
2
凸包(convex hull)问题是找出一个将平面上的点集围住的(面积)最小的凸多边形的问题.
试给出寻找凸包的一个 $O(N\log N)$ 算法.
References:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.
张怀勇 等译. Ex. 10.51, P.349
3
一维装球问题:
有 $N$ 个半径分别是 $r_1,r_2,\ldots,r_N$ 的圆盘(比如光盘). 将这些圆盘装到一个盒子中使得每个圆盘都与盒子的底边相切. 任何两个圆盘至多有一个公共点.
问这个盒子的底边长度最小是多少？
假设底边最短长是 $f(r_1,r_2,\ldots,r_N)$.
记 $h(x,y)=2\sqrt{xy}$.
Exer. 不妨假设 $r_1\leqslant r_2\leqslant r_3$. 记
\[
d=\max\{h(r_1,r_2)+h(r_1,r_3),\ h(r_2,r_3)\},
\]
证明
\[
f(r_1,r_2,r_3)=\max\{r_2+d, r_3\}+r_3.
\]
Q. $f(r_1,r_2,r_3,r_4)=?$
如果圆盘的排放是按原有顺序的, 若记 $\varphi_n(r_1,r_2,\ldots,r_n)$ 为排放这 $n$ 个圆盘的盒子底边的最短长度, 对于依次输入的 $r_1,r_2,\ldots,r_k$, 请编程依次输出 $\varphi_k$ 值.
References:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.
张怀勇 等译. Ex. 10.46, P.348
相关问题:
4
最小生成树是指一个加权图的具有最小权的连通生成子图.
由于在所有连通生成子图中, 生成树的边数最少, 因此就是具有最小权的连通生成子树.
寻找最小生成树有: Kruskal 算法、Prim 算法
Kruskal 算法的思想是, 程序管理的是一些连通子树的集合, 每次在添加新的边时, 考虑的是是否会形成环, 若不形成环, 则添加.
Prim 算法的思想是: 既然最终要得到的是最小生成树, 我们可以通过一条边接着一条边的生长方式形成最后的权最小的生成树.
从上面的两种思想, 可以看到, 最小生成树的生成算法本质上只有这两种.
Kruskal 算法的 C++ 实现:
http://www.technical-recipes.com/2012/kruskals-algorithm-in-c/
https://www.sanfoundry.com/cpp-program-find-mst-kruskals-algorithm/
5
Josephus 问题是指下面的游戏:
有 $N$ 个人坐成一圈, 编号依次为 $1,2,3,\ldots,N$.
从编号 $1$ 的人开始传递马铃薯. $M$ 次传递之后, 持有热马铃薯的人退出游戏, 圈缩小. 然后游戏从退出者下一位开始, 继续进行.
最终留下来的人获胜.
这样, 如果 $M=0$ 并且 $N=5$, 那么参加游戏的人依次退出, $5$ 号获胜.
如果 $M=1$ 并且 $N=5$, 那么退出的顺序就是 $2$、$4$、$1$、$5$. 最后是 $3$ 号获胜.
比如：
Josephus problem!
Please input the number of players: N = 5
Please input the gap: M = 1
N=5
M=1
start index =1
deleting 2
now vector a is
1 3 4 5
next index =2
--------------
start index =2
deleting 4
now vector a is
1 3 5
next index =3
--------------
start index =3
deleting 1
now vector a is
3 5
next index =1
--------------
start index =1
deleting 5
now vector a is
3
next index =2
--------------
start index =2
deleting 3
now vector a is
next index =1
--------------
=======================
The queue is:
2 4 1 5 3
References:
《数据结构与算法分析C++描述》（第3版）P.81, Exer 3.6.
https://en.wikipedia.org/wiki/Josephus_problem
6
/**
* 拓扑排序(Topological sorting)
*
* 拓扑排序问题的定义: 给定图 $G=(V,E)$, 将其顶点排成一列
* $v_{i1}, v_{i2}, \ldots, v_{in}$, 这里 $n$ 是顶点的个数.
* 要求满足下面的条件:
* 对所有边 $(v,w)\in E$, v 排在 w 的前面.
*
* 算法
* ====
* Step 1. 确定 in-degree 为 0 的顶点. 可以作为第一个顶点.
* 如果没有这样的顶点, 比如循环的图 A-->B-->C-->D-->A, 每个顶点的 in-degree > 0.
* 可以去掉某个边, 如成为: A-->B-->C-->D.
*
* 找到 in-degree=0 的顶点后, 将此顶点以及从该顶点出发的有向边删除.
*
* Example:
* A--->B--->C
* \ /|
* \ / | F
* \ / |
* * * v
* D--->E
*
* delete A and the edges start from A, it becomes
*
* B--->C C
* /| delete B /| delete C
* / | F ========> / | F ========>
* / | / |
* * v * v
* D--->E D--->E
*
* 将 A 输出. 然后重复此过程.
*
* output: A ==> B ==> C ==> D ==> E ==> F
*
* 如果中途在 delete B 之后选择 F 而不是 C 输出, 那么也可以, 此时得到线性序列
*
* output: A ==> B ==> F ==> C ==> D ==> E
*
*/
8
设我们实现三数中值例程如下：
找出 a[left]、a[center] 和 a[right] 的中值, 并将它与 a[right] 交换. 以通常的分割方法进行, 开始时 i 在 left 处且 j 在 right-1 处(而不是 left+1 和 right-2).
(1) 设输入为 $2,3,4,\ldots,N-1,N,1$. 对于该输入, 这种快速排序算法的运行时间是多少?
(2) 设输入数据呈反序排列, 对于该输入, 这种快速排序算法的运行时间又是多少?
Remark: 这里的运行时间是指时间复杂度.
9
用链接方式存储的队列, 在进行插入运算时
【code】
\begin{abcd2}
{用链接方式存储的队列, 在进行插入运算时}
{仅修改头指针}
{头、尾指针都要修改}
{仅修改尾指针}
{头、尾指针可能都要修改}
\end{abcd2}
10
栈和队列都是
【code】
\begin{abcd2}
{栈和队列都是}
{顺序存储的线性结构}
{链式存储的非线性结构}
{限制存取点的线性结构}
{限制存取点的非线性结构}
\end{abcd2}
answer:=C