《数据结构第9章答案》由会员分享，可在线阅读，更多相关《数据结构第9章答案（8页珍藏版）》请在金锄头文库上搜索。
1、第9章 查找参考答案 一、填空题（每空1分，共10分）1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。2. 线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。3. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 。解：显然，平均查找长度O（log2n）5次（25）。但具体是多少次，则不应当按照公式来
2、计算（即（21log221）/204.6次并不正确！）。因为这是在假设n2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为（122438455）74； ASL74/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）个不同的关键码插入到散列表中，解
3、决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 12n-1） 。(而任一元素查找次数 n-1)二、单项选择题（每小题1分，共27分）（ B ）1在表长为的链表中进行线性查找，它的平均查找长度为. ; . （）; . ; . （）（ A ）2【计研题2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）3【计研题2001】对22个记录的有序表作折半查找，当
4、查找失败时，至少需要比较 次关键字。A3 B4 C5 D 6（ A ）4. 链表适用于 查找A顺序 B二分法 C顺序，也能二分法 D随机（ C ）5. 折半搜索与二叉搜索树的时间性能 A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）6【91程P3】从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值
5、皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。供选择的答案：AC： 必须以顺序方式存储 必须以链表方式存储 必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E： 25000 30000 45000 90000答案： A= B= C= D E 7. （96初程P73）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B
6、 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：A：顺序存储线性表 非顺序存储非线性表顺序存储非线性表 非顺序存储线性表B： 不需要移动结点，不需改变结点指针 不需要移动结点，只需改变结点指针 只需移动结点，不需改变结点指针 既需移动结点，又需改变结点指针C： 顺序查找 循环查找 条件查找二分法查找D： 顺序查找 随机查找 二分法查找分块查找E： 效率较低的线性查找 效率较低的非线性查找 效率较高的非线性查找效率较高的线性查找答案：A B C D E 8. 【97程P1
7、8】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。供选择的答案A： 比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 比左右子树的所有结点的关键码值都大 与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B: 前序遍历 中序（对称）遍历 后序遍历 层次遍
8、历C： 除最下二层可以不满外，其余都是充满的 除最下一层可以不满外，其余都是充满的 每个结点的左右子树的高度之差的绝对值不大于1 最下层的叶子必须在最左边答案：A B C 9. 【92程 P6】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。供选择的答案A，B： 存储地址 元素的符号 元素个数 关键码值 非码属性 平均检索长度 负载因子 散列表空间 C: 两个元素具有相同序号 两个元素的关键码值不同，而非码属性相同 不同关键码值对应到相同的存储地址
9、 负载因子过大 数据元素过多D： 线性探查法和双散列函数法 建溢出区法和不建溢出区法 除余法和折叠法 拉链法和开地址法答案：A B C D 10.【91程P4】考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。现把9个数1，2，3，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。供选择的答案AC： 1 2 3 4 5 6 7 8 9DE： n7下面 n8下面 n9下面 n6下面 n
10、1与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
11、，87，95）进行折半查找，试回答下列问题：（1） 画出描述折半查找过程的判定树；（2） 若查找元素54，需依次与哪些元素比较？（3） 若查找元素90，需依次与哪些元素比较？（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。解：（1） 先画出判定树如下（注：mid=(1+12)/2=6）：305 633 7 42 87 4 24 54 72 95(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；(3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找12243=17次；
12、但最后一层未满，不能用84，只能用54=20次，所以ASL1/12（1720）37/123. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。4. 【计研题1999】设哈希（Hash）表的地址范围为017，哈希函数为：H（K）K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1） 画出哈希表的示意图；（2
