还剩5页未读,继续阅读
文本内容:
1、静态查找表和动态查找表的区别是所包含的数据元素的类型不同施加其上的操作不同它们的逻辑结构相同D以上都不对正确答案B解析B、若在查找的同时对表做修改操作如插入和删除,则相应的查找表称之为动态查找表若在查找中不涉及表的修改操作,则相应的查找表称之为静态查找表
2、顺序查找法适合于存储结构为的线性表索引存储压缩存储CJII页序存储或链式存储哈希存储正确答案C解析C、顺序查找可以从前向后或从后向前依次查找,既适合于顺序存储结构也适合于链式存储结构
3、采用顺序查找方法查找长度为n的顺序表时,在等概率时成功查找的平均查找长度为n-l/2nn/2D・n+l/2正确答案D解析D、顺序查找时,元素ai需i次比较,成功查找的平均查找长度=1+24-...+n/n=n+l/2o
4、采用顺序查找方法查找长度为n的顺序表时,在等概率时不成功查找的平均查找长度为n-l/2nn/2D・n+l/2正确答案B解析B、当查找的元素不在线性表中时,均需要n次元素之间的比较
5、适合于折半查找的数据组织方式是oA以链表存储的有序线性表以顺序表存储的有序线性表C以链表存储的线性表以顺序表存储的线性表正确答案B解析B、折半查找的数据必须是有序的另外,折半查找中需要确定查找区间,这要求存储结构最好具有随机存取特性,而顺序表满足这个特性
6、采用折半查找方法查找长度为n的线性表,当n很大时,在等概率时不成功查找的平均查找长度为oOnlog2n0n20nOlog2n正确答案D解析D、采用折半查找时,若n很大,对应的判定树可以看成是一棵满二叉树,失败节点夕卜部节点集中在最下一层,落在每个失败节点时比较的次都均为log2no
7、设有100个元素的有序表,采用折半查找方法,在等概率时成功时最大的比较次数是5025107正确答案D解析D、成功时最大比较次数为log2(n+l)(取上界)=log2
(101)(取上界)=
78、已知一个长度为16的顺序表,其元素按关键字有序排序,若采用折半查找法查找一个存在的元素,则比较的次数最多是()6547正确答案B解析B、n=16采用折半查找法查找一个存在的元素即为成功查找成功查找的最多比较次数=log2(n+l)(取上界)=log2
(17)(取上界)=
59、一个递增有序表为R[O..ll]采用折半查找方法进行查找,在一次不成功查找中,以下()是不可能的记录比较序列A・R
[5]、R
[8]、R
[6]、R
[7]B・R
[5]、R
[8]、R
[10]C・R
[5]、R
[2]、R
[3]D・R
[5]、R
[8]、R
[6]正确答案B解析成画出递增有序表采用折半查找对应的判定树一次失败的查找必须到达某个外部节点,而R
[5]、R
[8]、R
[10]序列没有到达任何外部节点
10、对有3600个记录的索引顺序表(分块表)进行分块查找,最理想的块长是()[log23600]1800601200正确答案C解析C、n=3600分块查找最理想的块长=,4代11=54代3600=
6011、二叉排序中,按遍历二叉排序得到的序列是一个有序序列A后序先序中序层次正确答案C解析C、二叉排序的中序遍历序列恰好是一个递增有序序列
12、在含有27个节点的二叉排序树上,查找关键字为35的节点,则依次比较的关键字有可能是O4636182835183628463528361846354628183635正确答案A解析A、画出各选项对应的查找树,从中看到只有选项D对应的查找树构成一棵二叉排序树,可以作为一棵二叉排序树的一部分其他查找树均不构成一棵二叉排序树
13、以下关于二叉排序树的叙述中正确的是二叉排序树是动态树表,在插入新节点时会引起树的重新分裂和合并在二叉排序树中进行查找,关键字的比较次数不超过节点数的一半对二叉排序树进行层次遍历可以得到一个有序序列D.在构造二叉排序树时,若关键字序列有序,则二叉排序树的高度最大正确答案D
14、有一棵含有8个节点的二叉排序树,其节点值为A~H,以下是其后序遍历结果BCAGEHFDBDACEFHGBCAEFDHGADBCEGFH正确答案C解析C、该二叉排序树的中序序列为ABCDEFGH后序序列应是A〜H的出栈序列其中选项A、B和D都不是合法的出栈序列,只有选项C是合法的出栈序列
15、具有5层节点的AVL树至少有()个节点10171512正确答案D解析D、设Nh表示高度为h的平衡二叉树中含有的最少节点数,有Nl=lN2=2Nh=Nh・l+Nh・2+l由此求出N5=12O
16、以下关于m阶B■树的叙述中正确的是()树中每个节点至多有个关键字所有叶子节点均在同一层上当插入一个关键字引起B■树节点分裂时,树增高一层每个节点至少有两棵非空子树正确答案B解析B、选项A错误,因为m阶B・树可能只有一个根节点选项B错误,在m阶B-树中除根节点外每个节点至少有m/2(取上界)-1个关键字选项D错误当插入一个关键字引起B■树节点分裂时,树不一定会增高一层,只有节点分裂延续到根节点,根节点也分裂后,树才会增高一层
17、在一棵m阶B■树中删除一个关键字会引起合并,则该节点原有()个关键字fm/2][m/2]-ll[m/2]+l正确答案B解析B、引起合并的节点应为关键字个数的下限
18、以下关于哈希查找的叙述中错误的是()哈希函数选得好可以减少冲突现象哈希函数H(k)=kMODpp通常取小于等于表长的素数用拉链法解决)中突易弓I起堆积现象D.用线性探测法解决冲突易引起堆积现象正确答案C解析C、用拉链法解决冲突时不存在堆积现象,只有用线性探测法解决冲突时易引起堆积现象
19、以下关于哈希查找的叙述中正确的是()A.哈希表的装填因子等于表中填入的记录数除以哈希表的长度B.采用拉链法解决冲突时,查找一个元素的时间是相同的哈希表在查找成功时的平均查找长度仅仅与表长有关哈希查找中不需要任何关键字的比较正确答案A
20、为提高哈希(Hash)表的查找效率,可以采取的正确措施是()I.增大装填(载)因子H.设计)中突(碰撞)少的哈希函数in.处理;中突(碰撞)时避免产生堆积(堆积)现象A.仅Ib.仅n仅u、md.仅i、n正确答案c解析c、装填(载)因子a越大发生冲突的可能性越大,所以I错误因为哈希表是由哈希函数和处理冲突两部分组成的,查找效率与这两部分有关,所以II和m是正确的。