四、畫圖/計算/證明/算法分析（30分）
（1）證明題（8分）
如果一棵樹有n1個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，…… ，nm個度為m的結(jié)點(diǎn)，證明葉結(jié)點(diǎn)的個數(shù)n0 = 1+ ｛提示：模仿二叉樹性質(zhì)證明｝。
（2）畫圖及計算題（8分）
某工程的AOE網(wǎng)如右圖所示，弧上的權(quán)值為活動a1～a10的期限（即完成活動所需的天數(shù)）。
求：
①該工程各事件的最早發(fā)生時間Ve和允許的最晚發(fā)生時間Vl及各活動的最早開始時間e和允許的最晚開始時間l (請列表Ve,Vl,e,l的各時間)，
②完成此項工程至少需要多少時間，及哪些活動是關(guān)鍵活動？
（3）已知某段電文中僅可能出現(xiàn)C, A, T, F, I五個字符，它們出現(xiàn)的頻度分別為35, 15, 25, 7, 18。請圖示一棵哈夫曼樹并給出各字符的哈夫曼編碼。（7分）
（4）給出的一組記錄的關(guān)鍵字{78,12,45,98,23,109,85,68,89,256,34}，①寫出對這組記錄進(jìn)行一趟快速排序的結(jié)果，并說明這趟排序中關(guān)鍵字比較的次數(shù)為多少；②將這組記錄關(guān)鍵字建成一個大根堆（堆頂元素值大）。（7分）
五、程序填空（每格2分，共20分）
1．有序線性表類（帶表頭的單鏈表結(jié)構(gòu)）的定義如下：
重慶分公司
重慶分公司
tmd 氣死了2．快速排序：對a[low]…a[high]的元素按關(guān)鍵字降序排序
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）已知一組記錄的關(guān)鍵字為｛18,2,10,6,78,56,45,50,110,8｝, 按輸入順序畫出此組記錄的平衡二叉樹，并求在等概率情況下查找成功的平均查找長度。（8分）
（2）設(shè)裝填因子為0.77, 散列函數(shù)H(Key) = Key MOD 11, 并反復(fù)用H(Key) +1解決沖突，試對（1）的記錄關(guān)鍵字構(gòu)造散列表，請圖示該表。（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試給出：①原圖，②鄰接表，③逆鄰接表，④強(qiáng)連通分量。(8分)
（4）已知關(guān)鍵字序列{38,12,21,77,65,7,38,53}，圖示采用快速排序方法（按關(guān)鍵字遞增）對其進(jìn)行第一趟排序時的過程（7分）
五、程序填空（每格2分，共20分）
1．有序線性表類的定義如下：
typedef char Datatype; // 或typedef int Datatype;
const int MaxListSize = 100;
class OrderSeqList
{
private:
Datatype data[MaxListSize];
int size; // 實(shí)際元素個數(shù)，即有效數(shù)據(jù)是data[0]..data[size-1]
public:
OrderSeqList(void);
~OrderSeqList(void);
int ListSize(void) const; // 返回線性表實(shí)際大小，即返回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); // 清空線性表
};下面是部分成員函數(shù)的實(shí)現(xiàn)：（這里的元素位置是指在data中的下標(biāo)）
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．編寫一個刪除子串的函數(shù)：
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分）
試證明二叉樹的性質(zhì)：若完全二叉樹的深度為K，則對于具有n個結(jié)點(diǎn)的完全二叉樹，其K是不大于long2n的最小正數(shù)。
（2）畫圖及計算題（8分）
某工程的AOE網(wǎng)如右圖所示，弧上的權(quán)值為活動a1～a10的期限（即完成活動所需的天數(shù)）。
求：
①該工程各事件的最早發(fā)生時間Ve和允許的最晚發(fā)生時間Vl及各活動的最早開始時間e和允許的最晚開始時間l (請列表Ve,Vl,e,l的各時間)，
②完成此項工程至少需要多少時間，及哪些活動是關(guān)鍵活動？
（3）已知某段電文中僅可能出現(xiàn)a, b, c, d, e五個字符，它們出現(xiàn)的頻度分別為32, 15, 24, 8, 19。要求：①圖示一棵哈夫曼樹；②再圖示一棵對應(yīng)于該哈夫曼樹的后根次序遍歷線索二叉樹。（7分）
（4）給出的一組記錄的關(guān)鍵字{25,18,46,2,53,39,32,4,74,67,60,11}，①圖示一棵處于平衡狀態(tài)的二叉排序樹（二叉查找樹）；②列出在等概率情況下各關(guān)鍵字在查找成功時的平均查找次數(shù)。（7分）
// ToDo
## 三、LZH組
### LZH 組一
### LZH 組二
### LZH 組三
### LZH 組四
### LZH 組五
### LZH 組六
### LZH 組七
## 四、LB組
### LB組一
### LB組二
### LB組三
### LB組四
### LB組五
### LB組六
### LB組七
### LB組八你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
