搜索
数据结构习题(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．索引顺序表查找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.数据分成若干块，每块（除最后一块外）中数据个数需相同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)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（C）。A．2B.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)对序列{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,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中，p值最好取___质数_______。3.分析题22)假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树；（2）若查找元素54，需依次与哪些元素比较？（3）若查找元素90，需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。1）305633742874245472952）（30634254）3）（30638795）4）ASL=1/12*(1+2*2+3*4+4*5)=323)二叉查找树的数据输入序列为{65,40,27,12,81,54,29,33}。回答以下问题,(1)画出该序列对应的二叉查找树，并标示平衡因子。(2)通过旋转算法，画出该二叉查找树对应的平衡二叉树，并计算平衡后的平均查找长度ASL.1)65408127541229330000-1-1+2+32)4027651229548133ASL=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和线性探测再散列处理冲突的方法在地址空间A[0..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=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)已知输入数据序列为{20,33,-7,11,82,40,8,52,16}，试回答以下问题。(1)将该输入序列调整为大顶堆。并画出该大顶堆对应的完全二叉树。(2)写出第二趟堆排序后的数据序列。1)2033-711825216408调整后的大顶堆为82524020331116-782)第一趟堆排序的结果为52334020161182-78对应序列(52,33,40,20,16,-7,8,11,82)第二趟堆排序的结果为40331120165282-78对应序列(40,33,11,20,16,-7,8,52,82)4.程序设计题26)写出希尔排序的算法程序27)写出快速排序的算法程序