Mathematics

最小生成树是指一个加权图的具有最小权的连通生成子图.

由于在所有连通生成子图中, 生成树的边数最少, 因此就是具有最小权的连通生成子树.

寻找最小生成树有好几种算法: Kruskal 算法、Prim 算法

Kruskal 算法的 C++ 实现:

https://www.sanfoundry.com/cpp-program-find-mst-kruskals-algorithm/

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

/**
* 拓扑排序(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
*
*/

二叉树

二叉查找树

AVL 树

完全二叉树

理想二叉树

满结点树

References:

http://www.cnblogs.com/lxw0109/p/binary-tree.html

设我们实现三数中值例程如下：

找出 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: 这里的运行时间是指时间复杂度.

用链接方式存储的队列, 在进行插入运算时

1. 仅修改头指针
2. 头、尾指针都要修改
3. 仅修改尾指针
4. 头、尾指针可能都要修改

【code】

\begin{abcd2}
{用链接方式存储的队列, 在进行插入运算时}
{仅修改头指针}
{头、尾指针都要修改}
{仅修改尾指针}
{头、尾指针可能都要修改}
\end{abcd2}

栈和队列都是

1. 顺序存储的线性结构
2. 链式存储的非线性结构
3. 限制存取点的线性结构
4. 限制存取点的非线性结构

【code】

\begin{abcd2}
{栈和队列都是}
{顺序存储的线性结构}
{链式存储的非线性结构}
{限制存取点的线性结构}
{限制存取点的非线性结构}
\end{abcd2}
answer:=C

设用链表作为栈的存储结构, 则退栈操作

1. 必须判别栈是否为满
2. 必须判别栈是否为空
3. 判别栈元素的类型
4. 对栈不作任何判别

【code】

\begin{abcd2}
{设用链表作为栈的存储结构, 则退栈操作}
{必须判别栈是否为满}
{必须判别栈是否为空}
{判别栈元素的类型}
{对栈不作任何判别}
\end{abcd2}
answer:=[B]

下列哪一种排序用到了递归

1. 快速排序
2. 堆排序
3. 谢尔排序
4. 插入排序

【code】

\begin{abcd}
{下列哪一种排序用到了递归}
{快速排序}
{堆排序}
{谢尔排序}
{插入排序}
\end{abcd}
%answer:=A

下面关于线性表的叙述错误的是

1. 线性表采用顺序存储必须占用一片连续的存储空间
2. 线性表采用链式存储不必占用一片连续的存储空间
3. 线性表采用链式存储便于插入和删除操作的实现
4. 线性表采用顺序存储便于插入和删除操作的实现
    

【代码】

\begin{abcd4}
{下面关于线性表的叙述{\bf 错误}的是}
{线性表采用顺序存储必须占用一片连续的存储空间}
{线性表采用链式存储不必占用一片连续的存储空间}
{线性表采用链式存储便于插入和删除操作的实现}
{线性表采用顺序存储便于插入和删除操作的实现}
\end{abcd4}
%%answer:=D