数据结构1800题动态存储管理

《数据结构 1800 题》
第八章 动态存储管理
一、选择题
1. 动态存储管理系统中，通常可有（ c ）种不同的分配策略。 【长沙铁道学院 1998 三、3 (2 分)】
A． 1 B. 2 C. 3 D. 4 E. 5

二、判断题
1． 1． 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。 （ 错误 ）
【北京邮电大学 2000 一、8(1 分)】
2． 2． 在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的
碎片。 （正确
） 【东南大学 2001 一、1-1 （1 分） 】 【中山大学 1994 一、1（2 分） 】

三、填空题
1．起始地址为 480,大小为 8 的块,其伙伴块的起始地址是__480+8=488（480 %2~(3+1)=0） _____;若块大小为 32,则其伙伴块的起始地址
为___480-32=448____。 【北方交通大学 1999 二、1（4 分） 】
2．二进制地址为 011011110000，大小为（4）10 和（16）10 块的伙伴地址分别为：___011011110100 _____、____011011100000_____。
【上海大学 2002 二、2（2 分） 】
3． 3． 无用单元是指___用户不再使用而系统没有回收的结构和变量。_____,例如，p=malloc(size)；…，p=null；________【北方交通大学 1999 二、6（4 分） 】

四、应用题
2．设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【北京科技大学 1999 一、6（2 分） 】


2．首次拟合法；从链表头指针开始查找，找到第一个≥所需空间的结点即分配。

最佳拟合法：链表结点大小增序排列，找到第一个≥所需空间的结点即分配。

最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。

首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时查询,以便插入适当位置。


3．计算起始二进制地址为011011110000，长度为 4（十进制）的块的伙伴地址是多少？
【中山大学 1999 一、2(3 分)】

3． 011011110100

4．在一个伙伴系统中，已知某存储块的始址Ｘ＝（011011110000）2，大小为２4
，则它的伙伴块的始址是
多少？【北方交通大学 1996 一、1（5 分） 】

4．011011100000

5．地址为（1664）10 大小为（128）10 的存储块的伙伴地址是什么？
地址为（2816）10 大小为（64

）10 的存储块的伙伴地址是什么？【清华大学 1996 四、 】

5．（1）buddy(1664,7)=1664-128=1536 （2）buddy(2816,6)=2816+64=2880

6． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【青岛大学 2000 十、 （10 分） 】 【中国人民大学 2000 一、1（4 分） 】

　6．动态存储分配伙伴系统的基本思想请参见上面题1。边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单，速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。


7．组织成循环链表的可利用空间表附加什么条件时，首次适配策略就转变为最佳适配策略？
【北方交通大学 1998 四、 （8 分） 】

　7．组织成循环链表的可利用空间表的结点大小按递增序排列时, 首次适配策略就转变为最佳适配策略。





《数据结构 1800 题》

第九章 查找
一、 选择题
1.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平
均查找长度ASL 为( C )。 【北京航空航天大学 2000 一、8 （2 分） 】
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) 【南京理工大
学 1998 一、7（2 分） 】
A． （N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ （1）D ）,二分法查找只适用于
查找顺序存储的有序表，平均比较次数为（ （2）C ） 。 在此假定 N 为线性表中结点数，且每次查找都是成
功的。 【长沙铁道学院 1997 四、3 (4 分)】
A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N
2

4. 下面关于二分查找的叙述正确的是 ( D ) 【南京理工大学 1996 一、3 （2 分） 】
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排
列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式
存储
5. 对线性表进行二分查找时，要求线性表必须（ B ） 【燕山大学 2001 一、5 （2 分） 】
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数
据元素有序
6．适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学 1997 一、6 （2 分） 】
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

7. 用二分（对半）查找表的元素的速度比用顺序法( D ) 【南京理工大学 1998 一、11 （2 分） 】
A． A． 必然快 B. 必然慢 C. 相等 D. 不能确定
8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的
查找速度( C )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
【南京理工大学 1997 一、7 （2 分） 】
9. 具有 12 个关键字的有序表，折半查找的平均查找长度（ A ） 【中山大学 1998 二、10 （2 分） 】
A. 3.1 B. 4 C. 2.5 D. 5
10. 折半查找的时间复杂性为（ D ） 【中山大学 1999 一、15】
A. O（n
2
） B. O（n） C. O（nlog
n
） D. O（log
n
）
11．当采用分快查找时，数据的组织方式为 ( B ) 【南京理工大学 1996 一、7 （2 分） 】
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
12. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2）C)时其查找效率最低【武汉交通科技大学
1996 一、2(4 分)】
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。


