计算机专业基础综合数据结构(集合)历年真题试卷汇编5

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