综合题
题型1 深度优先遍历与广度优先遍历
1．已知二维数组表示的图的邻接矩阵如下图所示。试分别给出深度优先和广度优先遍历序列，并画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
首先看邻接矩阵，矩阵中1代表相邻，0代表不相邻，
首先根据图表画出深度优先生成树，从1开始，找到7，7找到3，3找到4，4找到5，5找到6，（6找到1），代表主干已经找完
从6逆序向上找，6找到2，5找到10，4找到9，3找到8.故深度优先遍历序列：1，7，3，4，5，6，2，10，9，8
广度有先则是从1开始，全部找出，1找到7和9
7找到3和10，9找到5，7，10， 7和10之前重复了，故只有5
以此规则画出广度优先生成树
广度优先遍历序列：1，7，9，3，10，5，4，8，6，2
题型2 哈夫曼树题型
一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3,}，完成以下各题：
（1）设计最经济的编码方案。
（2）求此编码方案的平均长度、
此题应该用哈夫曼树来解决
从7个数中找到最小的两个自下而上组成哈夫曼树。
步骤如上，最后左子树为0，右子树为1 ，容易得
A01
B10
C001
D110
E111
F0000
G0001
平均长度等于，（长度×权值）的和除以权值的和
2×9+2×11+3×5+3×7+3×8+4×2+4×3=120
120/45=8/3
题型3 哈希题型
设有一组关键字{32,13,49,24,38,21,4,12}，其哈希函数为：H(key)=key % 7，采用开放地址法的线性探查法解决冲突，试在0～9的哈希地址空间中对该关键字序列构造哈希表，并求等概率下查找成功和查找失败的平均查找长度。（10分）
读题有八个关键字，0-9的哈希地址空间，
首先按照顺序将关键字加入哈希表中，
红色区域为查找次数，绿色为红色列的和，将元素个数比上17即为查找成功的值，即ASL=17/8；
此题mod7，共有0123456 ，7种可能性，
这7项每一项离空位的查找次数分别为，3，2，1，7，6，5，4.和为28，故不成功的ASL=28/7=4
题型4 堆排序
5.有一组关键字序列{66,89,8,123,9,44,55,37,200,127,98}：
（1）请将其调整成初始大根堆，并画出初始大根堆的树型表示。（5分）
（2）采用堆排序实现按关键字递增排序，请画出当有1个最大的关键字已放置到最终位置时，剩余关键字构成的大根堆。（5分）
将最终结果最大位，即200输出，200与66替换，继续调整堆，得到以上答案。
题型4 二叉树综合
有一棵二叉排序树按先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)。回答以下问题：
（1）画出该二叉排序树。
（2）给出该二叉排序树的中序遍历序列。
（3）求在等概率下的查找成功和不成功情况下的平均查找长度。
首先看题：
已知先序遍历，而中序遍历即为此序列的顺序排列，得中序遍历结果为(2,5,6,8,10,12,15,16,18,20)。
体干解读完成，看第一小题：
画出二叉树
先序(12,5,2,8,6,10,16,15,18,20)
中序(2,5,6,8,10,12,15,16,18,20)
第一步： 根据先序遍历可知12 为根，根据中序遍历结果从12 分为左右两部分。
第二步：看左边，左边有2，5，6，8，10，五个元素，看右边，有15，16，18，20四个元素
第三步：先序遍历中5比2 先出现，故5是2的根，以此结合顺序得到二叉树图。
中序遍历序列
第二题求
刚才已经给出，切记，中序序列是一个顺序序列
等概率下查找成功/不成功查找长度
第三题，在二叉树中，
成功长度的求法
是，看元素所在的深度，该深度的元素个数的乘积比上总元素数
（1* 1 + 2* 2 + 3* 4 + 4* 3）/10=2.9
不成功的求法
是首先补全二叉树，如图，补全的元素的深度减一乘以元素个数，比上新填的补全元素
(3 * 5+4 * 6）/11=39/11