一、4 （2分）】
24．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
【北京邮电大学 1998 一、6 （2分）】
25. N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 【上海交通大学 1998 一、9】
26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。
【中科院软件所 1997 】
27. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1
必定相同。
【上海交通大学 1998 一、11】
28. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。 【中山大学 1994 一、9 (2分)】 29. B-树中所有结点的平衡因子都为零。 【大连海事大学2001 一、（1，17） (1分)】
30. 在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。 【东北大学 1997 二、 4 (2分)】
31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。【长沙铁道学院 1998 一、9 (1分)】 32. 在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。【合肥工业大学 2001 二、9 （1分）】 33. B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。【华南理工大学 2001 一、3 （1
分）】
34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
【南京理工大学 1997 二、3 （2分）】
35. 二叉排序树删除一个结点后，仍是二叉排序树。【青岛大学 2000 四、4 （1分）】 36. B+树既能索引查找也能顺序查找。【青岛大学 2002 一、10 （1分）】
三、填空题
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 IF suc THEN __(3)__ ELSE __(4)__ END； 【福州大学 1998 二、8 (2分)】 36. 顺序查找 FUNC seq(a,n,k):integer; BEGIN I:=1; A[n+1]= __(1)____; WHILE a[I]<>k DO I:=I+1; IF __(2)___ THEN return(I) ELSE return(0); END; 【中山大学 1998 四、4 (4分)】 37. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言，PASCAL语言的考生不填） #define N /*学生人数*/ int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int head=1,mid,rear=N; do {mid=(head+rear)/2; if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__); if (a[head] return head; } 【西南交通大学 2000 一、12】 38. 假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success 为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点， 既是根结点，也是叶子结点。 #include typedef struct node { int key; struct node *left， *right; } node; node *root; int k，success; void del_leaf(node **t, int k, int *sn) { node *p, *pf; p=*t; *sn=0; while(_（1）_&&!*sn) if (k==p->key) *sn =1; else { _（2）_; if (k if (*sn && p->left==NULL && p->right==null) { if (_（3）_ ) if (pf->left ==p ) pf ->left=null; else pf->right=null; else _（4）_ ; free(p); } else *sn=0; /*call form :del_leaf( &root, k, &success);*/ 【上海大学 1999 一、2 （8分）】 四、应用题 1. 名词解释： 哈希表【燕山大学 1999 一、4（2分）】【哈尔滨工业大学 1999 一、3 （3分）】【首都经贸大学 1997 一、2 （4分）】 同义词： 【山东大学 1998 二、1 (2分)】【山东工业大学 2000 二、1 （2分）】 叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学 2001 五 （5分）】 B-树【南开大学 1996 五、4 (3分) 1998 五、4 (4分) 2000 二、2 （2）】【山东大学 2000 三 ( 8分)】 平衡二叉树（AVL树）？【南开大学 1996 五 、3 (3分) 1998 五、3 (4分)】【厦门大学 1998 四、2 （5分）】 平衡因子【西北工业大学 1999 一、2 (3分)】 平均查找长度（ASL）【西北工业大学 1999 一 、3 (3分)】 trie树。【中山大学 1997 一、3 （3分）】 2. 回答问题并填空 （1）（2分）散列表存储的基本思想是什么？ （2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）（４分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方 法？他们各有何特点？ （4）（３分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ （5）（２分）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。 【山东工业大学 1999 四（15分）】 3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。 【南京航空航天大学 1996 九、2 （6分）】 4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？ 【中国人民大学 2000 一、4 （4分）】 5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？ 【西安电子科技大学2000计应用一、8 （5分）】 6. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表