《2022年查找作业答案 .pdf》由会员分享，可在线阅读，更多相关《2022年查找作业答案 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 9 章查找1选择题（1）对 n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（） 。A(n-1)/2 B n/2 C(n+1)/2Dn （2）适用于折半查找的表的存储方式及元素排列要求为（） 。A链接方式存储，元素无序B链接方式存储，元素有序C顺序方式存储，元素无序D顺序方式 存储，元素有序（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（） 。A必定快B不一定C在大 部分情况下要 快D取决于表递增还是递减（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找表中元素58，则它将依次
2、与表中（）比较大小，查找结果是失败。A20，70，30， 50 B30，88，70，50 C 20，50 D30，88， 50 （5）对 22 个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A 3 B4 C5 D6 （6）折半搜索与二叉排序树的时间性能（） 。A相同B完全不同C有时不相同D数量级都是O(log2n) （7） 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（） 。A （100，80， 90， 60， 120， 110，130）B （100，120，110，130， 80， 60， 90）C （100，60， 80， 90， 120， 110
3、，130）D(100，80， 60， 90， 120，130，110) （8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知 A 的左孩子的平衡因子为0 右孩子的平衡因子为1，则应作（）型调整以使其平衡。A LL BLR CRL DRR （9）下列关于m 阶 B-树的说法错误的是（） 。A根结点至多有m 棵子树B所有叶子都在同一层次上C非叶结点至少有m/2 (m 为偶数 )或 m/2+1（m 为奇数）棵子树D根结点中的数据是有序的（10）下面关于B-和 B+ 树的叙述中，不正确的是（） 。AB-树和 B+ 树都是平衡的多叉树BB-树和 B+ 树都可用于文件的索引结构C
4、 B- 树和 B+树都能有效 地支持顺序检索DB-树和 B+ 树都能有效地支持随机检索（11）m 阶 B- 树是一棵（） 。Am 叉排序树Bm 叉平衡排序树C m-1 叉平衡排序树Dm+1 叉平衡排序树（12）下面关于哈希查找的说法，正确的是（） 。A哈希函数构造的越复杂越好，因为这样随机性好，冲突小名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - B除留余数法是所有哈希函数中最好的C不存在特别好与坏的哈希函数，要视情况而定D哈希
5、表的平均查找长度有时也和记录总数有关（13）下面关于哈希查找的说法，不正确的是（） 。A采用链地 址法处理冲突时，查找一个元素的时间是相同的B采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C用链地址法处理冲突，不会引起二次聚集现象D用链地址法处理冲突，适合表长不确定的情况（14）设哈希表长为14，哈希函数是H(key)=key%11 ，表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的元素加到表中，用二次探测法解决冲突，则放入的位置是（） 。A8 B3 C5 D9 （15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所
6、探测的这些位置上的关键字( )。A不一定 都是同义词B一定都是同义词C一定都不是同义词D都相同2应用题（1）假定对有序表： （3，4，5，7，24，30， 42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素54，需依次与哪些元素比较？ 若查找元素90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出判定树如下（注：mid= (1+12)/2=6）：查找元素54，需依次与30, 63, 42, 54 元素比较；查找元素90，需依次与30, 63,87, 95 元素比较；求 ASL 之前，需要统计每个
7、元素的查找次数。判定树的前3 层共查找 12243=17次；但最后一层未满，不能用84，只能用 54=20 次，所以 ASL 1/12（1720） 37/123.08 （2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21 （
8、3） 已知如下所示长度为12 的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
9、师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - （5）设哈希表的地址范围为017，哈希函数为：H（key）=key%16 。用线性探测法处理冲突，输入关键字序列：（10， 24， 32，17，31，30，46，47，40，63，49） ，构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32
10、17 63 49 24 40 10 30 31 46 47 查找 63, 首先要与 H(63)=63%16=15 号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6 次！查找 60,首先要与 H(60)=60%16=12 号单元内容比较，但因为 12 号单元为空 （应当有空标记） ，所以 应当只比较这一次即可。对于黑色数据元素，各比较1次；共 6 次；对红色元素则各不相同，要统计移位的位数。“63”需要 6 次， “49”需要 3 次， “40”需要2 次， “46”需要 3 次， “ 47”需要 3 次，所以 ASL=1/11 （6 23
11、3+6） 23/11 （6）设有一组关键字 （9，01，23，14，55，20，84，27） ，采用哈希函数： H （key）=key %7 ，表长为 10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0 1 2 3 4 5 6 7 8 9 关键字14 01 9 23 84 27 55 20 比较次数1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字 27 为例： H（27）=27%7=6 （冲突） H1=（6+1）%10=7 （冲突）H2=（6+22）%10=0
12、（冲突） H3=（6+33）%10=5 所以比较了4 次。（7）设哈希函数H（K）=3 K mod 11 ，哈希地址空间为010，对关键字序列（32，13，49，24，38， 21，4，12） ，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和 ASLunsucc。 线性探测法； 链地址法。散列地址0 1 2 3 4 5 6 7 8 9 10 关键字4 12 49 38 13 24 32 21 比较次数1 1 1 2 1 2 1 2 ASLsucc = （1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+
13、8+7+6+5+4+3+2+1）/11=40/11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - ASLsucc = （1*5+2*3 ）/8=11/8 ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11 （5）设哈希表的地址范围为017，哈希函数为：H（key）=key%16 。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） ，构造
14、哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解： （ 1）画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2） 查找 63, 首先要与 H(63)=63%16=15 号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6 次！（3）查找 60,首先要与 H(60)=60%1
15、6=12 号单元内容比较，但因为12 号单元为空（应当有空标记），所以 应当只比较这一次即可。（4） 对于黑色数据元素，各比较1 次；共 6 次；对红色元素则各不相同，要统计移位的位数。“63”需要 6 次， “49”需要 3 次， “40”需要2 次， “46”需要 3 次， “ 47”需要 3 次，所以 ASL=1/11 （6 233+6） 23/11 （6）设有一组关键字（9，01， 23，14，55， 20，84，27） ，采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0
16、1 2 3 4 5 6 7 8 9 关键字14 01 9 23 84 27 55 20 比较次数1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字 27 为例： H（27）=27%7=6 （冲突） H1=（6+1）%10=7 （冲突）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - H2=（6+22）%10=0 （冲突） H3=（6+33）%10=5 所以比较了
17、4 次。（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为010，对关键字序列（32，13，49，24，38，21，4，12） ，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和 ASLunsucc。 线性探测法； 链地址法。散列地址0 1 2 3 4 5 6 7 8 9 10 关键字4 12 49 38 13 24 32 21 比较次数1 1 1 2 1 2 1 2 ASLsucc = （1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -