的数据组成索引块

C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分为若干块，每块（除最后一块外）中数据个数需相同 10.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。 A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序和归并排

11、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l。建立二叉排序树，则先序遍历序列为 。

A、 abcloprstu B、 alcpobsrut C、 trbaoclpsu D、 trubsaocpl

12、设有一组记录的关键字为{19，24，23，1，68，20，84，27，55，11，10，79}，用链地址法构造哈希表，哈希函数为H(KEY)=KEY MOD 13 ,哈希地址为1的链中有 个记录。

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

13、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的健值

。

A、一定都是同义词 B、 一定都不是同义词 C、都相同 D 、健值不一定有序的顺序表

14、设哈希表长为14，哈希函数为H(key)= key mod 11,表中已经有4个结点：addr(14)=3, addr(38)=5, addr(61)=6, addr(85)=8,其余地址为空,用线性探测再散列法解决冲突，关键字为49的结点的地址为 。

A、7 B、3 C、5 D、 4

15、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经

次比较后查找成功。

A、2 B、 3 C、 4 D、 12

16、已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是

。

A、将该元素所在的存储单元清空。 B、将该元素用一个特殊的元素代替

C、将与该元素有相同Hash地址的后继元素顺次前移一个位置。 D、用与该元素有相同Hash地址的最后插入表中的元素替代。

- 33 -

17、以下说法错误的是 。

A、数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 B、除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 C、平方取中法以健值平方的中间几位作为散列地址。

D、基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。

18、下面关于B-树和B+树的叙述中，不正确的是 。

A、B-树和B+树都是平衡的多叉树 B、B-树和B+树都可用于文件的索引结构 C、B-树和B+树都能有效地支持顺序检索 D、B-树和B+树都能有效地支持随机检索 19、下列关于m阶B-树的说法错误的是 。

A、根结点至多有m棵子树。 B、 所欲叶子都在同一层 C、非叶子结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树 D、根结点中的数据都是有序的。

20、一棵3阶B-树中含有2047个关键字，包含叶结点层，该树的最大深度为 A、11 B、12 C、13 D、 14

21、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。

。

A、2k-1-1 B、 2k-1 C、2k-1+1 D、2k-1

22、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是 。

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)

23、设二叉排序树中关键字由1至1000的整数构成,现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查到的序列？ A、2，252，401，398，330，344，397，363； B、924，220，911，244，898，258，362，363； C、925，202，911，240 ，912，245，363；

D、2，399，387，219，266，382，381，278，363。

- 34 -

24、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 A 、LL B、 LR C、 RL D、 RR

二、判断题

1、n个数放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

2、若散列表的装填因子小于1，则可避免碰撞的产生。 3、哈希表的平均查找长度与处理冲突的方法无关。 4、对无序表用折半法查找比顺序查找法快。

5、在二叉排序树中插入一个新结点，总是插入到叶节点下面。

6、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。

7、对两棵具有相同关键字而形状不同的二叉排序树，按中序遍历得到的序列却是一致的。 8、完全二叉树肯定是平衡二叉树

9、在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。

10、如果完全二叉树从根结点开始按层次遍历的序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。

11、m阶B-树的任何一个结点的左右子树高度都相等。

12、设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。 13、对给定的关键字集合,以不同的次序插入初始为空的树中,将得到同一棵二叉排序树。 三、填空题

1． 动态查找表和静态查找表的重要区别在于前者包含有 后者不包含这两种运算。

2．对n个记录的表中进行折半查找，最大比较次数是 。

和 运算，而

型调整以使其平衡。

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

。

4．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需

次查找成功，查找47时需 次成功，查找100时，需 次才能确定不成功。

- 35 -

5.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为______，比较二次查找成功的结点数为________，比较三次查找成功的结点数为_________，比较四次查找成功的结点数为________，比较五次查找成功的结点数为__________。总的比较查找长度为__________。

6．使用分块查找时，除表本身外，尚需建立一个 及该块的起始位置。

7.采用散列技术来实现查找，需要解决的问题有:

; ;

。

，用来存放每一块中的最大值以

8.、在各种查找方法中，平均查找长度与结点个数无关的查找方法是 9.含有12个结点的平衡二叉树的最大深度是 。（设根结点深度为1）

10.如果将n个元素，按其关键字递增的顺序依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为

。

个，除根

11.在一个127阶的B-树上，每个结点中包含的关键字数目最多允许为 结点外的非终端至少有

棵子树。

12. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。

个；最少可以是 13.高度为5的平衡二叉树；其结点数最多可以有 个。

14．在一棵m阶的B-树中，当一关键字插入某结点而引起该结点分裂时，此结点原有 个关键字。若删去某结点中的一个关键字，而导致该结点合并时，该结点中原有 个关键字。

15.一个待散列存储的线性表为（18，34，58，26，75，67，48，93，81），哈希函数为H(key)=key ,若采用线性探测法解决冲突，则平均查找长度为 地址法解决冲突，则平均查找长度为

。

；若采用链16.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行

四、解答题

1．简述顺序查找法，折半查找法和分块查找法对被查找表中元素的要求。

- 36 -

探测。