顶点 V1 V2 V3 V4 V5 V6 V7 Ve 0 15 2 12 21 17 30 Vl 0 15 13 15 21 20 30 活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 e 0 0 15 2 21 0 12 17 2 l 0 11 15 13 21 3 15 20 16 l-e 0 11 0 11 0 3 3 3 14 （2）关键路径是V1－V2－V5－V7 （3）a1,a3,a5是关键活动
第九章作业
1. 画出对长度10的有序表进行折半查找的判定树，并求其等概率时查找成功时的平均查
找长度。
2. 编写在一个顺序表中顺序查找的算法。 3. 编写在一个有序表中折半查找的算法。 4. 若查找一颗二叉排序树中查找的算法。
5. 若查找表中记录的关键序列为（19.14.01.22.7.25.6）
（1） 按元素在表中的次序逐个插入，画出生成后的二叉树。 （2） 求其等概率下查找成功时的平均查找长度。 （3） 按表中元素顺序构造一颗平衡二叉树
（4） 对平衡二叉树求其等概率下查找成功时的平均查找长度。
6. 填空：
（1） 对二叉排序树进行_____序遍历，可以得到一个关键字的有序序列。
（2） 常用的构造哈希函数的方法有：_______，数字分析法________折叠法_______
和随机数法。
（3） 常用的处理冲突的方法有________，再哈希法,__________和，建立一个公共溢
出区。
7. 已知一组关键字为（100.90.120.60.78.35.42.31.15）哈希函数H（key）＝key mod 11，
分别使用线性搜测再散列＆链地址法处理冲突，哈希表表长m＝13 （1） 分别画出构造好的两个哈希表
（2） 分别求出等概率下查找成功时的平均查找长度。 答案 1.
2. int Search _Seq (SSTable ST,Key Tpye ke)
{
ST.elem[0].key=key;
for(i=ST.length;!EQ(ST.elem[i].key,key);--i); return i; }
3. int Search.Bin (SSTable,KeyType key)
{
low=1;high=ST.length; while(low<=high) {
mid=(low+high)/2;
if(EQ(key,ST.elem[mid].key)) return mid;
else if (LT (key,ST.elem[mid].key)) high=mid-1; else low=mid+1; }
return 0; }
4. int Search.Bin (SSTable,KeyType key)
{
low=1;high=ST.length; while(low<=high) {
mid=(low+high)/2;
if(EQ(key,ST.elem[mid].key)) return mid;
else if (LT (key,ST.elem[mid].key)) high=mid-1; else low=mid+1; }
return 0; }
5.
6. （1）中
（2）直接定址法，平方取中法，除留余数法
（3）开放定址法链地址法
7. （1）采用线性探测再散列处理冲突构造的哈希表为
0 1 2 3 4 5 6 7 8 9 10 11 12 100 90 78 35 60 15 42 120 31 ASL＝1/9(5×1+4×3)=17/9
（2）采用链地址法处理 冲突所得的哈希表为。
0 ∧ 78 100 90 ∧ ∧ 1 2 3 4 5 6 7 8 9 10
∧ 35 15 60 ∧ ∧ ∧ ∧ ∧ 31 120 ∧ 42 ∧ ASL＝1/9（6×1＋3×2）＝4/3
第十章作业
1. 待排记录关键字序列为（87，63，21，33，45，95，120，10）手工执行一下各排序方
法，分别写出第一趟排序结构时为关键字状态。 （1） 直接插入排序
（2） 希尔排序（增量d[1]=4）
（3） 快速排序（以第一记录为枢轴记录）
（4） 堆排序（堆顶元素为最小值）――会选择大顶堆还是小顶堆 （5） 2路归并排序 （6） 简单选择排序
2. 在直接插入排序，希尔排序，简单选择排序，堆排序，快速排序，起泡排序，2路归并
排序等排序方法中，哪些是简单的排序方法？哪些是先进的排序方法？（0（nlogn）） 3. 编写直接插入排序的完整算法。 4. 编写一趟快速排序的算法。 5. 编写简单选择排序的完整算法。
答案： 1.
（1）（63，87，21，33，45，95，120，10） （2）（45，63，21，10，87，95，120，33） （3）（10，63，21，33，45，87，120，95） （4）（10，33，21，63，45，95，120，87） （5）（63，87，21，33，45，95，10，120） （6）（10，63，21，33，45，95，120，87）
2. 不稳定：希尔排序，堆排序，快速排序。其余的为稳定的排序方法。
简单排序；直接插入排序，简单选择排序，起泡排序 先进的排序：堆排序，快速排序，归并排序。 3. void InsertSort (Sqlist &L)
{
For (i=2;i<=L.length;++i) If (LT(L.r[i].key,L.r[i-1].key)) {
L.r[0]=L.r[i]; L.r[i]=L.r[i-1];
For (j=i-2;LT(L.r[0].key,L.r[j].key));--j) L.r[j+1]=L.r[j]; L.r[j+1]=l.r[0]; } } 4.
int Partition (Sqlist &l,int low,int high) {
L.r[0]=L.r[low];
pivotkey=L.r[low].key; while (low while (low while (low L.r[low]=L.r[0]; return low; } 5. int Partition (Sqlist &l,int low,int high) { L.r[0]=L.r[low]; pivotkey=L.r[low].key; while (low while (low while (low L.r[low]=L.r[0]; return low; } 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构作业题(4)在线全文阅读。
相关推荐：