《计算机专业基础综合数据结构(集合)历年真题试卷汇编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。
