1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 1及答案解析(总分：82.00，做题时间：90 分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key11，其中 key为关键字，为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为 14的数据元素组 A14表示哈希表。(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的 ASL；(3)计算查找不成功时的 ASL。【华中科技大学 2007四、25(10分)】（
2、分数：2.00）_2.采用哈希函数 H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间012中对关键字序列 22，41，53，46，30，13，1，67，51。(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。【北京工业大学 2000三(8 分)】【烟台大学 2007四、4(10 分)】（分数：2.00）_3.设散列表长度为 14，散列函数 （分数：2.00）_4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10
3、，79)，按哈希函数 H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间 A015中构造哈希表。【燕山大学 1999八(14 分)】（分数：2.00）_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 ，)解决冲突。要求：对该关键字序列构造哈希表，
4、指出有哪些同义词并计算查找成功的平均查找长度。（分数：2.00）_6.设哈希表的长度为 15，哈希函数 H(k)=k mod 13，散列地址空间为 014，对关键字序列(19，5，21，24，45，20，68，27，70，11，10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学 2006四、5(5分)】（分数：2.00）_设哈希函数为：H(key)=key mod 13，其中 key为关键字；mod 为取模运算，试用关键字序列(39，25，15，54，26，24，14，21，37，38)构造哈希表：（分数：4
5、.00）(1).用链地址法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度；（分数：2.00）_(2).设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度。【华中科技大学 2006四、4(12 分)】（分数：2.00）_7.设开放定址哈希表的表长为 10，表中元素的编号从 0到 9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词 89，1 8，49，58，69 依次插入到该表中的过程。同时要求对每一步给出简要的说明。【中南大学 2005四、5(10 分)】
6、（分数：2.00）_8.若散列函数为 H(key)=f MOD 7，其中，i 为关键字 key的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空，地址值域为06的散列表中依次插入下列关键字 MON，TUE，WED，THU，FRI，SAT,SUN 以后的散列表。【北京航空航天大学 2005一(10 分)】（分数：2.00）_9.使用散列函数 hash(x)xmod 11，把一个整数值转换成散列表下标，现要把数据：1，13，12，34，38，33，27，22 插入到散列表中。(1)使用线性探查再散列法来构造散列表。(5 分)(2)使用链地址法构造散列表。
7、(5 分)(3)针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。(5 分)【清华大学 1998五(1 5 分)】（分数：2.00）_10.设散列函数 H(k)=k mod 7，散列表的地址空间为 06，对关键字序列32，13，49，18，22，38，21按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计算机应用一、5(5 分)】（分数：2.00）_11.选取哈希函数 H(key)=key mod 7，用链地址法解决冲突。试在 06 的散列地址空间内对关键字序列31，23，17，27，19，11，13，
8、91，61，41构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连海事大学 2001八(10 分)】（分数：2.00）_设哈希(Hash)表的地址范围为 017，哈希函数为：H(K)=K MOD 16，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)，造出哈希表，试回答下列问题：（分数：8.00）(1).画出哈希表示意图。（分数：2.00）_(2).若查找关键字 63，需要依次与哪些关键字比较?（分数：2.00）_(3).若查找关键字 60，需要依次与哪些关键字比较?（分数：2.00）_(4).假定每个关键字
9、的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999三(10 分)】【江苏大学 2006三、3(11 分)】（分数：2.00）_12.试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过 20。并请验证你造的哈希表的实际平均查找长度是否满足要求。(CHA，CAI，LAN，WEN，LONGZHAO，WU，LIU，CHEN，LI，WANG CAO，YUN，CHANG YANG)【清华大学 1996五】（分数：2.00）_设 a，b，c，d，e 五个字符的编码分别为 1，2，3，4，5，并设标识符依以下次序出现：ac，bd，aa，be，ab，ad，cd，bc，ae
10、，ce。要求用哈希(Hash)方法将它们存入具有 10个位置的表中。（分数：4.00）(1).将上述关键字(标识符)构造一个哈希函数，使得发生冲突尽可能地少；（分数：2.00）_(2).线性探测再散列法解决冲突。写出上述各关键字在表中的位置。【南开大学 1998六(10 分)】（分数：2.00）_13.对以下关键字序列建立哈希表： (SUN，MON，TUE，WED，THU，FRI，SAT)，哈希函数为 H(K)=(关键字中第一个字母在字母表中的序号)MOD 7，用线性探测法处理冲突，求构造一个装填因子为 07 的哈希表；并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学 20
11、00二、3(5 分)】（分数：2.00）_设散列表为 HT012，即表的大小为 m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：H 0 (key)=key13；注：是求余数运算(=mod) H i (H i-1 +REV(key+1)1 1+1)13； i=1，2，3，m 一 1 其中，函数 REV表示颠倒 10进制数 x的各位，如 REV(37)=73，REV(7)=7 等。若插入的关键字序列为(2，8，31，20，19，18，53，27)。（分数：4.00）(1).(8分)试画出插入这 8个关键字后的散列表；（分数：2.00）_(2).(5分)计算搜索成功的平均搜索长度 AS
12、L。【清华大学 2000八(13 分)】（分数：2.00）_设一个散列表含 hashsize=13个表项，其下标从 0到 12，采用线性探查法解决冲突。请按以下要求，将关键字10，100，32，45，58，126，3，29，200，400，0散列到表中。（分数：4.00）(1).散列函数采用除留余数法，用hashsize(取余运算)将各关键字映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。(7 分)（分数：2.00）_(2).散列函数采用先将关键字各位数字折叠相加，再用hashsize 将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字可能产生多少次冲突。(8 分)【清华大
13、学 2001五(15 分)】（分数：2.00）_14.有关键字集合 K=15，22，50，13，20，36，28，48，35，31，41，18采用散列存取，散列函数HT014。设散列函数 H(K)=K MOD 13，解决冲突采用开放定址法中的二次探测再散列的方法。试将K值填入 HT表中，并把查找每个关键字所需比较次数 m填入下表中，并请计算出查找成功时的平均查找长度。【中国海洋大学 2005六(12 分)】 （分数：2.00）_已知一组关键字为(26，36，41，38，44，15，68，12，06，51，25)，用链地址法解决冲突。假设装填因子 a=075，散列函数的形式为脚 H(K)=KMO
14、D P，回答下列问题：（分数：6.00）(1).构造出散列函数；(3 分)（分数：2.00）_(2).计算出等概率情况下查找成功的平均查找长度；(3 分)（分数：2.00）_(3).计算出等概率情况下查找失败的平均查找长度。(3 分)【东北大学 1999一、3(9 分)】（分数：2.00）_15.设哈希表的长度为 11，哈希函数 H(K)=K mod 11，散列地址空间为 010，对关键字序列(32，13，49，38，21，60，12)，按二次探测(平方探测)再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功的平均查找长度。【北京交通大学 2005五、6(5 分)】（分
15、数：2.00）_由 14个关键字(87，25，310，08，27，132，68，96，187，133，70，63，47，135)构造链地址法处理冲突的哈希表，哈希函数为 H（key)=key MOD 13，完成下列工作。（分数：4.00）(1).画出该哈希表，并求其查找成功的平均查找长度 ASL；（分数：2.00）_(2).在该哈希表中，若要删除值为 70的关键字，统计需要进行的比较操作次数。【北京工业大学 2005三、3(8分)】（分数：2.00）_给定关键字序列(26，25，20，33，21，24，45，204，42，38，29，31)，要用散列法进行存储，规定负载因子 a=06。（分数：
16、4.00）(1).请给出除余法的散列函数。（分数：2.00）_(2).用开地址线性探测法解决碰撞，请画出插入所有的关键字后得到的散列表，并指出发生碰撞的次数。【北京大学 1997三(6 分)】（分数：2.00）_16.已知记录关键字集合为(53，17，19，6l，98，75，79，63，46，49)要求散列到地址区间(100，101，102，103，104，105，106，107，108，109)内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。(设等概率情况)【东北大学 1998一、2(10 分)】（分数
17、：2.00）_17.Fibonacci树是一种特殊的二叉树，下面给出构造该树的一种算法： procedure FibonacciTree(d： integer； Var T： binarytree) (d 是 Fibonacci树的深度 if d=0 then T：=nil elsenew(T)； if d=1 then (Tlefptr：=nil； Trightptr：=nil ) else d=2 FibonacciTree(d 一 2， T1eftptr)； FibonacciTree(d 一 1， Trightptr)； (1)画出深度为 4的 Fibonacci树(即用 d=4调用上
18、述算法的结果)。(7 分) (2)从你画的树中分析深度为 d的 Fibonacci树中结点总数和Hbonacci数的关系。 Fibonacci 数定义如下： F n =1， F 1 =1 F n =F n-1 +F n-2 n1 (3)你所画出的Fibonacci树是否为平衡二叉树?若是，它是否为同样深度的平衡二叉树中结点数目最少的一种?(4 分)【中国科学技术大学 1998三(15 分)】（分数：2.00）_二、设计题(总题数：4，分数：10.00)已知某哈希表 HT的装填因子小于 1，哈希函数 H(key)为关键字的第一个字母在字母表中的序号。【西北大学 2001五】（分数：4.00）(1
19、).处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。（分数：2.00）_(2).处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。（分数：2.00）_18.有一个 100 * 100的稀疏矩阵，其中 1的元素为非零元素，现要求用哈希表作存储结构。 (1)请你设计一个哈希表。 (2)请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组(每个分量存放一个非零元素的行值、列值和元素值)作存储结构时存取元素的算法(注：此算法不需要写出，仅需说
20、明存取的方法和所用时间)进行比较。【北方交通大学 1994六(16 分)】（分数：2.00）_19.将一组数据元素按哈希函数 H(key)散列到哈希表 HT(0：m)中，用线性探测法处理冲突 H(key)+1，H(key)+2，H(key)一 1)，假设空单元用 EMPTY表示，删除操作是将哈希表中结点标志位从 INUSE标记为 DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001五、2(10分)】（分数：2.00）_20.设给定关键字输入序列为(100，90，120，60，78，35，42，31，15)用散列法散列 010 的地址区间。要求设计一合理的散
21、列函数；冲突时用链表法解决,写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少?【东北大学 1996四(12 分)】（分数：2.00）_计算机专业基础综合数据结构（集合）历年真题试卷汇编 1答案解析(总分：82.00，做题时间：90 分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key11，其中 key为关键字，为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为 14的数据元素组 A14表示哈希表。(1)画出该
22、哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的 ASL；(3)计算查找不成功时的 ASL。【华中科技大学 2007四、25(10分)】（分数：2.00）_正确答案：(正确答案：(1) )解析：2.采用哈希函数 H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间012中对关键字序列 22，41，53，46，30，13，1，67，51。(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。【北京工业大学 2000三(8 分)】【烟台大学 2007四、4(10 分)】（分数：2.00）_正确答案：(正确答案：
23、(1) )解析：3.设散列表长度为 14，散列函数 （分数：2.00）_正确答案：(正确答案：(1)ASL SUCC =1912 (2) )解析：4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数 H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间 A015中构造哈希表。【燕山大学 1999八(14 分)】（分数：2.00）_正确答案：(正确答案：常用构造哈希函数的方法有： (1)数字分析法。该方法需要事先知道关键字集合，且关键字位数比散列
24、表地址位数多，应选数字分布均匀的位。 (2)平方取中法。将关键字值的平方取中间几位作哈希地址。 (3)除留余数法。H(key)=keyp，通常 P取小于等于表长的最大素数。 (4)折叠法。将关键字分成长度相等(最后一段可不等)的几部分，进行移位叠加或间界叠加，其值作为哈希地址。 (5)基数转换法。两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在链地址法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。 )解析：5.解答题。【中国海洋大学 2006六
25、(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 ，)解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。（分数：2.00）_正确答案：(正确答案：(1)ASL 成功 =(1*1+2*2+4*3+3*4)10=2910(4*3 含义是 4个长度为 3的结点)判定树请参见上
26、面第 9题。 (2)55、20 和 27是同义词，9 和 23是同义词，14 和 84是同义词。 )解析：6.设哈希表的长度为 15，哈希函数 H(k)=k mod 13，散列地址空间为 014，对关键字序列(19，5，21，24，45，20，68，27，70，11，10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学 2006四、5(5分)】（分数：2.00）_正确答案：(正确答案： )解析：设哈希函数为：H(key)=key mod 13，其中 key为关键字；mod 为取模运算，试用关键字序列(39，25
27、，15，54，26，24，14，21，37，38)构造哈希表：（分数：4.00）(1).用链地址法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度；（分数：2.00）_正确答案：(正确答案： )解析：(2).设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度。【华中科技大学 2006四、4(12 分)】（分数：2.00）_正确答案：(正确答案：ASL AUCC =118 ASL UNSUCC =1911 值得指出的是，对用链地址法求查找失败时的平均查找长度有两种观点。
28、其一，认为比较到空指针算失败。以本题为例，哈希地址 0、2、5、7、9 和10均为比较 1次失败，而哈希地址 1和 3比较 2次失败，其余哈希地址均为比较 3次失败，因此，查找失败时的平均查找长度为 1911，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的 ASL UNSUCC =(1+1+2+2+2)11=811。)解析：7.设开放定址哈希表的表长为 10，表中元素的编号从 0到 9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词 89，1 8，49，58，69 依次插入到该表中的过程。同时要求对每一步给出简要的说
29、明。【中南大学 2005四、5(10 分)】（分数：2.00）_正确答案：(正确答案：设哈希函数为 H(key)=key7。数据太少，哈希函数得当，未发生冲突。 )解析：8.若散列函数为 H(key)=f MOD 7，其中，i 为关键字 key的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空，地址值域为06的散列表中依次插入下列关键字 MON，TUE，WED，THU，FRI，SAT,SUN 以后的散列表。【北京航空航天大学 2005一(10 分)】（分数：2.00）_正确答案：(正确答案： )解析：9.使用散列函数 hash(x)xmod 11，把
30、一个整数值转换成散列表下标，现要把数据：1，13，12，34，38，33，27，22 插入到散列表中。(1)使用线性探查再散列法来构造散列表。(5 分)(2)使用链地址法构造散列表。(5 分)(3)针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。(5 分)【清华大学 1998五(1 5 分)】（分数：2.00）_正确答案：(正确答案：由 hashf(x)=mod 11可知，散列地址空间是 0到 10，由于有 8个数据，装载因子取 07。 (1) ASL SUCC =218 ASL UNSUCC =4711 (2)ASL SUCC =138;ASL
31、UNSUCC =1911 )解析：10.设散列函数 H(k)=k mod 7，散列表的地址空间为 06，对关键字序列32，13，49，18，22，38，21按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计算机应用一、5(5 分)】（分数：2.00）_正确答案：(正确答案：查找时，对关键 49，22，38，32，13 各比较一次，对 21，18 各比较两次。)解析：11.选取哈希函数 H(key)=key mod 7，用链地址法解决冲突。试在 06 的散列地址空间内对关键字序列31，23，17，27，19，11，13，91，61，41构造哈希表，
32、并计算在等概率下成功查找的平均查找长度。【大连海事大学 2001八(10 分)】（分数：2.00）_正确答案：(正确答案：ASL SUCC =1510 )解析：设哈希(Hash)表的地址范围为 017，哈希函数为：H(K)=K MOD 16，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)，造出哈希表，试回答下列问题：（分数：8.00）(1).画出哈希表示意图。（分数：2.00）_正确答案：(正确答案： )解析：(2).若查找关键字 63，需要依次与哪些关键字比较?（分数：2.00）_正确答案：(正确答案：查找关键字 63，H(k)=63 MOD 16=15，依次与 31，46，47，32，17，63 比较。)解析：(3).若查找关键字 60，需要依次与哪些关键字比较?（分数：2.00）_正确答案：(正确答案：查找关键字 60，H(k)=60 MOD 16=12，散列地址 12内为空，查找失败。)解析：(4).假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999三(10 分)】【江苏大学
