发布时间 : 星期四 文章湖南科技大学数据结构综合应用题更新完毕开始阅读
计算机——《数据结构》
第5页 共13页
3
5 2
6 4 1
3
5 2
6 4 1
3
2
1 5 4 6
14、画出具有三个结点的二叉树的所有形态。
15、图如右，请画出prim算法构造最小生成树的过程。
16、对于如下无向图，请画出其深度优先搜索和广度优先搜索生成的树（画出一棵即可）。
1 3
5
2 4
17、用线性探测法建立Hash表，Hash函数为H(key)=key mod 11,Hash表长度为10，现有一组关键字（61，
18，30，72，13，24），请画出相应的Hash表。
18、// 设元素的类型为T；aList是存储顺序表的数组； p为即将删除元素的位置 // 删除成功则返回true，否则返回false
template
计算机——《数据结构》
第6页 共13页
if (p < 0 || p > curLen-1) { // 检查删除位置是否合法 cout << \ return false ; } for (i = p; i < curLen-1; i++)
aList[i] = aList[i+1]; // 从位置p开始每个元素左移直到curLen curLen--; // 表的实际长度减1 return true; }
14-18题答案： 14、 A A A A A
B B B C B B
C C C C
15、 1 1 1 1
1 1 1 2 2
5 5 2 3 3 3 5
11
4 1 1 22 5 5 2 4 2 4 3 3 3
5 6 56
16、注意：生成树是不唯一的，应该是一个生成树森林。所以此题还存在其它画法。
1 3 5 2 4 计算机——《数据结构》
第7页 共13页
设从结点1出发开始深度优先搜索，得到如下一棵深度优先生成树：
1 3
5
2 4
设从结点1出发开始广度优先搜索，得到如下一棵广度优先生成树：
1 3 5
2 4 17、
0 1 2 3 4 5 6 7 13 24 61 18 61 mod 11=6 18 mod 11=7 30 mod 11=8
72 mod 11=6→7→8→9 13 mod 11=2 24 mod 11=2→3
8 30 9 72 19．设一棵二叉树的先序遍历序列为： A B D F C E G H
中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。（5分）
（2）画出这棵二叉树的后序线索树。（5分） （3）画出由这棵二叉树转换成的树（或森林）。（5分）
20．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（要求画出Huffman树并写出编码）（15分）
21．已知一个无向图如下图所示，用Kruskal算法生成最小树（假设以①为起点，要求画出构造过程）。（10分）
22．对于以下的图，写出它的四个不同的拓扑有序序列。（10分）
计算机——《数据结构》
第8页 共13页
23．采用哈希函数H（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。 （1） 构造哈希表（画示意图）；（5分） （2） 求装填因子；（1分）
（3） 等概率下成功的和不成功的平均查找长度。（4分）
24．数据结构与数据类型有什么区别？
24.“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
25．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。 *25.该算术表达式转化的二叉树如右图所示。
++ +fgh
+*
a+bc de
26．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C L M K N O F
P A
B D E G C
H F I KO J L M
P N O