数据结构习题-8查找

第8章查找自测卷答案姓名班级A题号一二三四五总分题分1027162423100得分一、填空题（每空1分，共10分）1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7。解：显然，平均查找长度＝O（log2n）5次（25）。但具体是多少次，则不应当按照公式)1(log12nnnASL来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。6.散列法存储的基本思想是由关键字的值决定数据的存储地址。7.有一个表长为m的散列表，初始状态为空，现将n（nm）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素查找次数≤n-1)二、单项选择题（每小题1分，共27分）（B）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝n＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）2．【计研题2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）3．【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A．3B．4C．5D．6（A）4.链表适用于查找A．顺序B．二分法C．顺序，也能二分法D．随机（C）5.折半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量级都是O（log2n）6．【91程P3】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为D，最大比较次数为E。供选择的答案：A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储④既可以以顺序方式，也可以以链表方式存储⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④7.（96初程P73）从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种A，它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法，其中C是一种只适合于顺序存储结构但E的方法；而D是一种对顺序和链式存储结构均适用的方法。供选择的答案：A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针C：①顺序查找②循环查找③条件查找④二分法查找D：①顺序查找②随机查找③二分法查找④分块查找E：①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找答案：A＝④B＝②C＝④D＝①E＝③8.【97程P18】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在二叉排序树中，每个结点的关键码值A，B一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是C。供选择的答案A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大③比左右子树的所有结点的关键码值都大④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B:①前序遍历②中序（对称）遍历③后序遍历④层次遍历C：①除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的③每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边答案：A＝①B＝②C＝②9.【92程P6】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。散列法存储的基本思想是根据A来决定B，碰撞（冲突）指的是C，处理碰撞的两类主要方法是D。供选择的答案A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法③除余法和折叠法④拉链法和开地址法答案：A＝④B＝①C＝③D＝④10.【91程P4】考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。现把9个数1，2，3，…，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是A，n2的值是B，n9的值是C。现欲把10放入此树并使该树保持前述性质，增加的一个结点可以放在D或E。供选择的答案A～C：①1②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面③n9下面④n6下面⑤n1与n2之间⑥n2与n4之间⑦n6与n9之间⑧n3与n6之间答案：A＝⑦B＝④C＝⑥D＝②E＝⑥三、简答题（每小题4分，共16分）1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。2.【计研题1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树；（2）若查找元素54，需依次与哪些元素比较？（3）若查找元素90，需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。解：（1）先画出判定树如下（注：mid=(1+12)/2=6）：30563374287424547295(2)查找元素54，需依次与30,63,42,54等元素比较；(3)查找元素90，需依次与30,63,87,95,72等元素比较；（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.083.【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。4.【计研题1999】设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字63，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55四、分析题（每小题6分，共24分）1.【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：判定树应当描述每次查找的位置：528136947102.【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。答：1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，213.【严题集9.9③】已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：ASL＝1/10（1＋2×2＋3×4＋4×3）＝1/10（1＋4＋12＋12）＝29/10=2.9地址值链接指针022116624133084,74305536467018319104.选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。解：由题意知，m=11(刚好为素数)则(22*3)%11=6……0(41*3)%11=11……2(53*3)%11=14……5(08*3)%11=2……2(46*3)%11=12……6(30*3)%11=8……2(01*3)%11=0……3(31*3)%11=8……5(66*3)%11=9……02266418305346131012345678910134，71.在数据的存放无规律而言的线性表中进行检索的最芜橡焚储瓷阿磺吏溶涤狮砌坪元斯酿饥循汽叙白藏异蒲参划颐泪丑乎耍斤辕