中信银行笔试IT类复习参考资料带答案(14)

A.9 B.8 C.7 D.6 8.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59 依次存储到散列表中。

则元素59 存放在散列表中的地址是（ D ）。 A． 8 B. 9 C. 10 D. 11

9. 适于对动态查找表进行高效率查找的组织结构是（ C ） A.有序表 B.分块有序表 C.二叉排序树 D.线性链表

10.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为 D 。

A.n B.log2n C.(h+1)/2 D.h

11.将10个元素散列到100000个单元的哈希表中，则 C 产生冲突。

A. 一定会 B. 一定不会 C. 仍可能会 12.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) 。 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 13.散列查找时，解决冲突的方法有（ D ） A.除留余数法 B.数字分析法 C.直接定址法 D.链地址法

二、填空题

1. 假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为（ 1 ）,则比较二次查找成功的结点数为（ 2 ）,则比较三次查找成功的结点数为（ 4 ）,则比较四次查找成功的结点数为（ 8 ）,则比较五次查找成功的结点数为（ 5 ）,平均查找长度为（ 3.7 ）。 2.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5 的元素个数是（ 5 ） 在分块检索中如果采用顺序查找确定块，则对大小为196个元素的线性表分成（1 ） 块最好，这时平均查找长度为（ 89 ）。

3.假定查找有序表A[25]中每一元素的概率相等，则进行二分查找的平均查找长度为（ 5 ）。 4. 在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行（ 3 ）次元素之间的比较。

5.对有序表作折半查找，其中i和j表示查找过程中的上界和下界，则查找不成功时有（ log[j-i] ）。

6.在对长度为n的顺序存储的有序表进行二分检索，对应的二分检索判定树的高度为（ log[n]+1 ）。

7.在顺序存储的线性表R[0..29]上进行顺序检索的平均检索长度为（16 ），进行二分检索的平均检索长度为（ 6 ），进行分块检索（设分为5块）的平均检索长度为（ 7 ） 8.若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用（ 二分 ）遍历法。

9. 元素关键字转换为该元素存储位置的函数f称为（ 哈希函数 ）。