第8章查找

第8章 查找

一、 选择题

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

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

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

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。 A.N+1 B.2log2N C.log2N D.N/2 E.Nlog2N F.N2 4. 下面关于二分查找的叙述正确的是 ( )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 5. 对线性表进行二分查找时，要求线性表必须（ ）

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 6．适用于折半查找的表的存储方式及元素排列要求为( )

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

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 7. 用二分（对半）查找表的元素的速度比用顺序法( )

A． A． 必然快 B. 必然慢 C. 相等 D. 不能确定

8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )

A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 9. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为（ ）

A. O（n2） B. O（n） C. O（nlog2n） D. O（log2n） 11．当采用分快查找时，数据的组织方式为 ( )

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

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储；

D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。

（3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1)

14*．在等概率情况下,线性表的顺序查找的平均查找长度ASL为( （1） ),有序表的折半查找的ASL为( （2） ),对静态树表,在最坏情况下,ASL为( （3） ),而当它是一棵平衡树时,ASL为 ( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案：

（1）（2）（3）（4）（5）: A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n)

15. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是

((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案: A. 相同的 B.不同的

16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性 17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( )

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

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

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）

1

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

A. LL B. LR C. RL D. RR 20*．下列关于m阶B-树的说法错误的是( )

A．根结点至多有m棵子树 B．所有叶子都在同一层次上

C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的 21*. 下面关于m阶B树说法正确的是( )

①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。

A． ①②③ B. ②③ C. ②③④ D. ③

22. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突

A. 一定会 B. 一定不会 C. 仍可能会 23*. m阶B-树是一棵( )

A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 24*. 在一棵含有n个关键字的m阶B-树中进行查找，至多读盘( )次。

?m??n?1??n??m?1????2??2??2?nn2? D. 1+log????A. log2 B. 1+log2 C. 1+log???

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

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

26. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，

38，8，18，59依次存储到散列表中。

（1）元素59存放在散列表中的地址是（ ）。

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

（2）存放元素59需要搜索的次数是（ ）。

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

27. 设有一组记录的关键字为{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

28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

29. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成

一个指针数组，数组的下标范围为 (（2）)

（1） A．17 B. 13 C. 16 D. 任意

（2） A．0至17 B. 1至17 C. 0至16 D. 1至16 30. 关于杂凑查找说法不正确的有几个( )

（1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集

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

31. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字

为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )

A．8 B．3 C．5 D．9

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

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

33. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行

( )次探测。

A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2 34.顺序查找法适合于存储结构为（ ）的线性表。

2

A．哈希存储 B．顺序存储或链接存储

C．压缩存储 D．索引存储

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

A．以顺序方式存储

C．以链接方式存储

B．以链接方式存储，且结点按关键字有序排序 D．以顺序方式存储，且结点按关键字有序排序

36.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。

A．n B．n／2 C．(n+1)／2 D．(n－1)／2

37.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。

A．O(n2) B．O(nlog2n) C．O(n) D．O(log2n)

38.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ）查找方法。 A．分块 B．顺序 C．二分 D．哈希

39.采用分块查找时，若线性表共有625个元素，查找每个元素的概率相等，假设采用顺序查找来确定结点所在的块时，每块分（ ）个结点最佳。

A．6

B．10

C．25

D．625

40.100个元素采用二分查找时，最大的比较次数是（ ）。

A．25 B．50 C．7 D．10

41.衡量查找算法效率的主要标准是（ ）。 A．元素个数 B．平均查找长度 C．所需的存储量 D．算法难易程度

二、 判断题

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

3．散列函数越复杂越好，因为这样随机性好，冲突概率小. 4．哈希函数的选取平方取中法最好。

5．Hash表的平均查找长度与处理冲突的方法无关。

6．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。

7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 9. 若散列表的负载因子α<1，则可避免碰撞的产生。 10．查找相同结点的效率折半查找总比顺序查找高。

11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

12. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。

13. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 14. 折半查找法的查找速度一定比顺序查找法快 。

15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 16．对无序表用二分法查找比顺序查找快。

17．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长

度是相同的，而对于查找失败，它们的平均查找长度是不同的。

18．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间. 19*．最佳二叉树是AVL树（平衡二叉树）。

20．在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。 21*．完全二叉树肯定是平衡二叉树。

22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。

23．二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。

24．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 25. N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。

26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。 27*. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。

3

28*. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。

29*. B-树中所有结点的平衡因子都为零。

?m???30*. 在m阶B-树中每个结点上至少有?2?个关键字，最多有m个关键字。

31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。 32*. 在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。 33*. B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。

34*. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。 35. 二叉排序树删除一个结点后，仍是二叉排序树。 36. 二分查找法要求待查表的关键字的值必须有序。

37. 哈希法是一种将关键字转换为存储地址的存储方法。 38. 在二叉排序树中，根结点的值都小于孩子结点的值。

39. 对有序表而言，采用二分查找总比采用顺序查找法速度快。

40. 哈希表的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

41. 一般来说，用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。 三、填空题

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

2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.

3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。 4. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 5*. 高度为4的3阶b-树中，最多有__________个关键字。

6. 在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________ 7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。 8*. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。

9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。 10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 11*. 平衡二叉树又称__________，其定义是__________。 12. 在哈希函数H（key）=key%p中，p值最好取__________。

13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。 14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。

15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。

16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。

17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。 18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。

19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数

为__________。

20*. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次

插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 21*. 平衡因子的定义是__________

22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和__(3)__查找。处理哈希冲

突的方法有__(4)__、__(5)__、__(6)__和__(7)__。

23*. __________法构造的哈希函数肯定不会发生冲突。

4