练 习
1. 内存中一片连续空间（不妨假设地址从1到m ），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 答：S1空间地址1->M
S2空间地址M->1
即S1存储地址不断增加，S2存储地址为不断减小。
2. 叙述前序和中序遍历二叉树的步骤；一棵前序序列为1,2,3,4的二叉树, 其中序序列可能是4,1,2,3吗? 设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9, 其中序序列为2,3,1,5,4,7,8,6,9, 试画出该二叉树。
答：前续遍历：根->左->右。
中续遍历：左->根->右。 不可能为4、1、2、
3.
3. 设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。 答：（1）构造平衡二叉搜索树：
先右旋，再左旋
（2）平均查找长度为树高度h=3.
4. 设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：
H 0(key)=key%13; 注：％是求余数运算（＝mod ） H i =(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,…，m-1 其中，函数REV （x ）表示颠倒10进制数x 的各位，如REV(37)=73,REV(7)=7等。若插
入的关键码序列为{2,8,31,20,19,18,53,27}。 (1)试画出插入这8个关键码后的散列表。 (2)计算搜索成功的平均搜索长度ASL 。 答：（1）（注：代码看附录）
（2）ASL = (1 + 1 + 1 + 1 + 1 + 2 + 1 + 1)/8 = 1.125
5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
答：有两种选择：
6. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： （1）归并排序 每归并一次书写一个次序。 （2）快速排序 每划分一次书写一个次序。
（3）堆排序 先建成一个最大堆，然后每从堆顶取下一个元素后，将堆调整一次。 答：（1）归并排序：划分
29 18 25 4729 18 25 4729 18 25 4729 18 25 47
58 12 5158 12 5158 12 5158 12 51
10101010
归并：
10 12 18 1925 47 515818 19 25 4710 12 515818 19 25 4712 58 105129 18 25 47
58 12 51
10
（2）快速排序：
29 18 25 4758 12 511010 18 25 2958 12 514710 18 25 2958 12 514710 18 25 2947 12 515810 18 25 2947 12 515810 18 25 2912 47 515810 18 25 2912 47 515810 18 25 29
12 47 51
58
注：红色数字为选定的Pivot ，绿色为位置选定元素。 （3）堆排序： 建最大堆：
29 18 25 4758 12 511029 18 25 4758 12 511029 18 51 4758 12 251029 58 51 4718 12 251058 29 51 47
18 12 25
10
注：红色为调整的结点，绿色为调整结束。
取一个元素之后，数列为{10，29，51，47，18，12，25，调整：
10 29 51 4718 12 2551 29 10 4718 12 2551 29 25 47
18 12 10
10}
7. 假设用于通讯的电文由 5个字母组成，A B C D E F ，字母在电文中的出现频率分别为 0.09，0.12，0.07，0.22，0.23，0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。（左子树根节点值不大于右子树根节点值） 答：Huffman 树：
编码：
0.09 0.12 0.07 0.22 0.23 0.27
1111 110 1110 00 01 10
8. 已知序列（50，72，43，85，75，20，35，45，65，30），请以顺序插入方式构造二叉排序树，并画出删除结点72之后的二叉排序树。
答：建立二叉排序树（二叉搜索树）
采用替换删除法，删除结点72后：
9. 已知带权无向图G 的邻接矩阵是A 。
(1) 画出图G ；
(2) 分别画出一颗从V1出发的深度优先生成树和广度优先生成树；
(3) 画出一棵最小生成树。 答：图G 为：
（2）从V1出发 深度优先生成树为：
广度优先生成树为：
（3）最小生成树：
10. 假定一组记录的排序码为(46，79，56，38，40，84，50，42) ，利用堆排序方法画出初始大顶堆（以树状表示）。 答：图示如下：
11. 图的深度优先搜索类似于BFS, 不同之处在于使用栈代替BFS 中的队列，进出队列的操作改为入出栈的操作。即当一个顶点的一个邻接点被搜索后，下一个搜索的出发点应该是最近入栈(栈顶) 的顶点。用 深度优先搜索方法搜索下图, 设初始出发点为1。
(1) 画出搜索过程中栈的变化。
空
3 1
2
7 6 2
6 2
2
5 4
8 4
4
空
(2) 写出顶点的访问次序（当从某顶点出发搜索他的邻接点时，请按邻接点序号递增序搜索, 以使答案唯一）。
12. 按照次序输入关键字的值建立2-3树(3阶B-树):(68,54,82,35,75,90，103，22) 。 (1)请画出所建的2-3树。
(2)如果此后依次删除22,75，画出每一步执行后的2-3树的状态。 答：（1）2-3树为：
（2）删除操作：
13
．已知如下树林，画出对应的二叉树。
答：转化为二叉树为：
14. 已知二叉树，画出中序的线索。
答：线索化后为：
15. 以下图为例，按Dijkstra 算法计算得到的从顶点A 到其他各个顶点的最短路径和最短路径长度。
答：运用Dijkstra 算法可生成如下：
长度 1 8 6 8
B C D E
最短路径(A)
A->B A->B->D->C A->B->D A->B->D->E
附录
1、双hash 函数代码
#include
using namespace std;
int rev(int h) {
return ((h
int fh(int h, int n); void init(int *, int ); void print(int *, int );
int main() {
int h = 0, n, tmp; int HT[13];
init(HT, 13);
int keys[] = {2,8,31,20,19,18,53,27};
for (int i = 0; i
n = 0;
while (true ) {
tmp = fh(keys[i], n);
if (HT[tmp] == 0) {
HT[tmp] = keys[i]; break ; } else {
n ++;
} } }
print(HT, 13);
return 0; }
int fh(int h, int n) {
if (n == 0) {
return h % 13; } else {
return (fh(h, n - 1) + rev(h + 1)%11 + 1) % 13; } }
void init(int *a, int s) {
for (int i = 0; i
a[i] = 0; } }
void print(int *a, int s) {
for (int i = 0; i
cout
练 习
1. 内存中一片连续空间（不妨假设地址从1到m ），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 答：S1空间地址1->M
S2空间地址M->1
即S1存储地址不断增加，S2存储地址为不断减小。
2. 叙述前序和中序遍历二叉树的步骤；一棵前序序列为1,2,3,4的二叉树, 其中序序列可能是4,1,2,3吗? 设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9, 其中序序列为2,3,1,5,4,7,8,6,9, 试画出该二叉树。
答：前续遍历：根->左->右。
中续遍历：左->根->右。 不可能为4、1、2、
3.
3. 设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。 答：（1）构造平衡二叉搜索树：
先右旋，再左旋
（2）平均查找长度为树高度h=3.
4. 设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：
H 0(key)=key%13; 注：％是求余数运算（＝mod ） H i =(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,…，m-1 其中，函数REV （x ）表示颠倒10进制数x 的各位，如REV(37)=73,REV(7)=7等。若插
入的关键码序列为{2,8,31,20,19,18,53,27}。 (1)试画出插入这8个关键码后的散列表。 (2)计算搜索成功的平均搜索长度ASL 。 答：（1）（注：代码看附录）
（2）ASL = (1 + 1 + 1 + 1 + 1 + 2 + 1 + 1)/8 = 1.125
5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
答：有两种选择：
6. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： （1）归并排序 每归并一次书写一个次序。 （2）快速排序 每划分一次书写一个次序。
（3）堆排序 先建成一个最大堆，然后每从堆顶取下一个元素后，将堆调整一次。 答：（1）归并排序：划分
29 18 25 4729 18 25 4729 18 25 4729 18 25 47
58 12 5158 12 5158 12 5158 12 51
10101010
归并：
10 12 18 1925 47 515818 19 25 4710 12 515818 19 25 4712 58 105129 18 25 47
58 12 51
10
（2）快速排序：
29 18 25 4758 12 511010 18 25 2958 12 514710 18 25 2958 12 514710 18 25 2947 12 515810 18 25 2947 12 515810 18 25 2912 47 515810 18 25 2912 47 515810 18 25 29
12 47 51
58
注：红色数字为选定的Pivot ，绿色为位置选定元素。 （3）堆排序： 建最大堆：
29 18 25 4758 12 511029 18 25 4758 12 511029 18 51 4758 12 251029 58 51 4718 12 251058 29 51 47
18 12 25
10
注：红色为调整的结点，绿色为调整结束。
取一个元素之后，数列为{10，29，51，47，18，12，25，调整：
10 29 51 4718 12 2551 29 10 4718 12 2551 29 25 47
18 12 10
10}
7. 假设用于通讯的电文由 5个字母组成，A B C D E F ，字母在电文中的出现频率分别为 0.09，0.12，0.07，0.22，0.23，0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。（左子树根节点值不大于右子树根节点值） 答：Huffman 树：
编码：
0.09 0.12 0.07 0.22 0.23 0.27
1111 110 1110 00 01 10
8. 已知序列（50，72，43，85，75，20，35，45，65，30），请以顺序插入方式构造二叉排序树，并画出删除结点72之后的二叉排序树。
答：建立二叉排序树（二叉搜索树）
采用替换删除法，删除结点72后：
9. 已知带权无向图G 的邻接矩阵是A 。
(1) 画出图G ；
(2) 分别画出一颗从V1出发的深度优先生成树和广度优先生成树；
(3) 画出一棵最小生成树。 答：图G 为：
（2）从V1出发 深度优先生成树为：
广度优先生成树为：
（3）最小生成树：
10. 假定一组记录的排序码为(46，79，56，38，40，84，50，42) ，利用堆排序方法画出初始大顶堆（以树状表示）。 答：图示如下：
11. 图的深度优先搜索类似于BFS, 不同之处在于使用栈代替BFS 中的队列，进出队列的操作改为入出栈的操作。即当一个顶点的一个邻接点被搜索后，下一个搜索的出发点应该是最近入栈(栈顶) 的顶点。用 深度优先搜索方法搜索下图, 设初始出发点为1。
(1) 画出搜索过程中栈的变化。
空
3 1
2
7 6 2
6 2
2
5 4
8 4
4
空
(2) 写出顶点的访问次序（当从某顶点出发搜索他的邻接点时，请按邻接点序号递增序搜索, 以使答案唯一）。
12. 按照次序输入关键字的值建立2-3树(3阶B-树):(68,54,82,35,75,90，103，22) 。 (1)请画出所建的2-3树。
(2)如果此后依次删除22,75，画出每一步执行后的2-3树的状态。 答：（1）2-3树为：
（2）删除操作：
13
．已知如下树林，画出对应的二叉树。
答：转化为二叉树为：
14. 已知二叉树，画出中序的线索。
答：线索化后为：
15. 以下图为例，按Dijkstra 算法计算得到的从顶点A 到其他各个顶点的最短路径和最短路径长度。
答：运用Dijkstra 算法可生成如下：
长度 1 8 6 8
B C D E
最短路径(A)
A->B A->B->D->C A->B->D A->B->D->E
附录
1、双hash 函数代码
#include
using namespace std;
int rev(int h) {
return ((h
int fh(int h, int n); void init(int *, int ); void print(int *, int );
int main() {
int h = 0, n, tmp; int HT[13];
init(HT, 13);
int keys[] = {2,8,31,20,19,18,53,27};
for (int i = 0; i
n = 0;
while (true ) {
tmp = fh(keys[i], n);
if (HT[tmp] == 0) {
HT[tmp] = keys[i]; break ; } else {
n ++;
} } }
print(HT, 13);
return 0; }
int fh(int h, int n) {
if (n == 0) {
return h % 13; } else {
return (fh(h, n - 1) + rev(h + 1)%11 + 1) % 13; } }
void init(int *a, int s) {
for (int i = 0; i
a[i] = 0; } }
void print(int *a, int s) {
for (int i = 0; i
cout