15. 对大小均为 n 的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平
均查找长度是((1)B) ,对于查找成功,他们的平均查找长度是((2)A)供选择的答案: 【上海海运学院
1997 二、4 （3 分） 】
A. 相同的 B.不同的
16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A )查找法。
A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性
【西安电子科技大学 2001 应用一、8 （2 分） 】
17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) 【北方交通大学 2000 二、 4 （2 分） 】
A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 【合肥工业大学
2000 一、4（2 分） 】
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)
19. 在平衡二叉树中插入一个结

点后造成了不平衡， 设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因
子为 0 右孩子的平衡因子为 1,则应作( C ) 型调整以使其平衡。 【合肥工业大学 2001 一、4 （2 分） 】
A. LL B. LR C. RL D. RR
20．下列关于 m 阶 B-树的说法错误的是( D ) 【南京理工大学 1997 一、9 （2 分） 】
A．根结点至多有 m 棵子树 B．所有叶子都在同一层次上
C. 非叶结点至少有 m/2 (m 为偶数)或 m/2+1（m 为奇数）棵子树 D. 根结点中的数据是有序的
21. 下面关于 m 阶 B 树说法正确的是( B ) 【南京理工大学 1999 一、5 （2 分） 】
①每个结点至少有两棵非空子树； ②树中每个结点至多有 m 一 1 个关键字;
③所有叶子在同一层上; ④当插入一个数据项引起 B 树结点分裂后，树长高一层。
A． ①②③ B. ②③ C. ②③④ D. ③
22. 下面关于 B 和 B+树的叙述中，不正确的是( C ) 【北方交通大学 2001 一、17 （2 分） 】
A. B 树和 B+树都是平衡的多叉树。 B. B 树和 B+树都可用于文件的索引结构。
C. B 树和 B+树都能有效地支持顺序检索。 D. B 树和 B+树都能有效地支持随机检索。
23. m 阶B-树是一棵( B ) 【北京邮电大学 2000 二、2 （20/8 分） 】
A. m 叉排序树 B. m 叉平衡排序树 C. m-1 叉平衡排序树 D. m+1 叉平衡排序树


27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散
列表， 散列函数为 H （key） =key MOD 13,散列地址为 1 的链中有 （ D ） 个记录。 【南京理工大学 1997
一、4 （2 分） 】
A．1 B. 2 C. 3 D. 4
28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) 【南京理工大学 1998 一、10 （2 分） 】
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
29. 若采用链地址法构造散列表，散列函数为 H（key）=key MOD 17，则需 (（1）A) 个链表。这些链的链
首指针构成一个指针数组，数组的下标范围为 (（2）C) 【南京理工大学 1999 一、12(13) （4 分） 】
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0 至17 B. 1 至17 C. 0 至16 D. 1 至16
30. 关于杂凑查找说法不正确的有几个( B ) 【南京理工大学 2000 一、16 （1.5 分） 】
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
31. 设哈希表长为 14，哈希函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61，84 共四个，现
要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( D ) 【南
京理工大学 2001 一、15 （1.5 分） 】
A．8 B．3 C．5 D．9
32. 假定有k 个关键字互为同义词，若用线性探测法把这 k个关键字存入散列表中，至少要进行多少次探
测？( D )
A．k-1 次 B. k 次 C. k+1 次 D. k（k+1）/2 次
【中国科技大学 1998 二、3 （2 分） 】 【中科院计算所 1998 二、3 （2 分） 】
33. 哈希查找中 k 个关键字具有同一哈希值，若用线性探测法将这 k个关键字对应的记录存入哈希表中，
至少要进行( C )次探测。 【西安电子科技大学 1998 一、8 （2 分） 】
A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2
34. 散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率
【西安电子科技大学 2001 应用一、7 （2 分） 】 【北京邮电大学 1999 一、4 （2 分） 】
35. 散列表的地址区间为 0-17,散列函数为 H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列
26，25，72，38，8，18，59 依次存储到散列表中。
（1）元素 59 存放在散列表中的【北方交通大学 2001 一、 （19，20） （4 分） 】地址是（ D ） 。
A． 8 B. 9 C. 10 D. 11
（2）存放元素 59 需要搜索的次数是（ C ） 。
A． 2 B. 3 C. 4 D. 5
36. 将 10 个元素散列到 100000 个单元的哈希表中，则（C ）产生冲突。
【北京邮电大学 2001 一、4 （2 分） 】
A. 一定会 B. 一定不会 C. 仍可能会

