数据结构习题五(答案).doc

数据结构习题(5)学号_ 姓名_ 课堂号(A：周一课堂，B：周二课堂)1. 选择题1) 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A（N+1）/2 B. N/2 C. N D. （1+N）*N /22) 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3) 折半查找的时间复杂性为（ C ） 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 比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，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）=key MOD 13,散列地址为1的链中有（ D ）个记录。A1 B. 2 C. 3 D. 410) 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ D ）。A 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ C ）。A 2 B. 3 C. 4 D. 511) 下面给出的四种排序法中( C )排序法是不稳定性排序法。 A. 简单插入排序 B. 冒泡排序 C. 希尔排序 D. 快速排序12) 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( 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都不对。 B9，7，8，4，-1，7，15，20C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，2015) 下列四个序列中，哪一个是堆（ C ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 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，7，8，7，9，15，20 。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） 折半查找判定树为（2） 查找元素54，需依次与30，63，42，54比较（3） 查找元素90，需依次与30，63，87，95比较（4） ASL=1/12*（1+2*2+4*3+5*4）=323) 二叉查找树的数据输入序列为65,40,27,12,81,54,29,33。回答以下问题,(1)画出该序列对应的二叉查找树，并标示平衡因子。(2)通过旋转算法，画出该二叉查找树对应的平衡二叉树，并计算平衡后的平均查找长度ASL.1) 该序列对应的二叉查找树，并标示平衡因子2) 旋转算法(边创建边平衡)，画出该二叉查找树对应的平衡二叉树，并计算平衡后的平均查找长度ASLASL=1/8*(1+2*2+4*3+4*1)=2.3824) 已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数 H(Key)=Key MOD 13和线性探测再散列处理冲突的方法在地址空间A0.15中构造哈希表，并计算等概率条件下的平均查找长度。0123456789101112131415140168275519208479231110121431139113H(Key)=Key MOD 13（1）. H（19）= 19%13 = 6 （2）. H（14）= 14%13 = 1（3）. H（23）= 23%13 = 10（4）. H（01）= 1%13 = 1 冲突（H（01）+1 ）% 13= 2（5）. H（68）= 68%13 = 3（6）. H（20）= 20%13 =7（7）. H（84）= 84%13 =6 冲突（H（84）+1 ）% 13= 7 冲突（H（84）+2 ）% 13= 8 （8）. H（27）= 27%13 =1 冲突（H（27）+1 ）% 13= 2冲突（H（27）+2 ）% 13= 3冲突（H（27）+3 ）% 13= 4（9）. H（55）= 55%13 =3 冲突（H（55）+1 ）% 13= 4冲突（H（55）+2 ）% 13= 5（10）. H（11）= 11%13 =11（11）. H（10）= 11%13 =10 冲突（H（10）+1 ）% 13= 11 冲突（H（10）+2 ）% 13= 12 （12）. H（79）= 79%13 =1 冲突（H（79）+1 ）% 13= 2冲突 。 （H（79）+7 ）% 13= 8冲突（H（79）+8 ）% 13= 9ASL=1/12*（6*1+1*2+3*3+1*4+1*9）=2.525) 已知输入数据序列为20,33,-7,11,82,40,8,52