1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 9 及答案与解析一、综合题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 采用哈希函数 H(k)=3*k mod 13 并用线性探测开放地
2、址法处理冲突，在散列地址空间0 12中对关键字序列 22，41，53，46，30，13，1，67，51。(1)构造哈希表(画示意图) ；(2) 装填因子；等概率下 (3)成功的和(4) 不成功的平均查找长度。【北京工业大学 2000 三(8 分)】【烟台大学 2007 四、4(10 分)】3 设散列表长度为 14，散列函数 ，其中 i 为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb ，Mar，Apr，May，Jun，Jul ，Aug ，Sep，Oct ，Nov ，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2) 求出在等概率情况下，查找成功的平均查找长度。【厦门大
3、学 2001 二、2(243 分)】4 常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作? 为什么?已知一组关键字为 (19，14，23，01，68，20 ，84，27，55，11，10，79)，按哈希函数 H(Key)=KeyMOD 13 和线性探测再散列处理冲突的方法在地址空间A0 15中构造哈希表。【燕山大学 1999 八(14 分)】5 解答题。【中国海洋大学 2006 六(15 分)】 (1) 画出对长度为 10 的有序表进行折半查找的查找树，并求其等概率时查找成功的平均查找长度。 (2)设有一组关键字9，01 ，23， 14，55，20 ，84，27 ，采用哈希
4、函数： H(key)=key MOD 7，表长为10，用开放地址法的二次探测再散列方法胁=H(key)+di)MOD 10(di=12，2 2，3 2，)解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。6 设哈希表的长度为 15，哈希函数 H(k)=k mod 13，散列地址空间为 014，对关键字序列(19 ，5，21，24，45，20，68，27，70，11，10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学 2006 四、5(5 分)】6 设哈希函数为：H(key
5、)=key mod 13，其中 key 为关键字；mod 为取模运算，试用关键字序列(39，25，15，54，26，24，14，21，37，38)构造哈希表：7 用链地址法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度；8 设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度。【华中科技大学 2006 四、4(12 分)】9 设开放定址哈希表的表长为 10，表中元素的编号从 0 到 9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词 89，1 8，49，5
6、8，69 依次插入到该表中的过程。同时要求对每一步给出简要的说明。【中南大学 2005 四、5(10 分)】10 若散列函数为 H(key)=f MOD 7，其中，i 为关键字 key 的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空，地址值域为06 的散列表中依次插入下列关键字MON，TUE，WED，THU，FRI，SAT,SUN 以后的散列表。【北京航空航天大学2005 一(10 分) 】11 使用散列函数 hash(x)xmod 11，把一个整数值转换成散列表下标，现要把数据：1，13，12，34，38，33，27，22 插入到散列表中。(1
7、)使用线性探查再散列法来构造散列表。(5 分)(2)使用链地址法构造散列表。(5 分)(3)针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。(5 分)【清华大学 1998 五(1 5 分)】12 设散列函数 H(k)=k mod 7，散列表的地址空间为 06，对关键字序列32，13 ，49 ，18，22，38 ，21 按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学 1999 计算机应用一、5(5 分)】13 选取哈希函数 H(key)=key mod 7，用链地址法解决冲突。试在 06 的散列地址空间内对关
8、键字序列31， 23，17，27，19，11，13，91，61，41 构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连海事大学 2001 八(10 分)】13 设哈希(Hash)表的地址范围为 017，哈希函数为：H(K)=K MOD 16，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列：(10，24 ，32，17，31，30，46，47，40，63，49)，造出哈希表，试回答下列问题：14 画出哈希表示意图。15 若查找关键字 63，需要依次与哪些关键字比较?16 若查找关键字 60，需要依次与哪些关键字比较?17 假定每个关键字的查找概率相等，求查找成功时的平均查找长度
9、。【华中理工大学 1999 三(10 分) 】【江苏大学 2006 三、3(11 分)】18 试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过 20。并请验证你造的哈希表的实际平均查找长度是否满足要求。(CHA，CAI，LAN，WEN ，LONGZHAO，WU，LIU，CHEN ，LI ，WANG CAO，YUN，CHANG YANG)【清华大学 1996 五】18 设 a，b， c，d，e 五个字符的编码分别为 1，2，3，4，5，并设标识符依以下次序出现：ac，bd，aa，be，ab ，ad，cd，bc，ae，ce。要求用哈希(Hash)方法将它们存入具有 10 个
10、位置的表中。19 将上述关键字(标识符)构造一个哈希函数，使得发生冲突尽可能地少；20 线性探测再散列法解决冲突。写出上述各关键字在表中的位置。【南开大学1998 六(10 分) 】21 对以下关键字序列建立哈希表： (SUN，MON，TUE，WED ，THU，FRI ，SAT)，哈希函数为 H(K)=(关键字中第一个字母在字母表中的序号)MOD 7，用线性探测法处理冲突，求构造一个装填因子为 07 的哈希表；并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学 2000 二、3(5 分)】21 设散列表为 HT012 ，即表的大小为 m=13。现采用双散列法解决冲突。散列函数
11、和再散列函数分别为： H 0(key)=key13；注：是求余数运算(=mod) Hi(Hi-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)。22 (8 分 )试画出插入这 8 个关键字后的散列表；23 (5 分 )计算搜索成功的平均搜索长度 ASL。【清华大学 2000 八(13 分)】23 设一个散列表含 hashsize=13 个表项，其下标从 0 到 12，采用线性探查法解决冲突。请按以下
12、要求，将关键字10，100 ，32 ，45，58， 126，3，29，200，400，0 散列到表中。24 散列函数采用除留余数法，用hashsize(取余运算)将各关键字映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。(7 分)25 散列函数采用先将关键字各位数字折叠相加，再用hashsize 将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字可能产生多少次冲突。(8 分)【清华大学 2001 五(15 分)】26 有关键字集合 K=15，22，50，13，20，36，28，48，35，31，41，18采用散列存取，散列函数 HT014。设散列函数 H(K)=K MOD
13、13，解决冲突采用开放定址法中的二次探测再散列的方法。试将 K 值填入 HT 表中，并把查找每个关键字所需比较次数 m 填入下表中，并请计算出查找成功时的平均查找长度。 【中国海洋大学 2005 六(12 分)】26 已知一组关键字为(26，36，41，38，44，15，68，12，06，51，25)，用链地址法解决冲突。假设装填因子 a=075，散列函数的形式为脚 H(K)=KMOD P，回答下列问题：27 构造出散列函数；(3 分)28 计算出等概率情况下查找成功的平均查找长度；(3 分)29 计算出等概率情况下查找失败的平均查找长度。(3 分)【东北大学 1999 一、3(9分)】30
14、设哈希表的长度为 11，哈希函数 H(K)=K mod 11，散列地址空间为 010，对关键字序列(32，13，49，38，21，60，12)，按二次探测(平方探测)再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功的平均查找长度。【北京交通大学 2005 五、6(5 分)】30 由 14 个关键字(87，25 ，310，08，27，132，68，96，187，133，70，63，47，135)构造链地址法处理冲突的哈希表，哈希函数为 H（key)=key MOD 13，完成下列工作。31 画出该哈希表，并求其查找成功的平均查找长度 ASL；32 在该哈希表中，若要删除
15、值为 70 的关键字，统计需要进行的比较操作次数。【北京工业大学 2005 三、3(8 分)】32 给定关键字序列(26，25，20，33，21，24，45，204，42，38，29，31)，要用散列法进行存储，规定负载因子 a=06。33 请给出除余法的散列函数。34 用开地址线性探测法解决碰撞，请画出插入所有的关键字后得到的散列表，并指出发生碰撞的次数。【北京大学 1997 三(6 分)】35 已知记录关键字集合为(53，17，19，6l，98， 75，79，63，46，49)要求散列到地址区间(100，101，102，103，104，105，106，107，108，109)内，若产生冲突
16、用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。(设等概率情况)【东北大学 1998 一、2(10 分) 】36 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 Fibonacci
17、Tree(d 一 2， T1eftptr)； FibonacciTree(d 一 1， Trightptr) ； (1)画出深度为 4 的 Fibonacci 树(即用 d=4 调用上述算法的结果 )。(7 分) (2)从你画的树中分析深度为 d 的 Fibonacci 树中结点总数和 Hbonacci 数的关系。 Fibonacci 数定义如下： F n=1， F 1=1 Fn=Fn-1+Fn-2 n1 (3)你所画出的 Fibonacci 树是否为平衡二叉树? 若是，它是否为同样深度的平衡二叉树中结点数目最少的一种?(4分)【中国科学技术大学 1998 三(15 分)】二、设计题36 已知
18、某哈希表 HT 的装填因子小于 1，哈希函数 H(key)为关键字的第一个字母在字母表中的序号。【西北大学 2001 五】37 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。38 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。39 有一个 100*100 的稀疏矩阵，其中 1的元素为非零元素，现要求用哈希表作存储结构。 (1)请你设计一个哈希表。 (2) 请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组(每个分量存放一个非零
19、元素的行值、列值和元素值)作存储结构时存取元素的算法(注：此算法不需要写出，仅需说明存取的方法和所用时间)进行比较。【北方交通大学 1994 六(16分)】40 将一组数据元素按哈希函数 H(key)散列到哈希表 HT(0：m)中，用线性探测法处理冲突 H(key)+1，H(key)+2，H(key)一 1)，假设空单元用 EMPTY 表示，删除操作是将哈希表中结点标志位从 INUSE 标记为 DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001 五、2(10 分)】41 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15)用
20、散列法散列 010 的地址区间。要求设计一合理的散列函数；冲突时用链表法解决,写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少?【东北大学 1996 四(12 分)】计算机专业基础综合数据结构（集合）历年真题试卷汇编 9 答案与解析一、综合题1 【正确答案】 (1)(2)ASL 成功 =(6*1+2*3+5+7)10=2410(3)ASL 失败 =(4+3+2+1+2+1+1+2+1+9+8)11=34 1 1 。计算方法参见上面 58 题(3) 。2 【正确答案】 (1)(2)装填因子=913=07 (3)ASL SUCC=119 (4)ASL UNSUCC=29
21、133 【正确答案】 (1)ASL SUCC=1912 (2)4 【正确答案】 常用构造哈希函数的方法有：(1)数字分析法。该方法需要事先知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。(2)平方取中法。将关键字值的平方取中间几位作哈希地址。(3)除留余数法。H(key)=keyp，通常 P 取小于等于表长的最大素数。(4)折叠法。将关键字分成长度相等(最后一段可不等) 的几部分，进行移位叠加或间界叠加，其值作为哈希地址。(5)基数转换法。两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在链地址法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作
22、删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。5 【正确答案】 (1)ASL 成功 =(1*1+2*2+4*3+3*4)10=2910(4*3 含义是 4 个长度为 3 的结点)判定树请参见上面第 9 题。(2)55、20 和 27 是同义词，9 和 23 是同义词，14 和 84 是同义词。ASL 成功 =(4*1+2*2+2*3)8=146 【正确答案】 ASL 成功 =(6*1+2*2+3+4+6)11=231 1ASL 失败 =(1+2+1+2+1+10+9+8+7+6+5+4+3)13=59 137 【正确答案
23、】 ASLSUCC=(1+1+1+2+1+2+1+2)8=1 18ASL UNSUCC=(1+2+1+8+7+6+5+4+3+2+1)1 1=401 18 【正确答案】 ASL AUCC=118 ASL UNSUCC=1911 值得指出的是，对用链地址法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址 0、2、5、7、9 和 10 均为比较 1 次失败，而哈希地址 1 和 3 比较 2 次失败，其余哈希地址均为比较 3 次失败，因此，查找失败时的平均查找长度为 1911，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比
24、较不计算。照这种观点，本题的ASLUNSUCC=(1+1+2+2+2)11=8 11。9 【正确答案】 设哈希函数为 H(key)=key7。数据太少，哈希函数得当，未发生冲突。10 【正确答案】 11 【正确答案】 由 hashf(x)=mod 11 可知，散列地址空间是 0 到 10，由于有 8 个数据，装载因子取 07。(1)ASLSUCC=218 ASL UNSUCC=4711(2)ASL SUCC=138;ASL UNSUCC=191112 【正确答案】 查找时，对关键 49，22，38，32，13 各比较一次，对 21，18 各比较两次。13 【正确答案】 ASL SUCC=151
25、014 【正确答案】 15 【正确答案】 查找关键字 63，H(k)=63 MOD 16=15 ，依次与31，46，47，32，17，63 比较。16 【正确答案】 查找关键字 60，H(k)=60 MOD 16=12 ，散列地址 12 内为空，查找失败。17 【正确答案】 ASL SUCC=231118 【正确答案】 设用线性探测再散列解决冲突，根据公式 Snl(1+1(1 一 )2。可求出负载因子为 =067。再根据数据个数和装填因子，可求出表长m=15 067 ，取 m=23。设哈希函数 H(key)=(关键字首尾字母在字母表中序号之和)MOD23。从上表求出查找成功时的平均查找长度为
26、ASLSUCC=191 519 【正确答案】 哈希函数 H(key)=(关键字各字符编码之和)MOD720 【正确答案】 21 【正确答案】 =07，所以表长取 m=707=10ASLSUCC=1 87 ASL UNSUCC=207(哈希地址 0 6)22 【正确答案】 23 【正确答案】 ASL SUCC=11824 【正确答案】 关键字 29 和 45 各发生一次冲突，关键字 58、126 和 400 各发生两次冲突，其余关键字无冲突。25 【正确答案】 发生冲突次数：100、126 一次(探测 2 次)；200、400 两次；0 七次。其余关键字无冲突。26 【正确答案】 ASL=(7*
27、1+2*2+2*3+4)12=211227 【正确答案】 由 =075，得表长 m=110 75=15。(1)散列函数 H(k)=k MOD 13(p 取小于等于表长的最大素数)因为 p=13，散列地址 012，因为用链地址法解决冲突，所以实际长度取 13。28 【正确答案】 ASL SUCC=181 129 【正确答案】 ASL UNSUCC=241 330 【正确答案】 ASL=(4*1+2*2+3)7=11731 【正确答案】 哈希表略。ASL=(8*1+4*2+3+4)14=2314。32 【正确答案】 70 的哈希地址是 5，链表中在它之前有 96，187(按尾插法建立链表)，要比较
28、 3 次找到 70。33 【正确答案】 表长 m=1206=20 。(1)H(key)=key MOD 19(19 是小于 20 的最大素数)。34 【正确答案】 两次碰撞。26 和 45，33 和 204。35 【正确答案】 由于地址空间为 10，且从 100 开始，故散列函数选为 H(key)=key7+100。用线性探测再散列解决冲突，ASL succ=2710，因哈希空间已填满记录，故ASLunsucc=10。36 【正确答案】 (1) (2)见本章应用题第 30 题。(3)上面所画出的 Fibonacci 树是平衡二叉树，而且是同样深度的平衡二叉树中结点数目最少的一种。二、设计题37
29、 【正确答案】 由于装填因子小于 1，且哈希函数 H(k)为关键字第一个字母在字母表中的序号，字母 A 的序号为 1，表长可设为 n(n27)，而在链地址法中，表长为 26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数，请参见本章应用题第 65 题(2)。核心语句段如下：for(i=1；i26；i+) 哈希地址 1 到 26(j=1；count(next；count+=j；return (count260)；39 【正确答案】 非零元素个数是 100，负载因子取 08，表长 125 左右，取 p 为127，散列地址为 0 到 126。哈希函数用 H(k)=(3*i+2*f)1
30、27，i、j 为行值和列值。40 【正确答案】 本题哈希函数 H(key)，用线性探测解决冲突，空单元用EMPTY，删除标记用 DELETED，占用单元用 INUSE，其他均符合哈希表标准操作。插入、删除都以查找为基础，这里只给出查找的核心语句如下：i=H(key)； 计算哈希地址if(HTi=EMPTY)return(false)； 查找失败else if(HTi=key)return (true)；elsej=(i+1)m； 形成探测序列while(j!=i) 至多循环哈希表长if(HTj =key)return (true)； 查找成功else if(HTj=EMPTY)return(false)； 查找失败j=(j+1)m；return (false)； 查遍哈希表，未查到给定关键字 key else41 【正确答案】 用链地址法解决冲突，构造散列表，散列函数用 H(key)=key11。核心语句如下：for(i=0；ikey=x；if(rail=null)HTj=p； 第一个数据结点elsewhile(rail 一next!=null)rail=rail 一next ； 查找同义词链表尾rail 一 next=p；将插入结点链入同义词表查找成功时的平均查找长度 ASL=129。
