数据结构第九、十章 作业答案

第九章 查找

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a1，a2，a3， ，a256)是从小到大排列的，对一个给定的值k，用二分法检索

表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两

次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式

ASL n 1（即（21×log221）/20＝4.6log2(n 1)来计算n次并不正确！）。因为这是在假设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，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋ ＋n-1） 。(而任一元素查找次数 ≤n-1)

8、设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选（ 97 ）

9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法

有序排列。

11 在分块查找方法中，首先查找索引，然后再查找相应的 块。

12． 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ n __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ n+1 。

13．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_____6,9,11,12 _____。

14. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 _

15. 已知二叉排序树的左右子树均不为空，则____左子树______上所有结点的值均小于它的根结点值，____右子树______上所有结点的值均大于它的根结点的值。

16、中序遍历二叉排序树得到的序列是 有序 序列（填有序或无序）。 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字

17、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为1 和3 ·

二、单项选择题

（ B ）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;

Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ 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. 链表适用于 查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机

（ C ）5. 折半搜索与二叉搜索树的时间性能

A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）

6．散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ D ）。

A． 8 B. 9 C. 10 D. 11

7. 当采用分快查找时，数据的组织方式为 ( B )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

8. 散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率

9. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次

10、 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。【西安电子科技大学 1998 一、8 （2分）】

A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2

11、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR

12、二叉查找树的查找效率与二叉树的( C)有关, 在 (B）)时其查找效率最低

(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置

(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

13、在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为（ C）

A) 2 B) 3 C) 4 D) 5

14、对包含n个元素的哈希表进行查找，平均查找长度为（ D）

A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n

15、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n

16. 下面关于二分查找的叙述正确的是 ( D )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储

17. 对线性表进行二分查找时，要求线性表必须（ B ）

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序

18．适用于折半查找的表的存储方式及元素排列要求为( D )

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

19. 用二分（对半）查找表的元素的速度比用顺序法( D )

A． 必然快 …… 此处隐藏：13500字，全部文档内容请下载后查看。喜欢就下载吧 ……