三、填空题
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。【华中理工大学 2000 一、8 （2分）】
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
【北方交通大学 2001 二、2】
3．在有序表a[1..12]中，采用二分查找算法查等于a[12]的元素，所比较的元素下标依次为__________。
【中国人民大学 2001 一、2 （2分）】
4. 在有序表a[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________
【合肥工业大学 1999 三、9 （2分）】
5. 高度为4的3阶b-树中，最多有__________个关键字。【合肥工业大学 2000 三、9 （2分）】
6. 在有序表a[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________
【合肥工业大学 2000 三、10 （2分）】
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度wpl的值为__________。
【南京理工大学 1997 三、4 （2分）】
8. 在一棵m阶b-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。
【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。【南京理工大学 2000 二、7 （4.5分）】
10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。
【青岛大学 2000 六、2 （2分）】
11. 平衡二叉树又称__________，其定义是__________。【青岛大学 2001 六、3 （3分）】
12. 在哈希函数h（key）=key%p中，p值最好取__________。【青岛大学 2002 三、9 （2分）】
13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。【青岛大学 2002 三、10 （2分）】
14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。【中国科技大学 1998 一、4 （3分）】
15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。【中国矿业大学 2000 一、6 （3分）】
16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
【西安电子科技大学2001软件一、7 （2分）】
17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。【北京工业大学 1999 一、 5 ( 2分)】
18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。【山东大学 1998 一 、1 (3分)】
19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 【山东大学 1999 二、1 (４分)】
20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。【山东大学 1999 二、２ (４分)】
21. 平衡因子的定义是__________【北京轻工业学院 2000 一、2 （2分）】
22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。【华北计算机系统工程研究所 1999 一 （5分）】
23. __________法构造的哈希函数肯定不会发生冲突。【重庆大学 2000 一、3】
24. 具有n个关键字的b树的查找路径长度不会大于__________。【中科院计算机 1999 二、2】
25. 在一棵有n 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为________ 。
【西南交通大学 2000 一、8】
26. 假设有n个关键字，它们具有相同的hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做__________次插入和探测操作。【武汉大学 2000 一、8】
27. 高度为8的平衡二叉树的结点数至少有__________个。【武汉大学 2000 一、6】
28. 高度为5（除叶子层之外）的三阶b-树至少有__________个结点。【武汉大学 2000 一、4】
29. 假定查找有序表a[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为__________
【燕山大学 2001 二、4 （3分）】
30. 可以唯一的标识一个记录的关键字称为__________。【燕山大学 1998 一、7 （1分）】
31. 已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。【燕山大学 1998 一、8 （2分）】
32. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
【厦门大学 2001 一、3 （14%/5分）】
33. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________.
【北方交通大学 2001 二、8】
34. 127阶b-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶b+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；【北方交通大学 1999 二、5 （4分）】
35. 若静态查找表的类型定义如下：
type rectype=record key：keytype； ……； end；
ordlisttp=array[1..n] of rectype；
请完成以下二分查找的算法：
func binsrch（r：ordlisttp；k：keytype）：integer；
begin low:=1；hig:=n；suc:=false；
while ___(1)___ and not（suc）do
[ mid：=__(2)____；
case
k>r[mid].key：low:=mid+1；
k=r[mid].key：suc:=true；
k
end;]
if suc then __(3)__ else __(4)__
end； 【福州大学 1998 二、8 (2分)】
责任编辑：小草