二、 判断题
1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，
因为这会影响以后的查找。 【长沙铁道学院 1998 一、3 (1 分)】
√
2．在散列检索中， “比较”操作一般也是不可避免的。 【华南理工大学 2001 一、4 （1 分） 】
√
3．散列函数越复杂越好，因为这样随机性好，冲突概率小. 【南京理工大学 1997 二、5 （2 分） 】
×
4．哈希函数的选取平方取中法最好。 【青岛大学 2000 四、7 （1 分） 】
×
5．Hash 表的平均查找长度与处理冲突的方法无关。 【南京航空航天大学 1997 一、9

（1 分） 】
×
6．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。 【中科院软件所 1999 六
（1-3） （2 分） 】
√
7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 【中山大学
1994 一、8 (2 分)】
√
8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 【山东大学 2001 一 、6 (1 分)】
×
9. 若散列表的负载因子α<1，则可避免碰撞的产生。 【北京大学 1994 】
×
10．查找相同结点的效率折半查找总比顺序查找高。 【北京邮电大学 2002 一、8 （1 分） 】
×
11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。
【中科院软件所 1997 一、6 （1 分） 】
×
12. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，
而且与每块中元素个数有关。 【上海交通大学 1998 一、17】
√
13. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 【山东大学 2001 一、 1 (1 分)】
√
14. 折半查找法的查找速度一定比顺序查找法快 。 【山东大学 2001 一、 8 (1 分)】
×
15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
【西安交通大学 1996 二、 3 (3 分)】
×
16．对无序表用二分法查找比顺序查找快。 【青岛大学 2002 一、8 （1 分） 】
×
17．对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的
平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
【上海海运学院 1995 一、11 （1 分） 1998 一、12 （1 分） 】
√
18．18．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找
时间.
【上海海运学院 1997 一、10 （1 分） 】
×
19． 最佳二叉树是 AVL 树（平衡二叉树） 。 【北京大学 1994 】
√
20．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。
【上海海运学院 1999 一、8 （1 分） 】
×
21．完全二叉树肯定是平衡二叉树。 【南京航空航天大学 1996 六、5 （1 分） 】
×
22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
【南京航空航天大学 1995 五、4 （1 分） 】
×
23．二叉树中除叶结点外, 任一结点 X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值
≥该结点（X）的值,则此二叉树一定是二叉排序树。 【北京邮电大学 1998 一、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 分)】
√
31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。 【长沙铁道学院 1998 一、9 (1 分)】
×
32. 在 9 阶 B-树中，除叶子以外的任意结点的分支数介于 5 和 9 之间。 【合肥工业大学 2001 二、9 （1 分） 】
√
33. 33. B-树的插入算法中，通过结点的向上“分裂” ，代替了专门的平衡调整。 【华南理工大学 2001 一、3 （1 分）
√
34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
【南京理工大学 1997 二、3 （2 分） 】
×
35. 35. 二叉排序树删除一个结点后，仍是二叉排序树。 【青岛大学 2000 四、4 （1 分） 】
√
36. 36. B+树既能索引查找也能顺序查找。 【青岛大学 2002 一、10 （1 分） 】
√

