按类别列出问题

Mathematics


计算数学 >> 数据结构
Questions in category: 数据结构 (Data Structure).

<[1] [2] [3] [4] >

1

MST(Minimum Spanning Tree)最小生成树

Posted by haifeng on 2018-04-16 10:38:37 last update 2018-04-16 10:38:37 | Answers (0) | 收藏

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

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

 

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

 

Kruskal 算法的 C++ 实现:

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

 

2

Josephus 问题

Posted by haifeng on 2018-04-10 13:08:04 last update 2018-04-10 15:14:26 | Answers (0) | 收藏

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

 

3

拓扑排序

Posted by haifeng on 2018-03-20 22:37:12 last update 2018-03-20 22:37:12 | Answers (0) | 收藏

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

4

关于二叉树的基本概念

Posted by haifeng on 2017-07-07 12:43:16 last update 2017-07-07 12:43:16 | Answers (0) | 收藏

二叉树

二叉查找树

AVL 树

完全二叉树

理想二叉树

满结点树

 

 

References:

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

5

快速排序中的三数中值例程

Posted by haifeng on 2017-06-20 15:27:08 last update 2017-06-21 16:44:05 | Answers (0) | 收藏

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

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

6

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

Posted by haifeng on 2015-06-15 09:39:22 last update 2015-06-15 09:39:22 | Answers (0) | 收藏

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

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

【code】

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

7

栈和队列的共同点

Posted by haifeng on 2015-06-15 09:30:47 last update 2015-06-15 09:30:47 | Answers (0) | 收藏

栈和队列都是

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

 


【code】

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

8

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

Posted by haifeng on 2015-06-15 09:27:43 last update 2015-06-15 09:27:43 | Answers (0) | 收藏

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

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

【code】

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

9

用到递归的排序算法

Posted by haifeng on 2015-06-15 09:24:05 last update 2015-06-15 09:24:05 | Answers (0) | 收藏

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

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

 


【code】

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

10

线性表采用顺序存储和链式存储的区别

Posted by haifeng on 2015-06-15 09:16:12 last update 2015-06-15 09:16:12 | Answers (0) | 收藏

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

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

【代码】

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

<[1] [2] [3] [4] >

Search

New posted more ...