东北大学：《数据结构》课程教学资源（学习资料）第8章查找自测卷答案.doc_大学文库

第8章查找自测卷答案姓名班级四总分题分 10 27 16 24 100 填空题(每空1分,共10分) 1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找) 2.线性有序表(a,a,as,…,a5o是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索8次。设有100个结点,用二分法查找时,最大比较次数是7 3.假设在有序线性表a20上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为2;比较四次查找成功的结点数为8;平均查找长度为3.7。解:显然,平均查找长度=o(log2n)<5次(25)但具体是多少次,则不应当按照公式 S-n+1g2(m+)来计算(即(21×log21)/20=46次并不正确!因为这是在假设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(n<m)个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同,则探测的总次数是n(n-12=(1+2+ n-1)。(而任一元素查找次数≤n-1) 、单项选择题(每小题1分,共27分) (B)1.在表长为n的链表中进行线性查找,它的平均查找长度为 aSL=n B. A S (n+1)/2; C.ASL=√n+1;D.ASL≈1og,(n+1 A)2.【计研题2001】折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中比较大小,查找结果是失败 1.20,70,30,50 B.30,88,70,50 D.30,88,50 (C)3.【计研题2001】对22个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字

1 第 8 章查找自测卷答案姓名班级 A 题号一二三四五总分题分 10 27 16 24 23 100 得分一、填空题（每空 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）。但具体是多少次，则不应当按照公式 log ( 1) 1 2 + + = n n n ASL 来计算（即（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（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这 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，50 B．30，88，70，50 C．20，50 D．30，88，50 （ C ）3．【计研题 2001】对 22 个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。 A．3 B．4 C．5 D． 6

(A)4.链表适用于查找顺序 B.二分法C.顺序,也能二分法D.随机 (C)5.折半搜索与二叉搜索树的时间性能 A.相同 B.完全不同 C.有时不相同 D.数量级都是O(ogn) 6.【9程P3】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内要进行线性查找,则线性表A;要进行二分查找,则线性表B;要进行散列查找,则线性表某顺序存储的表格,其中有900个元素,已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的,并且各个元素的关键项的值皆不相同。当用顺序查找法查找时,平均比较次数约为 D,最大比较次数为E。供选择的答案: AC:①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储 ④既可以以顺序方式,也可以以链表方式存储 ⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好 ①25000 ③45000 ④9000 答案: 7.(%6初程P73)从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在谷卷的对应栏内数据结构反映了数据元素之间的结构关系。链表是一种它对于数据元素的插入和删除通常查找线性表数据元素的方法有和D两种方法,其中C是一种只适合于顺序存储结构但E的方法;而D是一种对顺序和链式存储结构均适用的方法。供选择的答案 A:①顺序存储线性表②非顺序存储非线性表⑧顺序存储非线性表④非顺序存储线性表 B:①不需要移动结点,不需改变结点指针②不需要移动结点,只需改变结点指针只需移动结点,不需改变结点指针 ④既需移动结点,又需改变结点指针 C:①顺序查找②循环查找 ③条件查找 ④二分法查找 D:①顺序查找②随机查找 ③二分法查找④分块查找 E:①效率较低的线性查找 ②效率较低的非线性查找 ③效率较高的非线性查找④效率较高的线性查找谷案:A=④ D=①E=_③ 8.【叨7程P18】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。在二叉排序树中,每个结点的关键码值 B一棵二叉排序,即可得到排序序列。同一个结点集合,可用不同的二叉排序树表示,人们把平均检索长度最短的二叉排序树称作最佳二叉排序,最佳二叉排序树在结构上的特点是C 供选择的答案 A:①比左子树所有结点的关键码值大,比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小,比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

2 （ 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： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

3 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 ⑨ 9 D～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): 95 (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.08 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时间复杂度更小,你采用什么方法?此方法的时间复杂度是多少? 答:查找某个元素的时间复杂度下限,如果理解为最短查找时间,则当关键字值与表头元素相同时,比较 1次即可。要想降低时间复杂度,可以改用Hash查找法。此方法对表内每个元素的比较次数都是0(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)画表如下: 01234567891011|121314151617 32176349 244010 30314647

4 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）： 30 5 63 3 7 42 87 4 24 54 72 95 (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.08 3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较 1 次即可。要想降低时间复杂度，可以改用 Hash 查找法。此方法对表内每个元素的比较次数都是 O（1）。 4. 【计研题 1999】设哈希（Hash）表的地址范围为 0～17，哈希函数为：H（K）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出 Hash 表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字 63，需要依次与哪些关键字进行比较？（3）若查找关键字 60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（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

(083%l1=2……2 (463)%ll=12……6 01*3)%ll=0…3 31*3)%11=8…5 (66*3)%ll=9…0 2264830546「3n工 4,7 五、算法设计题(4中选3,第1题7分必选,其余每题8分,共23分) 1.已知1个元素的有序表为(0513192137566475808892),请写出折半查找的算法程序,查找关键字为key的数据元素(建议上机调试) 解:折半查找的C程序有很多参考资料,注意此题要求是整型量。折半查找的一个递归算法如下,形式非常简洁1 nt search bin recursive( SSTable st, int key, int low, int high)∥折半查找的递归算法 if( low>high) return0,∥查找不到时返回0 mid=(low+high)/2 if(ST elem mid]. key==key) return mid else if(STelem(mid). key>key) eturn Search Bin Recursive(ST, key, low, mid-1); else return Search Bin Recursive(ST, key, mid+1, high) i//Search Bin Recursive 2.【严题集93④】试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。解:注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别:“若一棵非空的二叉树其左、右子树均为二叉排序树,且左子树的根的值小于根结点的值,又根结点的值不大于右子树的根的值则是二叉排序树 (刘注:即不能只判断左右孩子的情况,还要判断左右孩子与双亲甚至根结点的比值也要遵循(左小右大) 原则)。若要采用递归算法,建议您采用如下的函数首部: bool BisortTree( BiTree t, BiTree&PRE),其中PRE为指向当前访问结点的前驱的指针。 (或者直接存储前驱的数值,随时与当前根结点比较) 个漂亮的算法设计如下 ∥last是全局变量,用来记录前驱结点值,只要每个结点都比前驱大就行。 int Is Bs Tree( Bitree T) ∥判断二叉树T是否二叉排序树,是则返回1,否则返回0 if(T->lchild&&flag) Is BSTree(T->lchild) if(l>data<las)fag=0,∥与其中序前驱相比较,nag=0表示当前结点比直接前驱小,则立即返回

7 (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 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4，7 五、算法设计题（4 中选 3，第 1 题 7 分必选，其余每题 8 分，共 23 分） 1. 已知 11 个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算法程序，查找关键字为 key 的数据元素 (建议上机调试)。解：折半查找的 C 程序有很多参考资料，注意此题要求是整型量。折半查找的一个递归算法如下，形式非常简洁！ int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 { if(low>high) return 0; //查找不到时返回 0 mid=(low+high)/2; if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); } }//Search_Bin_Recursive 2. 【严题集 9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。若要采用递归算法，建议您采用如下的函数首部： bool BisortTree(BiTree T, BiTree&PRE)，其中 PRE 为指向当前访问结点的前驱的指针。（或者直接存储前驱的数值，随时与当前根结点比较）一个漂亮的算法设计如下： int last=0, flag=1; // last 是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树 T 是否二叉排序树，是则返回 1，否则返回 0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data<last) flag=0; //与其中序前驱相比较, flag=0 表示当前结点比直接前驱小，则立即返回

东北大学：《数据结构》课程教学资源（学习资料）第8章 查找自测卷答案

东北大学：《数据结构》课程教学资源（学习资料）第8章查找自测卷答案