三、填空题
1. 顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为__ n __次；当使用监视哨时，
若查找失败，则比较关键字的次数为__ n+1 __。 【华中理工大学 2000 一、8 （2 分） 】
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值 20，需做的关键
码比较次数为__4__.
【北方交通大学 2001 二、2】
3．在有序表A[1..12]中，采用二分查找算法查等于 A[12]的元素，所比较的元素下标依次为___6,9,11,12_______。
【中国人民大学 2001 一、2 （2 分）】
4. 在有序表 A[1..20]中，按二分查找方法进行查找，查找长度为 5 的元素个数是_____5_____
【合肥工业大学 1999 三、9 （2 分） 】
5. 高度为4 的3 阶b-树中，最多有____26(第4层是叶子结点，每个结点两个关键字)
______个关键字。 【合肥工业大学 2000 三、9 （2 分） 】
6. 在有序表 A[1…20]中，按二分查找方法进行查找，查找长度为 4 的元素的下标从小到大依次是
__

__1,3,6,8,11,13,16,19
______
【合肥工业大学 2000 三、10 （2 分） 】
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为____5______，带权路径长度 WPL
的值为____96______。
【南京理工大学 1997 三、4 （2 分） 】
8. 在一棵 m 阶 B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个
数是___m-1_______;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是
_____m/2-1_____。
【中国科技大学 1998 一、5 （3 分） 】 【南京理工大学 2001 二、4 （3 分） 】
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找 90 时，需____2______次查找
成功，47 时____4______成功，查 100时，需____3______次才能确定不成功。 【南京理工大学 2000 二、7
（4.5 分） 】
10. 10. 哈希表是通过将查找码按选定的__(1)哈希函数__和 __(2)解决冲突的方法__， 把结点按查找码转换为地址进行存储的线性
表。哈希方法的关键是_(3)选择好的哈希函数__和 __(4)_处理冲突的方法_。一个好的哈希函数其转换地址应尽可能__(5)均匀__，而且函数
运算应尽可能__(6)简单
__。
【青岛大学 2000 六、2 （2 分） 】
11. 平衡二叉树又称__AVL树(高度平衡树，高度平衡的二叉排序树)，或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。
________，其定义是__________。 【青岛大学 2001 六、3 （3 分） 】
12. 在哈希函数H（key）=key%p 中，p 值最好取__小于等于表长的最大素数或不包含小于20的质因子的合数________。 【青岛大学 2002 三、9 （2 分） 】
13. 对于长度为 255 的表，采用分块查找，每块的最佳长度为____16______。 【青岛大学 2002 三、10 （2
分） 】
15．有一个 2000 项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)__46_，分成
__(2)_45__块最为理想，平均查找长度是__(3)_46(块内顺序查找) __。 【中国矿业大学 2000 一、6 （3 分） 】
16．假定有 k 个关键字互为同义词，若用线性探测再散列法把这 k 个关键字存入散列表中，至少要进行
___k(k+1)/2
_______次探测。
【西安电子科技大学 2001 软件一、7 （2 分） 】
17. 分块检索中，若索引表和各块内均用顺序查找，则有 900 个元素的线性表分成_____30_____块最好：若
分成25 块，其平均查找长度为___31.5(块内顺序查找)_______。 【北京工业大学 1999 一、 5 ( 2 分)】
18. 执行顺序查找时，储存方式可以是__(1)顺序存储或链式存储__，二分法查找时，要求线性表__(2)顺序存储且有序 __，分块查找时要求线
性表 __(3)块内顺序存储，块间有序__

