内容发布更新时间 : 2024/6/3 22:06:46星期一 下面是文章的全部内容请认真阅读。

1. 用二分（对半）查找表的元素的速度比用顺序法( )

A． 必然快 B. 必然慢 C. 相等 D. 不能确定

2. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5

3．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性

4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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)

5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR

7. 下面关于B和B+树的叙述中，不正确的是( )

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。

C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。

8. m阶B-树是一棵( )

A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树

9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。

A．1 B. 2 C. 3 D. 4

10. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

11. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 （(1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）)

（1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16

12. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )

A．8 B．3 C．5 D．9

13. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次

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

A. 一定会 B. 一定不会 C. 仍可能会

15. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处

理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。

（1）元素59存放在散列表中的地址是（ ）。

A． 8 B. 9 C. 10 D. 11

（2）存放元素59需要搜索的次数是（ ）。

A． 2 B. 3 C. 4 D. 5

16. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。 答：4

17．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。 答：6,9,11,12

18. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 答：5

19. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。 答：m-1,「m/2?-1

20、 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈

希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。

答：(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单

21、 哈希函数H（key）=key%p中，p值最好取__________。 答：小于等于表长的最大素数或不包含小于20的质因子的合数

22、 对于长度为255的表，采用分块查找，每块的最佳长度为__________。 答：16

23. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 答：(n+1)/2

24. __________法构造的哈希函数肯定不会发生冲突。 答：直接定址法

25. 127阶B-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶B+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；

答：(1)126 (2)64 (3)33 (4)65

26. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。

#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]

答：(1)rear=mid-1 (2)head=mid+1 (3)head>rear

27. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 答： 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 01 9 23 84 27 55 20 比较次数 1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8