《计算机专业基础综合数据结构(集合)历年真题试卷汇编5》由会员分享,可在线阅读,更多相关《计算机专业基础综合数据结构(集合)历年真题试卷汇编5(5页珍藏版)》请在金锄头文库上搜索。
1、计算机专业基础综合数据结构(集合)历年真题试卷汇编 5(总分:66.00,做题时间:90 分钟)一、 单项选择题(总题数:21,分数:46.00)1含有n个非叶子结点的m阶B 一树至少包含()个关键字。【北京交通大学20041A. (m-1) * nB. nC. n * (m/ 2-1)D. (n 1) * (m/ 2-1)+1 丿2. 理论上,散列表的平均比较次数为( )次。【北京邮电大学2005一、9(2分)】A. 1 丿B. 2C. 4D. n3. 散列函数有一个共同的性质,即函数值应当以( )取其值域的每个值。【西安电子科技大学2001 计算机 应用一、7(2分)】 【北京邮电大学。
2、1999一、4(2分)】A. 最大概率B. 最小概率C. 平均概率D. 同等概率丿4. 将10个元素散列到100000个单元的哈希表中,则( )产生冲突。【北京邮电大学2001 一、4(2分)】A. 一定会B. 一定不会C. 仍可能会丿5. 采用链地址法解决冲突的哈希表中,查找成功的平均查找长度()。【北京交通大学2005一、6(2分)2007】A. 直接与关键字个数有关B. 直接与装填因子有关C. 直接与表的容量有关D. 直接与哈希函数有关丿链地址法解决冲突,是动态申请结点,容量只受内存所限。6下面关于哈希(Hash,杂凑)查找的说法正确的是()。【南京理工大学1998 一、10(2分)】【
3、烟台大学 2007一、 1 8(2分)】A. 哈希函数构造的越复杂越好,因为这样随机性好,冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数,要视情况而定丿D. 若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单地将该元素删去即可7. 在构造哈希表方面,下面的说法( )是正确的。 【华南理工大学2005一、 1(2分)】A. 再散列在处理冲突时不会产生“聚集”B. 散列表的装载因子越大,说明空间利用率越好,因此应使装载因子尽量大C. 散列函数选得好可减少冲突现象丿D. 对于任何具体关键字都不可能找到不产生冲突的散列函数8. 在构造散列表方面,下面的说法( )
4、是正确的。【华南理工大学2006】A. 链地址法在处理冲突时会产生聚集B. 线性探测再散列在处理冲突时会产生聚集丿C. 好的哈希函数可以完全避免冲突D. 在哈希表中进行查找是不需要关键字的比较的答案B是正确的。应该说答案C也并非完全错误。事实是,经过很多人的努力,处理Pascal关键字的函数 的确是“perfect”,就不产生冲突。9. 散列文件的特点是( )。【烟台大学2007 一、20(2 分)】A. 记录按照关键字排序B. 记录可以顺序存取C. 存取速度快,但占用的存储空间较多 丿D. 记录不需要排序,存取速度快若采用链地址法构造散列表,散列函数为 H(key)=key MOD 17,则
5、需(1)个链表。这些链的链首指针构成 一个指针数组,数组的下标范围为(2)。【南京理工大学1995一、12(13)(4分)】(分数:4. 00)(1). (1)A. 17 丿B. 13C. 16D. 任意(2). (2 )A. 0 至 17B. 1 至 17C. 0至16丿D. 1 至 1610. 设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79),用链地址法构造散列 表,散列函数为H(key)=keyMOD 13,散列地址为1的链中有()个记录。【南京理工大学1997 、4(2分)】A. 1B. 2C. 3D. 4 丿11. 已
6、知一个线性表(1, 13, 12, 34, 38, 33, 27, 22),假定采用h(k)=k%11计算散列地址进行散列存储, 若用链地址法处理冲突,则查找成功的平均查找长度为( )。【哈尔滨工业大学2005二、 6(1分)】A. 1B. 98C. 131 1D. 13/8丿12. 设哈希表长M=14,哈希函数H(KEY)=KEY MOD 1 1。表中已有4个结点:ADDR(15)=4, ADDR(38)=5, ADDR(61)=6, ADDR(84)=7,其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点的地址是()。【东华大学 2001 一、 8(1 分)】A. 8B. 3C.
7、 5D. 9 丿ADDR(49)=5,冲突,(5+1 2 ) %11=6,冲突,(51 2 ) %11=4,冲突,(5+2 2 ) %11=9,存入关键字 49。13. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测? ( ) 【中国科技大学1998二、 3(2分)】【中科院计算所1998二、 3(2分)】A. k-1 次B. k 次C. k+1 次D. k(k+1) / 2 次丿散列表的地址区间为017,散列函数为H(K)=Kmod 17。采用线性探测法处理冲突,并将关键字序列26, 25, 72, 38, 8, 18, 59依次存储到散列表中。【
8、北方交通大学2001一、 (19, 20)(4分)】(分数: 4.00) (1).元素59存放在散列表中的地址是( )。A. 8B. 9C. 10D. 11 丿 在关键字59 存入前,散列表如下,59 的散列地址是8,冲突。经探测4 次,存在散列地址1 1。(2). 存放元素59 需要搜索的次数是( )。A. 2B. 3C. 4 丿D. 514. 关于杂凑查找说法不正确的有几个? ( )【南京理工大学2000一、16(15分)】(1)采用链地址法解决 冲突时,查找一个元素的时间是相同的(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一 个元素的时间是相同的 (3)用链地址法解决冲突
9、易引起聚集现象(4)再哈希法不易产生聚集A. 1B. 2 丿C. 3D. 4(1)和(3)不正确。15. 采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是()。【中国科学技术大学1997一、4(1 分)】A. 数据元素过多B. 负载因子过大C. 哈希函数选择不当D. 解决冲突的算法选择不好丿16. 在采用链地址法处理冲突所构成的散列表上查找某一关键字,则在查找成功的情况下,所探测的这些位 置上的键值( )。【北京交通大学2006一、6(2分)】A. 定都是同义词 VB. 不一定都是同义词C. 都相同D. 一定都不是同义词17. 查找低效的数据结构是( )。【中国科学院2006】A. 有
10、序顺序表B. 二叉排序树C. 堆 VD. 平衡的二叉排序树A、B和C都数据有序,而堆只有双亲和左右子女间的关系,查找某元素效率最低。18假定关键字K=2789465,允许存储地址为3位十进制数,现在得到的散列地址为149,则所采用的构建散列函数的方法是( )。【南开大学 2005】A. 除留余数法,模为 23B. 平方取中法 VC. 移位叠加法D. 间界叠加法A、C和D 一试发现不对,B是对的。k 2 =7781114986225,取中间3位数149即可。19. 设散列地址空间为0m 1,为关键字,用p去除k,将所得到的余数作为k的散列地址,即H(k)=kmodp, 为了减少发生冲突的概率,一
11、般取P为()。【中国科学院自动化所】A. 小于 mB. 小于m的最大偶数C. mD. 小于 m 的最大素数 V二、 判断题(总题数:10,分数:20.00)20. 若在一棵(分类)平衡树T中先删除某结点N,然后再插入该结点N,得到的新的平衡树T,则T和T1不 一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的平衡树T2 一定与T完全相 同。 ( ) 【上海交通大学1994一、4 (2分) 】A. 正确B.错误丿如果因为插入结点M引起平衡树失衡,则要进行平衡化处理,插入的结点M可能不再是叶子。这时再删除 M结点,所得平衡树与插入M结点前不一定相同。只有二叉排序树插入结点后立刻
12、删除刚插入的结点,所 得二叉排序树不变。21. 二元查找树的任何结点的左右子树都是二元查找树。 ( ) 【哈尔滨工业大学2 002三、4 ( 1分) 】A. 正确丿B. 错误22将线性表中的结点信息组织成平衡的二叉树,其优点之一是总能保证任意检索长度均为log 2 n量级(n 为线性表中的结点数目)。 ( )【中山大学1994一、9(2分)】A. 正确丿B. 错误23. B 一树中所有结点的平衡因子都为零。()【大连海事大学2001 一、17(1分)】A. 正确丿B. 错误24. 在m阶B 一树中每个结点上至少有m/2个关键字,最多有m个关键字。()【东北大学1997二、4(2 分)】【烟台大
13、学2007二、 14(1分)】A. 正确B. 错误丿25. 在9阶B 一树中,除叶子以外的任意结点的分支数介于5和9之间。()【合肥工业大学2001二、9(1 分)】A. 正确B. 错误丿26. B 一树的插入算法中,通过结点的向上“分裂”,代替了专门的平衡调整。()【华南理工大学2001 一、 3(1 分)】A. 正确丿B. 错误27. m阶B 一树的任何一个结点的左右子树的高度都相等。()【中国海洋大学2004 一、4(2分)】A. 正确丿B. 错误28. 非空的平衡二叉树中插入一个结点,原有结点中至少一个结点的平衡因子会改变。 ( )【中南大学2003一、14(1 分)】A. 正确丿B. 错误29.3阶的B 一树是平衡的3路搜索树。反之,一棵平衡的3路搜索树是3阶B 一树。()【清华大学2002二、11(1 分)】A. 正确B. 错误丿B 一树的任意结点的平衡因子都是0,而平衡搜索树结点的平衡因子可以是一 1, 0和1。