第九章查找习题

第九章 查 找

一，选择

1. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )

A．（N+1）/2 B． N/2 C．N D． [（1+N）*N ]/2 2. 对线性表进行二分查找时，要求线性表必须（ ）

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

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

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 4. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5

5. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地

址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。

A．1 B. 2 C. 3 D. 4

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

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 8. 既希望较快的查找又便于线性表动态变化的查找方法是 ( )

A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR 1.A 2.B 3.D 4.A 5.D 7.D 8.C 9.C 10.C 二，判断

1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ） 2．在散列检索中，“比较”操作一般也是不可避免的。（ ）

3. 平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）

4.二叉排序树删除一个结点后，仍是二叉排序树。 （ ） 5．Hash表的平均查找长度与处理冲突的方法无关。 （ ）

6. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1

必定相同。（ ）

7. 散列法的平均检索长度不随表中结点数目的增加而增加，而随负载因子的增大而增大。（ ）

8. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二叉排序树相同。（ ）

1

9. 若散列表的负载因子α<1，则可避免碰撞的产生。 （ ） 10. 顺序查找法适用于存储结构为顺序或链接存储的线性表。（ ） 二，判断 1.√ 2.√ 3.× 4.√ 5.× 6.× 7.√ 8.× 9.× 10.√

三，填空

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

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

3. 在哈希函数H（key）=key%p中，p值最好取__________。 5. 平衡因子的定义是__________

6.处理哈希冲突的方法有__ __、__ _、__ _和__ __。 7. __________法构造的哈希函数肯定不会发生冲突。 三，填空

1．n n+1

2．6,9,11,12

3．小于等于表长的最大素数或不包含小于20的质因子的合数 5．结点的左子树的高度减去结点的右子树的高度

6．开放定址方法；链地址方法；再哈希；建立公共溢出区 7．直接定址法

四，应用题

1. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。

2．设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。

1． 散列地址 0 关键字 比较次数 1 ASLsucc =21/11 2．

1 1 2 1 3 1 4 2 5 1 6 2 7 3 8 2 9 4 10 3 11 231 89 79 25 47 16 38 82 51 39 151 2

3

本文来源：https://www.bwwdw.com/article/akqh.html