，而散列表的查找，要求线性表的存储方式是 __(4)散列存储__。 【山东大学 1998 一 、1 (3 分)】
19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平
均比较次数为___(n+1)/2_______。 【山东大学 1999 二、1 (４分)】
20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的
关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为____(n+1)/n*log2(n+1)-1______。 【山
东大学 1999 二、２ (４分)】
21. 平衡因子的定义是___结点的左子树的高度减去结点的右子树的高度
_______【北京轻工业学院 2000 一、2 （2 分） 】
22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)_顺序表_查找，__(2)树表__查找和__(3)哈希表__查找。
处理哈希冲突的方法有__(4)开放定址方法__、__(5)链地址方法__、__(6)再哈希__和__(7)_建立公共溢出区
_。 【华北计算机系统工程研究所 1999
一 （5 分） 】
23. ___直接定址法
_______法构造的哈希函数肯定不会发生冲突。 【重庆大学 2000 一、3】
25. 在一棵有 N 个结点的非平衡二叉树中进行查找， 平均时间复杂度的上限 （即最坏情况平均时间复杂度）
为___O(N)_____ 。
【西南交通大学 2000 一、8】
26. 假设有 n 个关键字，它们具有相同的 Hash 函数值，用线性探测方法解决冲突，把这 n 个关键字散列
到大小为 n 的地址空间中，共计需要做____n(n+1)/2
______次插入和探测操作。 【武汉大学 2000 一、8】
27. 高度为 8 的平衡二叉树的结点数至少有_____54_____个。 【武汉大学 2000 一、6】
28. 高度为 5（除叶子层之外）的三阶 B-树至少有___31_______个结点。 【武汉大学 2000 一、4】
29. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为____37/12______
【燕山大学 2001 二、4 （3 分） 】
30. 可以唯一的标识一个记录的关键字称为___主关键字_______。 【燕山大学 1998 一、7 （1 分） 】
31. 已知二叉排序树的左右子树均不为空，则___左子树 _______上所有结点的值均小于它的根结点值，
___右子树
_______上所有结点的值均大于它的根结点的值。 【燕山大学 1998 一、8 （2 分） 】
32. 动态查找表和静态查找表的重要区别在于前者包含有___插入 _______和____删除______运算，而后者不包含这
两种运算。
【厦门大学 2001 一、3 （14%/5 分）】
33. 对于具有 144 个记录的文件，若采用分块查找法，且每块长度为 8，则平均查找长度为____14______.
【北方交通大学 2001 二、8】
34. 127 阶B-树中每个结点最多有__(

1)126__个关键字；除根结点外所有非终端结点至少有__(2)64__棵子树；
65阶B+树中除根结点外所有结点至少有__(3)_33_个关键字； 最多有__(4)65__棵子树； 【北方交通大学 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)low<=high ___ AND NOT（suc）DO
[ mid：=__(2) (low+hig) DIV 2____；
CASE
k>r[mid].key：low:=mid+1；
k=r[mid].key：suc:=true；
kEND;]
IF suc THEN __(3) binsrch:=mid __ ELSE __(4)binsrch:=0
__
END； 【福州大学 1998 二、8 (2 分)】
36. 顺序查找
FUNC seq(a,n,k):integer;
BEGIN I:=1; A[n+1]= __(1)_K___;
WHILE a[I]<>k DO I:=I+1;
IF __(2)_IEND; 【中山大学 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)_rear=mid-1_ else __(2)head=mid+1__;
}while(__(3)head>rear__);
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）p!=null_&&!*sn)
if (k==p->key) *sn =1;
else { _（2）pf=p _;
if (kkey ) p=p->left; else p=p->right; }
if (*sn && p->left==NULL && p->right==null)
{ if (_（3）p!=*t_ )
if (pf->left ==p ) pf ->left=null; else pf->right=null;
else _（4）)*t=null_ ;
free(p); }
else *sn=0;
/*call form

:del_leaf( &root, k, &success);*/ 【上海大学 1999 一、2 （8 分） 】

四、应用题
3. 如何衡量 hash 函数的优劣？简要叙述 hash 表技术中的冲突概念，并指出三种解决冲突的方法。
【南京航空航天大学 1996 九、2 （6 分） 】

　3．评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。

4．HASH 方法的平均查找路长决定于什么？ 是否与结点个数 N 有关？ 处理冲突的方法主要有哪些？
【中国人民大学 2000 一、4 （4 分）】

　4．哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比)，它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。

5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？
【西安电子科技大学 2000 计应用一、8 （5 分） 】

　5．不一定相邻。哈希地址为i(0≤i≤m-1)的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。


12. 常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关
键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数 H(Key)=Key MOD 13 和线性探测再散列处
理冲突的方法在地址空间 A[0..15]中构造哈希表。 【燕山大学 1999 八 （14 分） 】

　12．常用构造哈希函数的方法有：

(1)数字分析法 该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。

(2)平方取中法 将关键字值的平方取中间几位作哈希地址。

(3)除留余数法 H(key)=key%p，通常p取小于等于表长的最大素数。

(4)折叠法 将关键字分成长度相等(最后一段可不等)的几部分，进行移位叠加或间界叠加，其值作哈希地址。

(5)基数转换法 两基数要互素，且后一基数要大于前一基数。

在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。