计算机专业基础综合数据结构(集合)历年真题试卷汇编1
- 格式：docx
- 大小：33.18 KB
- 文档页数：6
计算机专业基础综合数据结构（集合）历年真题试卷汇编1
(总分：82.00，做题时间：90分钟)
一、 综合题(总题数：25，分数：72.00)
1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。【华中科技大学2007四、25(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：(1)
(2)ASL 成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败
=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。计算方法参见上面58题(3)。)
2.采用哈希函数H(k)=3*k
mod
13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：(1) (2)装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)
3.设散列表长度为14，散列函数，其中i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。【厦门大学2001二、2(24％／3分)】
__________________________________________________________________________________________
正确答案：(正确答案：(1)ASL SUCC =19／12 (2) )
4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间A[0．．15]中构造哈希表。【燕山大学1999八(14分)】
__________________________________________________________________________________________
正确答案：(正确答案：常用构造哈希函数的方法有： (1)数字分析法。该方法需要事先知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。 (2)平方取中法。将关键字值的平方取中间几位作哈希地址。 (3)除留余数法。H(key)=key％p，通常P取小于等于表长的最大素数。 (4)折叠法。将关键字分成长度相等(最后一段可不等)的几部分，进行移位叠加或间界叠加，其值作为哈希地址。 (5)基数转换法。两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在链地址法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。)
5.解答题。【中国海洋大学2006六(15分)】 (1)画出对长度为10的有序表进行折半查找的查找树，并求其等概率时查找成功的平均查找长度。 (2)设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H(key)=key MOD 7，表长为10，用开放地址法的二次探测再散列方法胁=H(key)+di)MOD 10(di=1 2 ，2 2 ，3 2 ，…)解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。
__________________________________________________________________________________________
正确答案：(正确答案：(1)ASL 成功 =(1*1+2*2+4*3+3*4)／10=29／10(4*3含义是4个长度为3的结点)判定树请参见上面第9题。 (2)55、20和27是同义词，9和23是同义词，14和84是同义词。 ASL 成功 =(4*1+2*2+2*3)／8=14／) 6.设哈希表的长度为15，哈希函数H(k)=k mod 13，散列地址空间为0～14，对关键字序列(19，5，21，24，45，20，68，27，70，11，10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学2006四、5(5分)】
__________________________________________________________________________________________
正确答案：(正确答案：
ASL 成功 =(6*1+2*2+3+4+6)／11=23／1 1 ASL 失败
=(1+2+1+2+1+10+9+8+7+6+5+4+3)／13=59／13)
设哈希函数为：H(key)=key mod
13，其中key为关键字；mod为取模运算，试用关键字序列(39，25，15，54，26，24，14，21，37，38)构造哈希表：（分数：4.00）
(1).用链地址法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度；
__________________________________________________________________________________________
正确答案：(正确答案： ASL SUCC =(1+1+1+2+1+2+1+2)／8=1 1／8 ASL UNSUCC =(1+2+1+8+7+6+5+4+3+2+1)／1 1=40／1 1)
(2).设表地址范围为0～13，用线性探测再散列法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度。【华中科技大学2006四、4(12分)】
__________________________________________________________________________________________
正确答案：(正确答案：ASL AUCC =11／8 ASL UNSUCC =19／11值得指出的是，对用链地址法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19／11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASL UNSUCC =(1+1+2+2+2)／11=8／11。)
7.设开放定址哈希表的表长为10，表中元素的编号从0到9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词89，1 8，49，58，69依次插入到该表中的过程。同时要求对每一步给出简要的说明。【中南大学2005四、5(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：设哈希函数为H(key)=key％7。数据太少，哈希函数得当，未发生冲突。)
8.若散列函数为H(key)=f MOD 7，其中，i为关键字key的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空，地址值域为[0．．6]的散列表中依次插入下列关键字MON，TUE，WED，THU，FRI，SAT,SUN以后的散列表。【北京航空航天大学2005一(10分)】
__________________________________________________________________________________________
正确答案：(正确答案：)
9.使用散列函数hash(x)xmod 11，把一个整数值转换成散列表下标，现要把数据：1，13，12，34，38，33，27，22插入到散列表中。(1)使用线性探查再散列法来构造散列表。(5分)(2)使用链地址法构造散列表。(5分)(3)针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。(5分)【清华大学1998五(1 5分)】
__________________________________________________________________________________________
正确答案：(正确答案：由hashf(x)=mod 11可知，散列地址空间是0到10，由于有8个数据，装载因子取0．7。 (1) ASL SUCC =21／8 ASL UNSUCC =47／11 (2)ASL SUCC =13／8;ASL UNSUCC =19／11 )
10.设散列函数H(k)=k mod 7，散列表的地址空间为0～6，对关键字序列{32，13，49，18，22，38，21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计算机应用一、5(5分)】
__________________________________________________________________________________________
正确答案：(正确答案：查找时，对关键49，22，38，32，13各比较一次，对21，18各比较两次。)
