万维试题库系统 第 1 页 一、应用题 1
已知关键字序列为：（74,33,52,41,13,88,66,59）哈希表长为9，哈希函数为：H (k)＝k %9，解决冲突用线性补偿探测法 （取Q=5），试构造哈希表，并求出等概率下查找成功的平均查找长度
【答案】 （1）哈希表: 0 1 2 3 4 5 6 7 8 59 74 88 13 41 33 52 66 2 1 2 1 1 1 1 2 (2) ASL=（5*1+3*2）/8=11/8 2
已知一个AOV网如图所示
(1)试画出它的邻接链表
（顶点号递减出现在各邻接表中） (2)试写出按照拓扑排序算法得到的拓扑序列
V 6 V 1 V 2 V 4 V 5 V 3 【答案】 (1) 1 v1 0 6 v6 1 5 v5 3 3 V3 2 4 v4 0 2 v2 2 ∧ 6 5 3 ∧ 5 ∧ 5 ∧ 2 ∧ 3 2 ∧ (2)v4,v6,v1,v3,v5,v2 3
已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： （1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态； （2）简述算法f30的功能
void f30 (SeqList *L) { int i,j; for (i=j=0;ilength; i++) if(L->data[i]>=0){ if(i
=j)L->data[j]=L->data[i]; j++； } L->length=j; } 【答案】 （1）L=(21,19,0,34,30) (2) 删除顺序表中小于0的数
已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序
（1）写出在构成初始堆后关键字的排列情况
（2）写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情
