资源描述：
《数据结构应用题new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、应用题1.已知关键字序列为：（74,33,52,41,13,88,66,59）哈希表长为9，哈希函数为：H(k)＝k%9，解决冲突用线性补偿探测法（取Q=5），试构造哈希表，并求出等概率下查找成功的平均查找长度。【答案】（1）哈希表:012345678597488134133526621211112(2)ASL=（5*1+3*2）/8=11/82.已知一个AOV网如图所示。(1)试画出它的邻接链表。（顶点号递减出现在各邻接表中）(2)试写出按照拓扑排序算法得到的拓扑序列。【答案】(1)(2)v4,v6,v1,v3,v5,v23.已知线性表的存储结构为顺序
2、表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。voidf30(SeqList*L){inti,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},利用堆排序
3、的方法对其排序。（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.请用克鲁斯卡尔算法构造下图所示网络的最小生成树。【答案】最小生成树如下图所示：万维试题库系统第10页6.给出一组关键字K={14,28,17,9,7,21,13,4
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)归并排序：[11，28][9，17][7，21][4，13][11]7.假设一棵二叉树的先根遍历序列为ABCDEFGHI，中根遍历序列为ADCEBFHIG。(1)画出该
5、二叉树；（2）写出后根遍历序列。【答案】（1）二叉树：（2）后根遍历序列：DECIHGFBA8.已知关键字序列为：（93,42,79,131,12,102,27），哈希表长为9，哈希函数为：H(k)＝k%9，解决冲突用线性探测再散列法，试构造哈希表，并求出等概率下查找成功的平均查找长度。【答案】(1)哈希表:0123456782793121314279102(2)ASL=（5*1+1*2+1*6）/7=13/79.设网络如图所示，试用普里姆算法按照并入最小生成树中边的次序填写下表(从顶点A开始)，并画出对应的最小生成树。12345始点终点权值【答案】1234
6、5始点ARCCE终点RCDEF权值2223110.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。【答案】万维试题库系统第10页（1）ASL=(1+2*2+3*3+3*4)/9=26/9（2）811.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，
7、84，99），写出在该序列中二分查找37时所需进行的比较次数。【答案】（1）如图所示.（2）4次12.已知二叉树如右图所示。（1）画出该二叉树的二叉链表；（2）分别写出该二叉树的先根、中根和后根遍历序列。【答案】(1)（2）先根遍历序列：ABDCEGF中根遍历序列:DBAEGCF后根遍历序列:DBGEFCA13.已知关键字序列为：（70,31,52,41,88,12,27,66）哈希表长为9，哈希函数为：H(k)＝k%9，解决冲突用线性探测再散列法，试构造哈希表，并求等概率下查找成功的平均查找长度。【答案】(1)哈希表:0123456788827123141
8、667052(2)ASL=（4*1+2*2+1*3+
