万维试题库系统 第 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的数。 4. 已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序。 （1）写出在构成初始堆后关键字的排列情况。 （2）写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情况。 【答案】 （1）初始堆：{12,26,22,34,63,41,47,59} （2）输出12后：{22，26，41，34，63，59，47} 输出22后：{26，34，41，47，63，59} 输出26后：{34，47，41，59，63} 输出34后：{41，47，63，59} 5. 请用克鲁斯卡尔算法构造下图所示网络的最小生成树。 14 v1 v4 v5 v2 v3 V6 10 8 18 22 12 10 16 19 20 【答案】 最小生成树如下图所示： 万维试题库系统 第 2 页 14 v1 v4 v5 v2 v3 V6 8 18 12 10 6. 给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序(2)希尔排序(d1=4) (3)归并排序 【答案】 给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序：{11,4,13,9,7}14{21,17,28} (2) 希尔排序(d1=4) ： {7,21,13,4,11,28,17,9,14} (3)归并排...
VIP
