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