四、画图/计算/证明/算法分析（30分）
（1）证明题（8分）
如果一棵树有n1个度为1的结点，n2个度为2的结点，…… ，nm个度为m的结点，证明叶结点的个数n0 = 1+ ｛提示：模仿二叉树性质证明｝。
（2）画图及计算题（8分）
某工程的AOE网如右图所示，弧上的权值为活动a1～a10的期限（即完成活动所需的天数）。
求：
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间)，
②完成此项工程至少需要多少时间，及哪些活动是关键活动？
（3）已知某段电文中仅可能出现C, A, T, F, I五个字符，它们出现的频度分别为35, 15, 25, 7, 18。请图示一棵哈夫曼树并给出各字符的哈夫曼编码。（7分）
（4）给出的一组记录的关键字{78,12,45,98,23,109,85,68,89,256,34}，①写出对这组记录进行一趟快速排序的结果，并说明这趟排序中关键字比较的次数为多少；②将这组记录关键字建成一个大根堆（堆顶元素值大）。（7分）
五、程序填空（每格2分，共20分）
1．有序线性表类（带表头的单链表结构）的定义如下：
tmd 气死了2．快速排序：对a[low]…a[high]的元素按关键字降序排序
void QuickSort(Datatype a[], int low, int high)
{
int i = low, j = high;
Datatype temp = a[low];
while (i< j)
{
while (i< j && ___________)
j--;
if (i< j)
a[i++] = a[j];
while (i< j && a[i].key >= temp.key)
______________;
if (i< j)
a[j--] = a[i];
}
a[i] = temp;
if (low< i)
QuickSort(a, low, i - 1);
if (i< high)
____________________;
}
void QuickSort(Datatype a[], int n)
{
QuickSort(a, 0, n - 1);
}四、画图/计算/证明/算法分析（30分）
（1）已知一组记录的关键字为｛18,2,10,6,78,56,45,50,110,8｝, 按输入顺序画出此组记录的平衡二叉树，并求在等概率情况下查找成功的平均查找长度。（8分）
（2）设装填因子为0.77, 散列函数H(Key) = Key MOD 11, 并反复用H(Key) +1解决冲突，试对（1）的记录关键字构造散列表，请图示该表。（7分）
（3）已知有向图的邻接矩阵为：
V0 V1 V2 V3 V4 V5
V0 0 ∞ ∞ ∞ ∞ ∞
V1 30 0 ∞ 40 ∞ ∞
V2 ∞ 20 0 ∞ ∞ 10
V3 ∞ ∞ 20 0 50 40
V4 10 ∞ ∞ ∞ 0 ∞
V5 20 10 ∞ ∞ 20 0试给出：①原图，②邻接表，③逆邻接表，④强连通分量。(8分)
（4）已知关键字序列{38,12,21,77,65,7,38,53}，图示采用快速排序方法（按关键字递增）对其进行第一趟排序时的过程（7分）
五、程序填空（每格2分，共20分）
1．有序线性表类的定义如下：
typedef char Datatype; // 或typedef int Datatype;
const int MaxListSize = 100;
class OrderSeqList
{
private:
Datatype data[MaxListSize];
int size; // 实际元素个数，即有效数据是data[0]..data[size-1]
public:
OrderSeqList(void);
~OrderSeqList(void);
int ListSize(void) const; // 返回线性表实际大小，即返回size
int ListEmpty(void) const; // 判断线性表是否为空
int Find(Datatype &item) const; // 返回item在线性表中的位置
Datatype GetData(int pos) const; // 取出线性表pos位置上的元素
void Insert(Datatype item); // 在有序线性表中插入新元素item
Delete(Datatype item); // 在有序线性表中删除元素item
void ClearList(void); // 清空线性表
};下面是部分成员函数的实现：（这里的元素位置是指在data中的下标）
int OrderSeqList::Find(Datatype &item) const
{
if (size == 0)
return -1;
int i = 0;
while (________________________)
i++;
if (item == data[i])
return i;
else
return -1;
}
void OrderSeqList::Insert(Datatype item)
{
int i;
if (___________________________)
{
cerr<< "顺序表已满，无法插入！"<< endl;
exit(1);
}
for (i = size; (data[i - 1] >item) && (i >0); i--)
data[i] = ___________;
data[i] = __________________;
size++;
}
OrderSeqList::Delete(Datatype item)
{
if (size == 0)
{
cerr<< "顺序表已空，无元素可删！"<< endl;
exit(1);
}
int loc = Find(item);
if (loc != -1)
{
for (int j = loc; j< size - 1; j++)
data[j] = _______________;
_______________;
}
}
2．编写一个删除子串的函数：
void deletestr(char *str, int start, int span)
{
int i;
int len = strlen(str);
if ((start< 0) || (start >len - 1))
return;
if ((start + span< -1) || (start + span >len))
return;
if (span >0)
for (i = start; i<= _______________; i++)
str[i] = ________________;
else
for (i = __________________; i<= len + span + 1; i++)
_______________;
}
四、画图/计算/证明/算法分析（30分）
（1）证明题（8分）
试证明二叉树的性质：若完全二叉树的深度为K，则对于具有n个结点的完全二叉树，其K是不大于long2n的最小正数。
（2）画图及计算题（8分）
某工程的AOE网如右图所示，弧上的权值为活动a1～a10的期限（即完成活动所需的天数）。
求：
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间)，
②完成此项工程至少需要多少时间，及哪些活动是关键活动？
（3）已知某段电文中仅可能出现a, b, c, d, e五个字符，它们出现的频度分别为32, 15, 24, 8, 19。要求：①图示一棵哈夫曼树；②再图示一棵对应于该哈夫曼树的后根次序遍历线索二叉树。（7分）
（4）给出的一组记录的关键字{25,18,46,2,53,39,32,4,74,67,60,11}，①图示一棵处于平衡状态的二叉排序树（二叉查找树）；②列出在等概率情况下各关键字在查找成功时的平均查找次数。（7分）
// ToDo
## 三、LZH组
### LZH 组一
### LZH 组二
### LZH 组三
### LZH 组四
### LZH 组五
### LZH 组六
### LZH 组七
## 四、LB组
### LB组一
### LB组二
### LB组三
### LB组四
### LB组五
### LB组六
### LB组七
### LB组八你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
