法处理冲突。6分
1构造HASH表。2分别求查找成功和不成功时的平均查找长度。
2．给定表（1914221520215610）（8分）（1）按元素在表中的次序，建立一棵二叉排序树
第2页共7页
f（2）对1中所建立的二叉排序树进行中序遍历，写出遍历序列。
（3）画出对2中的遍历序列进行折半查找过程的判定树。
3．已知二个稀疏矩阵A和B的压缩存储三元组表如下：
A
B
ijV
ijV
135
252
246
337
252
413
421
529
529
558
写出AB压缩存储的三元组表。（5分）
4．已知一维数组中的数据为（1812255318）试写出插入排序（升序）过程。并指出具有
个元素的插入排序的时间复杂度是多少？5分
5．已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。8分，要有
过程
ABCDEF
A651
B

6

5
3

C572
D

1
5
7

6
4

E366


F246
（1）求从顶点A开始的最小生成树。
（2）分别画出以A为起点的DFS生成树和BFS生成树。
6．已知数据六个字母及在通信中出现频率如下表：
A
B
C
D
E
F
01501501
010203
把这些字母和频率作为叶子结点及权值，完成如下工作7分，要有过程。
（1）画出对应的Huffma
树。
（2）计算带权路径长度WPL。
（3）求A、B、C、D、E、F的Huffma
编码。
第3页共7页
f7．已知有如下的有向网：
A
2
5
B
3
E
6
4C10
6D12
求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）
2
三、设计题（30分，每题10分用C语言写出算法，做在答题纸
上）
1．已知线性表（a1a2…a
）以顺序存储结构为存储结构，其类型定义如下：
defi
eLIST_INIT_SIZE100顺序表初始分配容量
typedefstruct
Elemtypeelem
顺序存储空间基址
i
tle
gth
当前长度（存储元素个数）
SqList
设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的
平均时间复杂度。其算法函数头部如下：StatusListDeleteSqlistLElemtypex……
2．设顺序栈如左图所示。其中结点定义如下：
typedefstructElemtypebase栈底指针Elemtypetop栈顶指针
Stack设计算法，将栈顶元素出栈并存入e中．
top
a

…
a2a1
base
3．设二叉链树的类型定义如下：typedefi
tElemtypetypedefstruct
odeElemtypedatastruct
odelchildrchildBi
NodeBi
Tree
试写出求该二叉树叶子结点数的算法
第4页共7页
fStatusCou
tLeavesBi
Treerooti
t
isthe
umberofleaves
……
答案：
选择题（每题1分）
1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C
一、填空题
1．设计、实现
2．特殊、栈顶
3．LOC（a1r