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