第8章 查 自测卷答案
一、填空题（每空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）。但具体是多少次，则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7
4．折半查有序表（4，6，12，20，28，38，50，70，88，100），若查表中元素20，它将依次与表中元素 28，6，12，pcti20 比较大小。
5. 在各种查方法中，平均查长度与结点个数n无关的查方法是 散列查 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查次数 ≤n-1)
二、单项选择题（每小题1分，共27分）
（ B ）1．在表长为ｎ的链表中进行线性查，它的平均查长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）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
（ C ）3．对22个记录的有序表作折半查，当查失败时，至少需要比较 次关键字。
A．3 B．4 C．5 D． 6
（ A ）4. 链表适用于51.cm 查
A．顺序 B．二分法 C．顺序，也能二分法 D．随机
（ C ）5. 折半搜索与二叉搜索树的时间性能
A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）
6．从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
要进行线性查，则线性表 A ；要进行二分查，则线性表 B ；要进行散列查，则线性表 C 。
某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查法查时，平均比较次数约为 D ，最大比较次数为 E 。
供选择的答案：
A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储
④ 既可以以顺序方式，也可以以链表方式存储
⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好
⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好
D，E： ① 25000 ② 30000 ③ 45000 ④ 90000
答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④
7.从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。
供选择的答案：
A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表
B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针
③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针
C：① 顺序查 ②循环查 ③条件查 ④二分法查
D：① 顺序查 ②随机查 ③二分法查 ④分块查
E：① 效率较低的线性查 ②效率较低的非线性查
③ 效率较高的非线性查 ④效率较高的线性查
答案：A＝ ④ B＝ ② C＝ ④ D＝ ① E＝ ③
8. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。
供选择的答案
A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大
③比左右子树的所有结点的关键码值都大
④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系
B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历
C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的
③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边
答案：A＝ ① B＝ ② C＝ ②
9. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
散列法存储的基本思想是根据 A 数模转换 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。
供选择的答案
A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值
⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间
C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同
③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多
D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法
③ 除余法和折叠法 ④ 拉链法和开地址法
答案：A＝ ④ B＝ ① C＝ ③ D＝ ④
10.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。
现把9个数1，2，3，…，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把发电机集电环放入此树并使该树保持前述性质，增加的一个结点可以放在 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.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查，试回答下列问题：
（1）画出描述折半查过程的判定树；
（2）若查元素54，需依次与哪些元素比较？
（3）若查元素90，需依次与哪些元素比较？
（4）假定每个元素的查概率相等，求查成功时的平均查长度。
解：
（1）先画出判定树如下（注：mid= ab胶管(1+12)/2 =6）：
30
5 63
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议