数据结构习题五(答案)

1、数据结构习题(5)学号姓名课堂号()1 .选择题1)对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A.(N+1)/2B.N/2C.ND.(1+N)*N/22 )下面关于二分查找的叙述正确的是(D)A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储3)折半查找的时间复杂性为(D)A.O(n2)B.O(n)C.O(nlog(n)D.O(log(n)4)概率不同的有序表，最适合的查找算法是(C)A.顺序查找B.折半查找C.静态树表查找D.索引顺序

2、表查找5) 平均查找长度最短的查找方法是C。A.折半查找B.顺序查找C.哈希查找4.其他6) 折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中A比较大小，查找结果是失败。A.20,70,30,50B,30,88,70,50C.20,50D,30,88,507)当采用分快查找时，数据的组织方式为(B)A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外

3、)中数据个数需相同8)分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,80,60,90,120,130,110)9)设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,79,用链地址法构造散列表，散列函数为H(key)=keyMOD13,散列地址为1的链中有(D)个记录。A.1B.2C.3D.410)散列表的地址区间为0-17,散列函数为H(K)=Kmod1

4、7。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。(1)元素59存放在散列表中的地址是(D)。A.8B.9C.10D.11(2)存放元素59需要搜索的次数是(C)。B.3C.4D.511）下面给出的四种排序法中（C）排序法是不稳定性排序法。A.简单插入排序B.冒泡排序C.希尔排序D.快速排序12）对一组数据（84,47,25,15,21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是（A）。A.选择B.冒泡C.快速D.插入13）对序

5、列15,9,7,8,20,-1,4进行排序，进行一趟后数据的排列变为4,9,-1,8,20,7,15;则采用的是（C）排序。A.选择B.快速C.希尔D.冒泡14）有一组数据（15,9,7,8,20,-1,7,4）用快速排序的划分方法进行一趟划分后数据的排序为（A）（按递增序）。A.下面的B,C,D都不对。B.9,7,8,4,-1,7,15,20C.20,15,8,9,7,-1,4,7D.9,4,7,8,7,-1,15,2015）下列四个序列中，哪一个是堆（C）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,

6、25,20,10D.75,45,65,10,25,30,20,152.填空题16）在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键字20,需做的关键字比较次数为4次.17）查找表分为哪两种：静态查找表和动态查找表。18） 一棵m阶B-树，每个结点包含的键值最多为m-1一个。19）排序算法一般分为插入排序，交换排序，选择排序，归并排序和基数排序。其中希尔排序属于插入排序，堆排序属于选择排序。20）有一组数据（15,9,7,8,20,-1,7,4）,该序列第二趟快速排序序列为-1（4）78791520。21）在哈希函数H（key）=key%p中

7、，p值最女?取质数。3.分析题22）假定对有序表：（3,4,5,7,24,30,42,54,63,72,87,95）进行折半查找，试回答下列问题：(2) 若查找元素54,需依次与哪些元素比较？(3) 若查找元素90,需依次与哪些元素比较？(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。3)(30638795)4)ASL=1/12*(1+2*2+3*4+4*5)=323)二叉查找树的数据输入序列为65,40,27,12,81,54,29,33。回答以下问题，(1)画出该序列对应的二叉查找树，并标示平衡因子。(2)通过旋转算法，画出该二叉查找树对应的平衡二叉树，并计算平衡后的平均查

8、找长度ASL.1)2)2740651229548133ASL=1/8*(1+2*2+4*3+1*4)=2.62524)已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79)按哈希函数H(Key)=KeyMOD13和线性探测再散列处理冲突的方法在地址空间A0.15中构造哈希表，并计算等概率条件下的平均查找长度。012345678910111213141401682755192084792311101214311391131)H(19)=19%13=62)H(14)=14%13=13)H(23)=23%13=104)H(01)=1%13=1冲突；(1+1)%13

9、=2;5)H(68)=68%13=36)H(20)=20%13=77)H(84)=84%13=6冲突;(6+1)%13=7冲突；(6+2)%13=88)H(27)%13=1冲突;(1+1)%13=2冲突;(1+2)%13=3冲突;(1+3)%13=49)H(55)=55%13=3冲突;(3+1)%13=4冲突;(3+2)%13=510)H(11)=11%13=1111)H(10)=10%13=10冲突；(10+1)%13=11冲突;(10+2)%13=1212)H(79)=79%13=1冲突.冲突8次ASL=1/12(1*6+2*1+3*3+4*1+9*1)=2.7525)已知输入数据序列为2

10、0,33,-7,11,82,40,8,52,16,试回答以下问题。(1)将该输入序列调整为大顶堆。并画出该大顶堆对应的完全二叉树。(2)写出第二趟堆排序后的数据序列。调整后的大顶堆为2)第一趟堆排序的结果为对应序列(52,33,40,20,16,-7,8,11,82)第二趟堆排序的结果为对应序列(40,33,11,20,16,-7,8,52,82)4.程序设计题26)写出希尔排序的算法程序27）写出快速排序的算法程序Whenyouareoldandgreyandfullofsleep,Andnoddingbythefire,takedownthisbook,Andslowlyread,andd

11、reamofthesoftlookYoureyeshadonce,andoftheirshadowsdeep;Howmanylovedyourmomentsofgladgrace,Andlovedyourbeautywithlovefalseortrue,Butonemanlovedthepilgrimsoulinyou,Andlovedthesorrowsofyourchangingface;Andbendingdownbesidetheglowingbars,Murmur,alittlesadly,howlovefledAndpaceduponthemountainsoverheadAnd

12、hidhisfaceamidacrowdofstars.ThefurthestdistanceintheworldIsnotbetweenlifeanddeathButwhenIstandinfrontofyouYetyoudon'tknowthatIloveyou.ThefurthestdistanceintheworldIsnotwhenIstandinfrontofyouYetyoucan'tseemyloveButwhenundoubtedlyknowingthelovefrombothYetcannotbetogether.ThefurthestdistanceintheworldIsnotbeingapartwhilebeinginloveButwhenIplainlycannot