一、简述与证明
1. 给出排序稳定性的含义、作用和证明方法，并给出简单选择排序方法的排序稳定性证明。

2. 说明O 、、θΩ三种函数阶的定义，给出O 函数阶的示例证明过程。

3. 设n n g n n n n f log )(log )(=+=，，给出)()(n g n f 和间的函数阶证明过程。

二、方法选择
1. 只想得到N 个元素序列中第K 个最大元素之前的部分递减有序序列（K<<N ），列出2
种速度快的方法名称与原因。

2. 在一个连通无向图上，欲求从一点VI 到另一点VJ （V I ≠VJ ）所经结点数目最少的路
径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。

3. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，在前序、中
序、后序遍历方法中，是否所有遍历方法都适合，简述原因。

4. 在数轴上有n 个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到
右依次编号为1-N 。

试问：要查找每个给定值x 所在区间，你认为应选择什么方法查找最快，简述原因。

三、构造结果
1. 要计算矩阵连乘积M0 M1 M2 M3，M0r0*r1，M1r1*r2，M2 r2*r3，M3 r3*r4，各自的维数为
r0=10，r1=20，r2=50，r3=6，r4=80，按动态规划算法步骤，给出计算矩阵连乘积最优解的表示（即最小运算量的矩阵运算次序）。

2. 给出4个顶点的图如下：
只给出三种颜色，如何给4个顶点着色，使之有连边关系的顶点颜色不同，一共有多少种着色方法，请绘图说明。

四、编写算法
1. 判别给定（以二叉树链表存储）二叉树是否为二叉排序树的非递归算法。

2. 查找数据域为X 的节点，并输出X 节点的所有祖先。

五、编写算法
1. 已知有N 个节点的无向图，采用邻接表结构存储，要求由根开始逐层输出连通子图中
所有生成树中的各条边，边输出格式为（K i ，K j ）。

2. 树采用孩子-兄弟方式存放，节点结构为
A B
C D fch data nsid level
其中fch 表示指向第一个孩子，nisid 表示指向下一个兄弟，level 表示节点层次。

设根结点层次为1，其它以此类推。

编写算法，将数中所有节点层次值置入响应level 域。

五、编写算法并分析
1. 给定数组a[0:n-1]，设计一个算法，在最坏情况下用[
23n -2]次比较找出a[0:n-1]中元素
的最大值和最小值，并给出相关算法分析与证明。