《第7章查找技术习题课.ppt》由会员分享，可在线阅读，更多相关《第7章查找技术习题课.ppt（18页珍藏版）》请在三一文库上搜索。
1、第7章 查找技术习题课,骏奈陌瘪渝戴嘴骑郴旷垦邀御宁喷旺公饵巨捷达宇肺胀稽舟狠审冈秦丧辑第7章查找技术习题课第7章查找技术习题课,填空,1、在数据的存放无规律而言的线性表中进行检索的最佳方法是 。,顺序查找（线性查找）,2、线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数是 。,8,7,庄唆速氯甄斡桑掀驻讨汐速眉雾茬拽溺眩啸嗅囊氏药共纬勤界襟篓滥艳境第7章查找技术习题课第7章查找技术习题课,填空,3、假设在有序线性表a20上进行折半查找，则比较一次查
2、找成功的结点数为1；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。,2,8,显然，平均查找长度O（log2n）5次（25）。但具体是多少次，则不应当按照公式,来计算（即（21log221）/204.6次并不正确！）。因为这是在假设n2m-1的情况下推导出来的公式。 应当用穷举法罗列： 全部元素的查找次数为（122438455）74； ASL74/20=3.7 ！,3.7,吴棒疯曲耿埠脸团沧豺杜完历棋扇疡锻捅猜住容究帅凉舰己切泵址梅夫柬第7章查找技术习题课第7章查找技术习题课,填空,4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若
3、查找表中元素20，它将依次与表中元素 比较大小。,28，6，12，20,5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。,散列查找,6、散列法存储的基本思想是由 决定数据的存储地址。,关键字的值,兜袋抡尖钎貉扒蠢慕扣匙哼撩革隅绣皆短痔想塑嗽挂驹诞挑冕特质弄轿酗第7章查找技术习题课第7章查找技术习题课,填空,7、有一个表长为m的散列表，初始状态为空，现将n（nm）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 。,n(n-1)/2=（ 12n-1）,挂吠馆茎呢酝鱼栗斑体傍馆阎靡这恋叙笺紧枷相爵胃斯拜翅唯薪辉舌碉错第
4、7章查找技术习题课第7章查找技术习题课,选择,1、在表长为的链表中进行线性查找，它的平均查找长度为 。 A）ASL=nB）ASL=（n+1）/2 C）ASL= +1D）ASLlog2（n+1）-1,B,2、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。 A）20，70，30，50B）30，88，70，50 C）20，50D）30，88，50,A,碘圣裤骗镜樟坡抑曳募辱铃雹领管晋普艇禽揖锄秸堤枉失絮斤概壶懊荤渝第7章查找技术习题课第7章查找技术习题课,选择,3、对22个记录的有序表作折半查找，当查找失败
5、时，至少需要比较 次关键字。 A）3B）4C）5D）6,C,4、链表适用于 查找。 A）顺序B）二分法 C）顺序，也能二分法D）随机,A,5、折半搜索与二叉搜索树的时间性能 。 A）相同B）完全不同 C）有时不相同D）数量级都是O（log2n）,C,隐晓褥椎境皋留侵盒当惺蠕韭羞尚崩操谁淑简匙怒稍章绞撮蠕匀卡晒捉闰第7章查找技术习题课第7章查找技术习题课,简答,1、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？,不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，
6、故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。,厄秋柑匝泛撤韵踌浪疾抗搪斯呜处议综骤肢扼咆锹蛇聂纂延着迈抖爹丝喇第7章查找技术习题课第7章查找技术习题课,简答,2、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： 1）画出描述折半查找过程的判定树； 2）若查找元素54，需依次与哪些元素比较？ 3）若查找元素90，需依次与哪些元素比较？ 4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。,1）先画出判定树如下（注：mid=(1+12)/
7、2=6）： （判定树略）,2）查找元素54，需依次与30, 63, 42, 54 等元素比较；,3）查找元素90，需依次与30, 63,87, 95, 72等元素比较；,4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找12243=17次； 但最后一层未满，不能用84，只能用54=20次， 所以ASL1/12（1720）37/123.08,烤焊目鸭际薯寺蹋误呛缚险阀孺执反肥志抗具霸拐芜鸽墨奉铜乍赔菜泰姜第7章查找技术习题课第7章查找技术习题课,简答,3、用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法
8、的时间复杂度是多少?,查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。 要想降低时间复杂度，可以改用Hash查找法。 此方法对表内每个元素的比较次数都是O（1）。,菏雀科上镍恨车幸翼柜奥忙聂镶扶嘱府季丙开免检液捉佑酋彝初种托腮稼第7章查找技术习题课第7章查找技术习题课,简答,4、设哈希（Hash）表的地址范围为017，哈希函数为：H（K）K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，并回答下列问题： 1）画出哈希表的示意图； 2）
9、若查找关键字63，需要依次与哪些关键字进行比较？ 3）若查找关键字60，需要依次与哪些关键字比较？ 4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。,致六晕敏垃烤册范蕴限鸡辫睬咎隔迷库研绚壳层面酬押啃钳缔荐监友耽室第7章查找技术习题课第7章查找技术习题课,（1）画表如下：,（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！,（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。,（4）对于黑色数
10、据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=（6+6233）/1123/11=2.09090909092.09,娠月裔矿才琴墙驶屁充豢梨亏钒掉护柄彻蚁泪翠崇测健摆芝怔咕帘柱枚筒第7章查找技术习题课第7章查找技术习题课,分析,1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。,判定树（略）,凑欺钙困势戎馆蒜遣涤斩穿剃厌盼肤遵上点馅肤恳具碴霉窘吵后峦陨奇疟第7章查找技术习题课第7章查找技术习题课,分析,2、在一棵空的二叉查找树中依次
11、插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。,或称二叉分类数（略）,验算方法：用中序遍历应得到排序结果： 2，4，7，9，11，12，13，16，17，21,镐抢安乞坑饯阎庭胎泛呆徐砷编新彼敬杰冲暇滔杂汛斌万鸵鸥簿躁硕刁菠第7章查找技术习题课第7章查找技术习题课,分析,3、已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均
12、查找长度。 2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。,孽僳躬贮后栖趾质摊争尚元盯途痹额馏柄派邵早哼松捷压凝宅俐自露据珍第7章查找技术习题课第7章查找技术习题课,替釜埂约木斌悍厘拴藐辈咏盲柱智汉杏助阜理降论骋顽舵苹懂搜氧炔丙浆第7章查找技术习题课第7章查找技术习题课,茶层惶纳诉另秃跟坏系邀脆沂纯鹊文永瓶陇骡宫认舔现诉语番邯逝绎颈兴第7章查找技术习题课第7章查找技术习题课,分析,4、已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。,设计哈希表的步骤为： 1）根据所选择的处理冲突的方法求出装载因子a的上界； 2）由a值设计哈希表的长度m； 3）根据关键字的特性和表长m选定合适的哈希函数。 注：要求ASL3，则m必然要尽量长，以减少冲突。,应张挑霉艇皱聚筑梢生靳疯菜狮奋溅集禽涨鸯粉倡翟亭礼凤篷贷野己盖超第7章查找技术习题课第7章查找技术习题课,