2017 秋 -Quiz

一 排序

1-1

如果在 1000000 个记录中找出 2 个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？

1-2

关于堆排序方法

1-2-1

简述该方法的基本思想

1-2-2

写出堆排序算法；

1-2-3

分析该算法的时间复杂度.

1-3

叙述基数排序算法，并对下列整数序列图示其基数排序的全过程.

$$(179,208,93,306,55,859,984,9,271,33)$$

1-4

给出一组关键字： $29,18,25,47,58,12,51,10$ , 分别写出按下列各种排序方法进行排序时的变化过程：

1-4-1

归并排序 每归并一次书写一个次序.

1-4-2

快速排序 每划分一次书写一个次序.

1-4-3

堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次.

二 树

2-1

树和二叉树之间有什么样的区别与联系？解释几种常见的表示方法及优缺点.

2-2

已知一棵度为 $m$ 的树有 $n_1$ 个度为 1 的结点， $n_2$ 个度为 2 的结点， $\dots$, $n_m$ 个度为 $m$ 的结点，问该树中有多少个叶子结点？

2-3

将算术表达式 $((a+b)+c\ast (d+e)+f)\ast (g+h)$ 转化为二叉树.

2-4

二叉树 T 的中序遍历序列和层次遍历序列分别是 BAFDGCE 和 ABCDEFG, 试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法

2-5

已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表.

2-6

设后序线索树中结点构造为 (Ltag, Lchild, Data, Rchild, Rtag), 其中：Ltag, Rtag 值为 0 时 Lchild、Rchild 分别为儿子指针；否则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点 $p$ 的直接前驱 $q$ 的算法.

2-7

描述优先队列的几种实现方法及解释其优缺点；编写算法建立最小堆.

2-8

给定一组数列 $(15,8,10,21,6,19,3)$ 分别代表字符 A, B, C, D, E, F, G 出现的频度，试叙述建立哈夫曼编码的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点.

三 图

3-1

如果 $G_1$ 是一个具有 $n$ 个顶点的连通无向图，那么 $G_1$ 最多有多少条边？ $G_1$ 最少有多少条边？如果 $G_2$ 是一个具有 $n$ 个顶点的强连通有向图？如果 $G_3$ 是一个具有 $n$ 个顶点的弱连通有向图？

3-2

假定 $G=(V,E)$ 是有向图，其中 $V=\{1,2,\dots ,N\},N\ge 1$. $G$ 以邻接矩阵方式存储，邻接矩阵为 $A$. 若 $i$ 到 $j$ 有边，则 $A[i,j]=1$, 否则 $A[i,j]=0$. 请给出一个算法判断 $G$ 是否为无环图 (即是否不存在回路), 要求时间复杂度为 $O(n^2)$.

3-3

设无向图 G 有 n 个点 e 条边，写一算法建立 G 的邻接多表，要求该算法时间复杂性为 $O(n+e)$ , 且除邻接多表本身所占空间之外只用 $O(1)$ 辅助空间.

3-4

假定有 $n$ 个城市组成的一个公路网，且认为公路是有向的，并用代价邻接矩阵表示该网络。试设计从指定城市 V1 到其他城市的最短路径的算法.

3-5

下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的 $n-1$ 条线路，画出所有可能的选择.