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