第八章 查找习题

•一、填空题•1.在数据的存放无规律而言的线性表中进行检索的最佳方法是。•一、填空题•1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。•3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为。•3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8。•5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。•6.散列法存储的基本思想是由决定数据的存储地址。•5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。•6.散列法存储的基本思想是由关键字的值决定数据的存储地址。•（）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为•Ａ.ＡＳＬ＝ｎ;•Ｂ.ＡＳＬ＝（ｎ＋１）／２;•Ｃ.ＡＳＬ＝＋１;•Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１二、单项选择题•（B）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为•Ａ.ＡＳＬ＝ｎ;•Ｂ.ＡＳＬ＝（ｎ＋１）／２;•Ｃ.ＡＳＬ＝＋１;•Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１•（）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。•A．20，70，30，50•B．30，88，70，50•C．20，50•D．30，88，50•（A）2．【计研题2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。•A．20，70，30，50•B．30，88，70，50•C．20，50•D．30，88，50•（）4.链表适用于查找•A．顺序•B．二分法•C．顺序，也能二分法•D．随机•（A）4.链表适用于查找•A．顺序•B．二分法•C．顺序，也能二分法•D．随机•6．要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。•供选择的答案：•A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储•④既可以以顺序方式，也可以以链表方式存储•⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好•⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好•答案：A=B=C=•6．要进行线性查找，则线性表A；要进•行二分查找，则线性表B；要进行散列查找，则线性表C。•供选择的答案：•A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储•④既可以以顺序方式，也可以以链表方式存储•⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好•⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好•答案：A=④B=⑤C=③•7.数据结构反映了数据元素之间的结构关系。链表•是一种A，它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法，其中C是一种只适合于顺序存储结构但E的方法；而D是一种对顺序和链式存储结构均适用的方法。•A：①顺序存储线性表②非顺序存储非线性表•③顺序存储非线性表④非顺序存储线性表•B：①不需要移动结点，不需改变结点指针•②不需要移动结点，只需改变结点指针•③只需移动结点，不需改变结点指针•④既需移动结点，又需改变结点指针•C：①顺序查找②循环查找③条件查找④二分法查找•D：①顺序查找②随机查找③二分法查找④分块查找•E：①效率较低的线性查找②效率较低的非线性查找•③效率较高的非线性查找④效率较高的线性查找•答案：A＝B＝C＝D＝•E＝•7.数据结构反映了数据元素之间的结构关系。链表•是一种A，它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法，其中C是一种只适合于顺序存储结构但E的方法；而D是一种对顺序和链式存储结构均适用的方法。•A：①顺序存储线性表②非顺序存储非线性表•③顺序存储非线性表④非顺序存储线性表•B：①不需要移动结点，不需改变结点指针•②不需要移动结点，只需改变结点指针•③只需移动结点，不需改变结点指针•④既需移动结点，又需改变结点指针•C：①顺序查找②循环查找③条件查找④二分法查找•D：①顺序查找②随机查找③二分法查找④分块查找•E：①效率较低的线性查找②效率较低的非线性查找•③效率较高的非线性查找④效率较高的线性查找•答案：A＝④B＝②C＝④•D＝①E＝③•三、简答题•1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？•1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？•答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。•二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。•4.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。•K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）•造出Hash表，试回答下列问题：•画出哈希表的示意图；•若查找关键字63，需要依次与哪些关键字进行比较？•若查找关键字60，需要依次与哪些关键字比较？•假定每个关键字的查找概率相等，求查找成功时的平均查找长度。••解：（1）画表如下：•（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•4.选取散列函数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……0